Matrices using a bitsliced representation. More...

#include <m4ri/m4ri.h>
#include <m4rie/mzd_poly.h>
#include <m4rie/mzed.h>
#include <m4rie/blm.h>

Data Structures
struct	mzd_slice_t
	Dense matrices over \(\mathbb{F}_{2^e}\) represented as slices of matrices over \(\mathbb{F}_2\). More...

Macros
#define	mzd_slice_sub mzd_slice_add
	\( C = A + B\). More...

#define	_mzd_slice_sub _mzd_slice_add
	\( C = A + B\). More...

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. More...

void	mzd_slice_set_ui (mzd_slice_t *A, word value)
	Return diagonal matrix with value on the diagonal. More...

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. More...

static void	mzd_slice_free (mzd_slice_t *A)
	Free a matrix created with mzd_slice_init(). More...

static mzd_slice_t *	mzd_slice_copy (mzd_slice_t B, const mzd_slice_t A)
	copy A to B More...

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. More...

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. More...

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. More...

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. More...

static int	mzd_slice_is_zero (const mzd_slice_t *A)
	Zero test for matrix. More...

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. More...

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. More...

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. More...

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. More...

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. More...

void	mzd_slice_print (const mzd_slice_t *A)
	Print a matrix to stdout. More...

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. More...

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. More...

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. More...

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. More...

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. More...

static void	mzd_slice_free_window (mzd_slice_t *A)
	Free a matrix window created with mzd_slice_init_window(). More...

static mzd_slice_t *	_mzd_slice_add (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A + B\). More...

static mzd_slice_t *	mzd_slice_add (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t *B)
	\( C = A + B\). More...

mzd_slice_t *	_mzd_slice_addmul_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. More...

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\). More...

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\). More...

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\). More...

static mzd_slice_t *	_mzd_slice_mul_blm (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t B, blm_t f)
	\( C = A \cdot B \) using bilinear maps over matrices over \(\mathbb{F}_2\). More...

static mzd_slice_t *	mzd_slice_mul_blm (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t B, blm_t f)
	\( C = A \cdot B \) using bilinear maps over matrices over \(\mathbb{F}_2\). More...

static mzd_slice_t *	mzd_slice_addmul_blm (mzd_slice_t C, const mzd_slice_t A, const mzd_slice_t B, blm_t f)
	\( C = C + A \cdot B \) using bilinear maps over matrices over \(\mathbb{F}_2\). More...

mzd_slice_t *	mzd_slice_mul_scalar (mzd_slice_t C, const word a, const mzd_slice_t B)
	\( C = a \cdot B \). More...

mzd_slice_t *	mzd_slice_addmul_scalar (mzd_slice_t C, const word a, const mzd_slice_t B)
	\( C += a \cdot B \). More...

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 \). More...

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 \). More...

static void	mzd_slice_randomize (mzd_slice_t *A)
	Fill matrix A with random elements. More...

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

Function Documentation

static mzd_slice_t* _mzd_slice_adapt_depth	(	mzd_slice_t *	A,
		const unsigned int	new_depth
	)

inlinestatic

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
	)

inlinestatic

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
	)

inlinestatic

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
	)

inlinestatic

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 )

inlinestatic

Zero test for matrix.

Parameters

A	Input matrix.

Data Structures

Macros

Functions

Detailed Description

Function Documentation