Matrices using a bitsliced representation. More...

#include <m4ri/m4ri.h>
#include "mzd_poly.h"
#include "mzed.h"

Data Structures
struct	mzd_slice_t
	Dense matrices over \(\mathbb{F}_{2^e}\) represented as slices of matrices over \(\mathbb{F}_2\). More...
Defines
#define	__M4RIE_MAX_KARATSUBA_DEGREE 8
#define	mzd_slice_sub mzd_slice_add
	\( C = A + B\).
#define	_mzd_slice_sub _mzd_slice_add
	\( C = A + B\).
Functions
static mzd_slice_t *	mzd_slice_init (const gf2e *ff, const rci_t m, const rci_t n)
	Create a new matrix of dimension \( m \times n\) over ff.
void	mzd_slice_set_ui (mzd_slice_t *A, word value)
	Return diagonal matrix with value on the diagonal.
static mzd_slice_t *	_mzd_slice_adapt_depth (mzd_slice_t *A, const unsigned int new_depth)
	Extend or truncate the depth of A to depth new_depth.
static void	mzd_slice_free (mzd_slice_t *A)
	Free a matrix created with mzd_slice_init().
static mzd_slice_t *	mzd_slice_concat (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	Concatenate B to A and write the result to C.
static mzd_slice_t *	mzd_slice_stack (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	Stack A on top of B and write the result to C.
static mzd_slice_t *	mzd_slice_submatrix (mzd_slice_t S, const mzd_slice_t A, const size_t lowr, const size_t lowc, const size_t highr, const size_t highc)
	Copy a submatrix.
static mzd_slice_t *	mzd_slice_init_window (const mzd_slice_t *A, const size_t lowr, const size_t lowc, const size_t highr, const size_t highc)
	Create a window/view into the matrix M.
static void	mzd_slice_free_window (mzd_slice_t *A)
	Free a matrix window created with mzd_slice_init_window().
static mzd_slice_t *	_mzd_slice_add (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A + B\).
static mzd_slice_t *	mzd_slice_add (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A + B\).
mzd_slice_t *	_mzd_slice_mul_naive (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \) using quadratic polynomial multiplication with matrix coefficients.
mzd_slice_t *	_mzd_slice_mul_karatsuba2 (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \) over \(\mathbb{F}_{2^2}\) using 3 multiplications over \(\mathbb{F}_2\) and 2 temporary \(\mathbb{F}_2\) matrices..
mzd_slice_t *	_mzd_slice_mul_karatsuba3 (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \) over \(\mathbb{F}_{2^3}\) using 6 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices..
mzd_slice_t *	_mzd_slice_mul_karatsuba4 (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \) over \(\mathbb{F}_{2^4}\) using 9 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices..
mzd_slice_t *	_mzd_slice_mul_karatsuba5 (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \) over \(\mathbb{F}_{2^5}\) using 13 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices..
mzd_slice_t *	_mzd_slice_mul_karatsuba6 (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \) over \(\mathbb{F}_{2^6}\) using 17 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices.
mzd_slice_t *	_mzd_slice_mul_karatsuba7 (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \) over \(\mathbb{F}_{2^7}\) using 22 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices.
mzd_slice_t *	_mzd_slice_mul_karatsuba8 (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \) over \(\mathbb{F}_{2^8}\) using 27 multiplications over \(\mathbb{F}_2\) and 15 temporary \(\mathbb{F}_2\) matrices.
static mzd_slice_t *	_mzd_slice_mul_karatsuba (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = C + A \cdot B \) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\).
static mzd_slice_t *	mzd_slice_mul_karatsuba (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\).
static mzd_slice_t *	mzd_slice_addmul_karatsuba (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = C + A \cdot B\) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\).
mzd_slice_t *	mzd_slice_mul_scalar (mzd_slice_t C, const word a, const mzd_slice_t B)
	\( C = a \cdot B \).
mzd_slice_t *	mzd_slice_addmul_scalar (mzd_slice_t C, const word a, const mzd_slice_t B)
	\( C += a \cdot B \).
static mzd_slice_t *	mzd_slice_mul (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A \cdot B \).
static mzd_slice_t *	mzd_slice_addmul (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = C + A \cdot B \).
static void	mzd_slice_randomize (mzd_slice_t *A)
	Fill matrix A with random elements.
static mzd_slice_t *	mzd_slice_copy (mzd_slice_t B, const mzd_slice_t A)
	Copy matrix A to B.
static word	mzd_slice_read_elem (const mzd_slice_t *A, const rci_t row, const rci_t col)
	Get the element at position (row,col) from the matrix A.
static void	mzd_slice_add_elem (mzd_slice_t *A, const rci_t row, const rci_t col, word elem)
	At the element elem to the element at position (row,col) in the matrix A.
static void	mzd_slice_write_elem (mzd_slice_t *A, const rci_t row, const rci_t col, word elem)
	Write the element elem to the position (row,col) in the matrix A.
static int	mzd_slice_cmp (mzd_slice_t A, mzd_slice_t B)
	Return -1,0,1 if if A < B, A == B or A > B respectively.
static int	mzd_slice_is_zero (const mzd_slice_t *A)
	Zero test for matrix.
static void	mzd_slice_row_swap (mzd_slice_t *A, const rci_t rowa, const rci_t rowb)
	Swap the two rows rowa and rowb.
static void	mzd_slice_copy_row (mzd_slice_t B, size_t i, const mzd_slice_t A, size_t j)
	copy row j from A to row i from B.
static void	mzd_slice_col_swap (mzd_slice_t *A, const rci_t cola, const rci_t colb)
	Swap the two columns cola and colb.
static void	mzd_slice_col_swap_in_rows (mzd_slice_t *A, const rci_t cola, const rci_t colb, const rci_t start_row, rci_t stop_row)
	Swap the two columns cola and colb but only between start_row and stop_row.
static void	mzd_slice_row_add (mzd_slice_t *A, const rci_t sourcerow, const rci_t destrow)
	Add the rows sourcerow and destrow and stores the total in the row destrow.
static void	mzd_slice_row_clear_offset (mzd_slice_t *A, const rci_t row, const rci_t coloffset)
	Clear the given row, but only begins at the column coloffset.
void	mzd_slice_print (const mzd_slice_t *A)
	Print a matrix to stdout.
static void	_mzd_slice_compress_l (mzd_slice_t *A, const rci_t r1, const rci_t n1, const rci_t r2)
	Move the submatrix L of rank r2 starting at column n1 to the left to column r1.

Detailed Description

Matrices using a bitsliced representation.

Matrices over \(\mathbb{F}_{2^e}\) can be represented as polynomials with matrix coefficients where the matrices are in \(\mathbb{F}_2\).

In this file, matrices over \(\mathbb{F}_{2^e}\) are implemented as \(e\) slices of matrices over \(\mathbb{F}_2\) where each slice holds the coefficients of one degree when viewing elements of \(\mathbb{F}_{2^e}\) as polynomials over \(\mathbb{F}_2\).

Author:: Martin Albrecht marti.nosp@m.nral.nosp@m.brech.nosp@m.t@go.nosp@m.oglem.nosp@m.ail..nosp@m.com

Define Documentation

#define __M4RIE_MAX_KARATSUBA_DEGREE 8

Degree up to which Karatsuba multiplication and slicing/cling is implemented.

Examples:: tests/test_elimination.cc.

Function Documentation

static mzd_slice_t* _mzd_slice_adapt_depth	(	mzd_slice_t *	A,
		const unsigned int	new_depth
	)		`[inline, static]`

Extend or truncate the depth of A to depth new_depth.

We may think of mzd_slice_t as polynomials over matrices over \(\mathbb{F}_2\). This function then truncates/extends these polynomials to degree new_depth-1. In case of extension, all newly created coefficients are zero, hence the mathematical content of A is not changed. In case of truncation higher degree terms are simply deleted and A's mathematical content modified.

Parameters:

A	Matrix, modifed in place.
new_depth	Integer >= mzd_slice_t::finite_field::degree.

static void _mzd_slice_compress_l	(	mzd_slice_t *	A,
		const rci_t	r1,
		const rci_t	n1,
		const rci_t	r2
	)		`[inline, static]`

Move the submatrix L of rank r2 starting at column n1 to the left to column r1.

Parameters:

A	Matrix
r1	Integer < n1
n1	Integer > r1
r2	Integer <= A->ncols - n1

static int mzd_slice_cmp	(	mzd_slice_t *	A,
		mzd_slice_t *	B
	)		`[inline, static]`

Return -1,0,1 if if A < B, A == B or A > B respectively.

Parameters:

A	Matrix.
B	Matrix.

Note:: This comparison is not well defined (except for !=0) mathematically and relatively arbitrary since elements of GF(2^k) don't have an ordering.

static void mzd_slice_col_swap_in_rows	(	mzd_slice_t *	A,
		const rci_t	cola,
		const rci_t	colb,
		const rci_t	start_row,
		rci_t	stop_row
	)		`[inline, static]`

Swap the two columns cola and colb but only between start_row and stop_row.

Parameters:

A	Matrix.
cola	Column index.
colb	Column index.
start_row	Row index.
stop_row	Row index (exclusive).

static int mzd_slice_is_zero ( const mzd_slice_t * A ) [inline, static]

Zero test for matrix.

Parameters:

A	Input matrix.

Data Structures

Defines

Functions

Detailed Description

Define Documentation

Function Documentation