mzd.h File Reference

Dense matrices over GF(2) represented as a bit field. More...

#include <m4ri/m4ri_config.h>
#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <m4ri/misc.h>
#include <m4ri/debug_dump.h>

Go to the source code of this file.

Data Structures
struct	mzd_block_t
	Data containers containing the values packed into words. More...
struct	mzd_t
	Dense matrices over GF(2). More...

Macros
#define	__M4RI_MAX_MZD_BLOCKSIZE   (((size_t)1) << 27)
#define	__M4RI_MUL_BLOCKSIZE   MIN(((int)sqrt((double)(4 * __M4RI_CPU_L3_CACHE))) / 2, 2048)
	Matrix multiplication block-ing dimension. More...
#define	mzd_free_window   mzd_free
	Free a matrix window created with mzd_init_window. More...
#define	mzd_sub   mzd_add
	Same as mzd_add. More...
#define	_mzd_sub   _mzd_add
	Same as mzd_sub but without any checks on the input. More...

Typedefs
typedef struct mzd_t	mzd_t
	Dense matrices over GF(2). More...

Functions
static int	mzd_is_windowed (mzd_t const *M)
	Test if a matrix is windowed. More...
static int	mzd_owns_blocks (mzd_t const *M)
	Test if this mzd_t should free blocks. More...
static word *	mzd_first_row (mzd_t const *M)
	Get a pointer the first word. More...
static word *	mzd_first_row_next_block (mzd_t const *M, int n)
	Get a pointer to the first word in block n. More...
static int	mzd_row_to_block (mzd_t const *M, rci_t row)
	Convert row to blocks index. More...
static wi_t	mzd_rows_in_block (mzd_t const *M, int n)
	Total number of rows in this block. More...
static wi_t	mzd_remaining_rows_in_block (mzd_t const *M, rci_t r)
	Number of rows in this block including r. More...
static word *	mzd_row (mzd_t const *M, rci_t row)
	Get pointer to first word of row. More...
mzd_t *	mzd_init (rci_t const r, rci_t const c)
	Create a new matrix of dimension r x c. More...
void	mzd_free (mzd_t *A)
	Free a matrix created with mzd_init. More...
mzd_t *	mzd_init_window (mzd_t *M, rci_t const lowr, rci_t const lowc, rci_t const highr, rci_t const highc)
	Create a window/view into the matrix M. More...
static mzd_t const *	mzd_init_window_const (mzd_t const *M, rci_t const lowr, rci_t const lowc, rci_t const highr, rci_t const highc)
	Create a const window/view into a const matrix M. More...
static void	_mzd_row_swap (mzd_t *M, rci_t const rowa, rci_t const rowb, wi_t const startblock)
	Swap the two rows rowa and rowb starting at startblock. More...
static void	mzd_row_swap (mzd_t *M, rci_t const rowa, rci_t const rowb)
	Swap the two rows rowa and rowb. More...
void	mzd_copy_row (mzd_t *B, rci_t i, mzd_t const *A, rci_t j)
	copy row j from A to row i from B. More...
void	mzd_col_swap (mzd_t *M, rci_t const cola, rci_t const colb)
	Swap the two columns cola and colb. More...
static void	mzd_col_swap_in_rows (mzd_t *M, rci_t const cola, rci_t const colb, rci_t const start_row, rci_t const stop_row)
	Swap the two columns cola and colb but only between start_row and stop_row. More...
static BIT	mzd_read_bit (mzd_t const *M, rci_t const row, rci_t const col)
	Read the bit at position M[row,col]. More...
static void	mzd_write_bit (mzd_t *M, rci_t const row, rci_t const col, BIT const value)
	Write the bit value to position M[row,col]. More...
static void	mzd_xor_bits (mzd_t const *M, rci_t const x, rci_t const y, int const n, word values)
	XOR n bits from values to M starting a position (x,y). More...
static void	mzd_and_bits (mzd_t const *M, rci_t const x, rci_t const y, int const n, word values)
	AND n bits from values to M starting a position (x,y). More...
static void	mzd_clear_bits (mzd_t const *M, rci_t const x, rci_t const y, int const n)
	Clear n bits in M starting a position (x,y). More...
static void	mzd_row_add_offset (mzd_t *M, rci_t dstrow, rci_t srcrow, rci_t coloffset)
	Add the rows sourcerow and destrow and stores the total in the row destrow, but only begins at the column coloffset. More...
void	mzd_row_add (mzd_t *M, rci_t const sourcerow, rci_t const destrow)
	Add the rows sourcerow and destrow and stores the total in the row destrow. More...
mzd_t *	mzd_transpose (mzd_t *DST, mzd_t const *A)
	Transpose a matrix. More...
mzd_t *	mzd_mul_naive (mzd_t *C, mzd_t const *A, mzd_t const *B)
	Naive cubic matrix multiplication. More...
mzd_t *	mzd_addmul_naive (mzd_t *C, mzd_t const *A, mzd_t const *B)
	Naive cubic matrix multiplication and addition. More...
mzd_t *	_mzd_mul_naive (mzd_t *C, mzd_t const *A, mzd_t const *B, int const clear)
	Naive cubic matrix multiplication with the pre-transposed B. More...
mzd_t *	_mzd_mul_va (mzd_t *C, mzd_t const *v, mzd_t const *A, int const clear)
	Matrix multiplication optimized for v*A where v is a vector. More...
void	mzd_randomize (mzd_t *M)
	Fill matrix M with uniformly distributed bits. More...
void	mzd_set_ui (mzd_t *M, unsigned int const value)
	Set the matrix M to the value equivalent to the integer value provided. More...
rci_t	mzd_gauss_delayed (mzd_t *M, rci_t const startcol, int const full)
	Gaussian elimination. More...
rci_t	mzd_echelonize_naive (mzd_t *M, int const full)
	Gaussian elimination. More...
int	mzd_equal (mzd_t const *A, mzd_t const *B)
	Return TRUE if A == B. More...
int	mzd_cmp (mzd_t const *A, mzd_t const *B)
	Return -1,0,1 if if A < B, A == B or A > B respectively. More...
mzd_t *	mzd_copy (mzd_t *DST, mzd_t const *A)
	Copy matrix A to DST. More...
mzd_t *	mzd_concat (mzd_t *C, mzd_t const *A, mzd_t const *B)
	Concatenate B to A and write the result to C. More...
mzd_t *	mzd_stack (mzd_t *C, mzd_t const *A, mzd_t const *B)
	Stack A on top of B and write the result to C. More...
mzd_t *	mzd_submatrix (mzd_t *S, mzd_t const *M, rci_t const lowr, rci_t const lowc, rci_t const highr, rci_t const highc)
	Copy a submatrix. More...
mzd_t *	mzd_invert_naive (mzd_t *INV, mzd_t const *A, mzd_t const *I)
	Invert the matrix target using Gaussian elimination. More...
mzd_t *	mzd_add (mzd_t *C, mzd_t const *A, mzd_t const *B)
	Set C = A+B. More...
mzd_t *	_mzd_add (mzd_t *C, mzd_t const *A, mzd_t const *B)
	Same as mzd_add but without any checks on the input. More...
static word	mzd_read_bits (mzd_t const *M, rci_t const x, rci_t const y, int const n)
static void	mzd_combine_even_in_place (mzd_t *A, rci_t const a_row, wi_t const a_startblock, mzd_t const *B, rci_t const b_row, wi_t const b_startblock)
	a_row[a_startblock:] += b_row[b_startblock:] for offset 0 More...
static void	mzd_combine_even (mzd_t *C, rci_t const c_row, wi_t const c_startblock, mzd_t const *A, rci_t const a_row, wi_t const a_startblock, mzd_t const *B, rci_t const b_row, wi_t const b_startblock)
	c_row[c_startblock:] = a_row[a_startblock:] + b_row[b_startblock:] for offset 0 More...
static void	mzd_combine (mzd_t *C, rci_t const c_row, wi_t const c_startblock, mzd_t const *A, rci_t const a_row, wi_t const a_startblock, mzd_t const *B, rci_t const b_row, wi_t const b_startblock)
	row3[col3:] = row1[col1:] + row2[col2:] More...
static int	mzd_read_bits_int (mzd_t const *M, rci_t const x, rci_t const y, int const n)
	Get n bits starting a position (x,y) from the matrix M. More...
int	mzd_is_zero (mzd_t const *A)
	Zero test for matrix. More...
void	mzd_row_clear_offset (mzd_t *M, rci_t const row, rci_t const coloffset)
	Clear the given row, but only begins at the column coloffset. More...
int	mzd_find_pivot (mzd_t const *M, rci_t start_row, rci_t start_col, rci_t *r, rci_t *c)
	Find the next nonzero entry in M starting at start_row and start_col. More...
double	mzd_density (mzd_t const *A, wi_t res)
	Return the number of nonzero entries divided by nrows * ncols. More...
double	_mzd_density (mzd_t const *A, wi_t res, rci_t r, rci_t c)
	Return the number of nonzero entries divided by nrows * ncols considering only the submatrix starting at (r,c). More...
rci_t	mzd_first_zero_row (mzd_t const *A)
	Return the first row with all zero entries. More...
static word	mzd_hash (mzd_t const *A)
	Return hash value for matrix. More...
mzd_t *	mzd_extract_u (mzd_t *U, mzd_t const *A)
mzd_t *	mzd_extract_l (mzd_t *L, mzd_t const *A)

Variables
static wi_t const	mzd_paddingwidth = 1
	The minimum width where padding occurs.
static uint8_t const	mzd_flag_nonzero_excess = 0x2
	flag when ncols%64 == 0
static uint8_t const	mzd_flag_windowed_zerooffset = 0x4
	flag for windowed matrix
static uint8_t const	mzd_flag_windowed_zeroexcess = 0x8
	flag for windowed matrix where ncols%64 == 0
static uint8_t const	mzd_flag_windowed_ownsblocks = 0x10
	flag for windowed matrix wich owns its memory
static uint8_t const	mzd_flag_multiple_blocks = 0x20
	flag for multiply blocks

Detailed Description

Dense matrices over GF(2) represented as a bit field.

Author

Gregory Bard bard@.nosp@m.ford.nosp@m.ham.e.nosp@m.du

Martin Albrecht marti.nosp@m.nral.nosp@m.brech.nosp@m.t+m4.nosp@m.ri@go.nosp@m.ogle.nosp@m.mail..nosp@m.com

Carlo Wood carlo.nosp@m.@ali.nosp@m.noe.c.nosp@m.om

Macro Definition Documentation

#define __M4RI_MAX_MZD_BLOCKSIZE   (((size_t)1) << 27)

Maximum number of words allocated for one mzd_t block.

Note

This value must fit in an int, even though it's type is size_t.

#define __M4RI_MUL_BLOCKSIZE   MIN(((int)sqrt((double)(4 * __M4RI_CPU_L3_CACHE))) / 2, 2048)

Matrix multiplication block-ing dimension.

Defines the number of rows of the matrix A that are processed as one block during the execution of a multiplication algorithm.

#define _mzd_sub   _mzd_add

Same as mzd_sub but without any checks on the input.

Parameters

C	Preallocated difference matrix, may be NULL for automatic creation.
A	Matrix
B	Matrix

#define mzd_free_window   mzd_free

Free a matrix window created with mzd_init_window.

Parameters

A

Matrix

#define mzd_sub   mzd_add

Same as mzd_add.

Parameters

C	Preallocated difference matrix, may be NULL for automatic creation.
A	Matrix
B	Matrix

Typedef Documentation

typedef struct mzd_t mzd_t

Dense matrices over GF(2).

The most fundamental data type in this library.

Function Documentation

mzd_t* _mzd_add	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B
	)

Same as mzd_add but without any checks on the input.

Parameters

C	Preallocated sum matrix, may be NULL for automatic creation.
A	Matrix
B	Matrix

double _mzd_density	(	mzd_t const *	A,
		wi_t	res,
		rci_t	r,
		rci_t	c
	)

Return the number of nonzero entries divided by nrows * ncols considering only the submatrix starting at (r,c).

If res = 0 then 100 samples per row are made, if res > 0 the function takes res sized steps within each row (res = 1 uses every word).

Parameters

A	Matrix
res	Resolution of sampling (in words)
r	Row to start counting
c	Column to start counting

mzd_t* _mzd_mul_naive	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B,
		int const	clear
	)

Naive cubic matrix multiplication with the pre-transposed B.

That is, compute C such that C == AB^t.

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Pre-transposed input matrix B.
clear	Whether to clear C before accumulating AB

mzd_t* _mzd_mul_va	(	mzd_t *	C,
		mzd_t const *	v,
		mzd_t const *	A,
		int const	clear
	)

Matrix multiplication optimized for v*A where v is a vector.

Parameters

C	Preallocated product matrix.
v	Input matrix v.
A	Input matrix A.
clear	If set clear C first, otherwise add result to C.

static void _mzd_row_swap ( mzd_t *  M, rci_t const  rowa, rci_t const  rowb, wi_t const  startblock  )

inlinestatic

Swap the two rows rowa and rowb starting at startblock.

Parameters

M	Matrix with a zero offset.
rowa	Row index.
rowb	Row index.
startblock	Start swapping only in this block.

mzd_t* mzd_add	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B
	)

Set C = A+B.

C is also returned. If C is NULL then a new matrix is created which must be freed by mzd_free.

Parameters

C	Preallocated sum matrix, may be NULL for automatic creation.
A	Matrix
B	Matrix

Examples:

testsuite/test_multiplication.c.

mzd_t* mzd_addmul_naive	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B
	)

Naive cubic matrix multiplication and addition.

That is, compute C such that C == C + AB.

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Input matrix B.

Note

Normally, if you will multiply several times by b, it is smarter to calculate bT yourself, and keep it, and then use the function called _mzd_mul_naive

static void mzd_and_bits ( mzd_t const *  M, rci_t const  x, rci_t const  y, int const  n, word  values  )

inlinestatic

AND n bits from values to M starting a position (x,y).

Parameters

M	Source matrix.
x	Starting row.
y	Starting column.
n	Number of bits (<= m4ri_radix);
values	Word with values;

static void mzd_clear_bits ( mzd_t const *  M, rci_t const  x, rci_t const  y, int const  n  )

inlinestatic

Clear n bits in M starting a position (x,y).

Parameters

M	Source matrix.
x	Starting row.
y	Starting column.
n	Number of bits (0 < n <= m4ri_radix);

Examples:

testsuite/bench_elimination.c.

int mzd_cmp	(	mzd_t const *	A,
		mzd_t const *	B
	)

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 mathematically and relatively arbitrary since elements of GF(2) don't have an ordering.

void mzd_col_swap	(	mzd_t *	M,
		rci_t const	cola,
		rci_t const	colb
	)

Swap the two columns cola and colb.

Parameters

M	Matrix.
cola	Column index.
colb	Column index.

static void mzd_col_swap_in_rows ( mzd_t *  M, rci_t const  cola, rci_t const  colb, rci_t const  start_row, rci_t const  stop_row  )

inlinestatic

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

Parameters

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

static void mzd_combine ( mzd_t *  C, rci_t const  c_row, wi_t const  c_startblock, mzd_t const *  A, rci_t const  a_row, wi_t const  a_startblock, mzd_t const *  B, rci_t const  b_row, wi_t const  b_startblock  )

inlinestatic

row3[col3:] = row1[col1:] + row2[col2:]

Adds row1 of SC1, starting with startblock1 to the end, to row2 of SC2, starting with startblock2 to the end. This gets stored in DST, in row3, starting with startblock3.

Parameters

C	destination matrix
c_row	destination row for matrix dst
c_startblock	starting block to work on in matrix dst
A	source matrix
a_row	source row for matrix sc1
a_startblock	starting block to work on in matrix sc1
B	source matrix
b_row	source row for matrix sc2
b_startblock	starting block to work on in matrix sc2

static void mzd_combine_even ( mzd_t *  C, rci_t const  c_row, wi_t const  c_startblock, mzd_t const *  A, rci_t const  a_row, wi_t const  a_startblock, mzd_t const *  B, rci_t const  b_row, wi_t const  b_startblock  )

inlinestatic

c_row[c_startblock:] = a_row[a_startblock:] + b_row[b_startblock:] for offset 0

Adds a_row of A, starting with a_startblock to the end, to b_row of B, starting with b_startblock to the end. This gets stored in C, in c_row, starting with c_startblock.

Parameters

C	destination matrix
c_row	destination row for matrix C
c_startblock	starting block to work on in matrix C
A	source matrix
a_row	source row for matrix A
a_startblock	starting block to work on in matrix A
B	source matrix
b_row	source row for matrix B
b_startblock	starting block to work on in matrix B

static void mzd_combine_even_in_place ( mzd_t *  A, rci_t const  a_row, wi_t const  a_startblock, mzd_t const *  B, rci_t const  b_row, wi_t const  b_startblock  )

inlinestatic

a_row[a_startblock:] += b_row[b_startblock:] for offset 0

Adds a_row of A, starting with a_startblock to the end, to b_row of B, starting with b_startblock to the end. This gets stored in A, in a_row, starting with a_startblock.

Parameters

A	destination matrix
a_row	destination row for matrix C
a_startblock	starting block to work on in matrix C
B	source matrix
b_row	source row for matrix B
b_startblock	starting block to work on in matrix B

mzd_t* mzd_concat	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B
	)

Concatenate B to A and write the result to C.

That is,

[ A ], [ B ] -> [ A  B ] = C

The inputs are not modified but a new matrix is created.

Parameters

C	Matrix, may be NULL for automatic creation
A	Matrix
B	Matrix

Note

This is sometimes called augment.

mzd_t* mzd_copy	(	mzd_t *	DST,
		mzd_t const *	A
	)

Copy matrix A to DST.

Parameters

DST	May be NULL for automatic creation.
A	Source matrix.

Examples:

testsuite/test_elimination.c, testsuite/test_multiplication.c, and testsuite/test_ple.c.

void mzd_copy_row	(	mzd_t *	B,
		rci_t	i,
		mzd_t const *	A,
		rci_t	j
	)

copy row j from A to row i from B.

The offsets of A and B must match and the number of columns of A must be less than or equal to the number of columns of B.

Parameters

B	Target matrix.
i	Target row index.
A	Source matrix.
j	Source row index.

double mzd_density	(	mzd_t const *	A,
		wi_t	res
	)

Return the number of nonzero entries divided by nrows * ncols.

If res = 0 then 100 samples per row are made, if res > 0 the function takes res sized steps within each row (res = 1 uses every word).

Parameters

A	Matrix
res	Resolution of sampling (in words)

rci_t mzd_echelonize_naive	(	mzd_t *	M,
		int const	full
	)

Gaussian elimination.

This will do Gaussian elimination on the matrix m. If full=FALSE, then it will do triangular style elimination, and if full=TRUE, it will do Gauss-Jordan style, or full elimination.

Parameters

M	Matrix
full	Gauss-Jordan style or upper triangular form only.

See also

mzd_echelonize_m4ri(), mzd_echelonize_pluq()

Examples:

testsuite/bench_elimination.c, and testsuite/test_elimination.c.

int mzd_equal	(	mzd_t const *	A,
		mzd_t const *	B
	)

Return TRUE if A == B.

Parameters

A	Matrix
B	Matrix

Examples:

testsuite/test_elimination.c, and testsuite/test_multiplication.c.

mzd_t* mzd_extract_l	(	mzd_t *	L,
		mzd_t const *	A
	)

Return lower triangular submatrix of A

Parameters

L	Output matrix, if NULL a new matrix will be returned
A	Source matrix

Returns

L

mzd_t* mzd_extract_u	(	mzd_t *	U,
		mzd_t const *	A
	)

Return upper triangular submatrix of A

Parameters

U	Output matrix, if NULL a new matrix will be returned
A	Source matrix

Returns

U

int mzd_find_pivot	(	mzd_t const *	M,
		rci_t	start_row,
		rci_t	start_col,
		rci_t *	r,
		rci_t *	c
	)

Find the next nonzero entry in M starting at start_row and start_col.

This function walks down rows in the inner loop and columns in the outer loop. If a nonzero entry is found this function returns 1 and zero otherwise.

If and only if a nonzero entry is found r and c are updated.

Parameters

M	Matrix
start_row	Index of row where to start search
start_col	Index of column where to start search
r	Row index updated if pivot is found
c	Column index updated if pivot is found

static word* mzd_first_row ( mzd_t const *  M )

inlinestatic

Get a pointer the first word.

Parameters

M

Matrix

Returns

a pointer to the first word of the first row.

static word* mzd_first_row_next_block ( mzd_t const *  M, int  n  )

inlinestatic

Get a pointer to the first word in block n.

Use mzd_first_row for block number 0.

Parameters

M	Matrix
n	The block number. Must be larger than 0.

Returns

a pointer to the first word of the first row in block n.

rci_t mzd_first_zero_row

(

mzd_t const *

A

)

Return the first row with all zero entries.

If no such row can be found returns nrows.

Parameters

A

Matrix

void mzd_free

(

mzd_t *

A

)

Free a matrix created with mzd_init.

Parameters

A

Matrix

Examples:

testsuite/bench_elimination.c, testsuite/test_elimination.c, testsuite/test_multiplication.c, and testsuite/test_ple.c.

rci_t mzd_gauss_delayed	(	mzd_t *	M,
		rci_t const	startcol,
		int const	full
	)

Gaussian elimination.

This will do Gaussian elimination on the matrix m but will start not at column 0 necc but at column startcol. If full=FALSE, then it will do triangular style elimination, and if full=TRUE, it will do Gauss-Jordan style, or full elimination.

Parameters

M	Matrix
startcol	First column to consider for reduction.
full	Gauss-Jordan style or upper triangular form only.

static word mzd_hash ( mzd_t const *  A )

inlinestatic

Return hash value for matrix.

Parameters

A

Matrix

mzd_t* mzd_init	(	rci_t const	r,
		rci_t const	c
	)

Create a new matrix of dimension r x c.

Use mzd_free to kill it.

Parameters

r	Number of rows
c	Number of columns

Examples:

testsuite/bench_elimination.c, testsuite/test_elimination.c, testsuite/test_multiplication.c, and testsuite/test_ple.c.

mzd_t* mzd_init_window	(	mzd_t *	M,
		rci_t const	lowr,
		rci_t const	lowc,
		rci_t const	highr,
		rci_t const	highc
	)

Create a window/view into the matrix M.

A matrix window for M is a meta structure on the matrix M. It is setup to point into the matrix so M must not be freed while the matrix window is used.

This function puts the restriction on the provided parameters that all parameters must be within range for M which is not enforced currently .

Use mzd_free_window to free the window.

Parameters

M	Matrix
lowr	Starting row (inclusive)
lowc	Starting column (inclusive, must be multiple of m4ri_radix)
highr	End row (exclusive)
highc	End column (exclusive)

static mzd_t const* mzd_init_window_const ( mzd_t const *  M, rci_t const  lowr, rci_t const  lowc, rci_t const  highr, rci_t const  highc  )

inlinestatic

Create a const window/view into a const matrix M.

See mzd_init_window, but for constant M.

mzd_t* mzd_invert_naive	(	mzd_t *	INV,
		mzd_t const *	A,
		mzd_t const *	I
	)

Invert the matrix target using Gaussian elimination.

To avoid recomputing the identity matrix over and over again, I may be passed in as identity parameter.

Parameters

INV	Preallocated space for inversion matrix, may be NULL for automatic creation.
A	Matrix to be reduced.
I	Identity matrix.

static int mzd_is_windowed ( mzd_t const *  M )

inlinestatic

Test if a matrix is windowed.

Parameters

M

Matrix

Returns

a non-zero value if the matrix is windowed, otherwise return zero.

int mzd_is_zero

(

mzd_t const *

A

)

Zero test for matrix.

Parameters

A	Input matrix.

mzd_t* mzd_mul_naive	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B
	)

Naive cubic matrix multiplication.

That is, compute C such that C == AB.

Parameters

C	Preallocated product matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

Note

Normally, if you will multiply several times by b, it is smarter to calculate bT yourself, and keep it, and then use the function called _mzd_mul_naive

Examples:

testsuite/test_multiplication.c.

static int mzd_owns_blocks ( mzd_t const *  M )

inlinestatic

Test if this mzd_t should free blocks.

Parameters

M

Matrix

Returns

TRUE iff blocks is non-zero and should be freed upon a call to mzd_free.

void mzd_randomize

(

mzd_t *

M

)

Fill matrix M with uniformly distributed bits.

Parameters

M

Matrix

Todo:

Allow the user to provide a RNG callback.

Examples:

testsuite/bench_elimination.c, testsuite/test_elimination.c, testsuite/test_multiplication.c, and testsuite/test_ple.c.

static BIT mzd_read_bit ( mzd_t const *  M, rci_t const  row, rci_t const  col  )

inlinestatic

Read the bit at position M[row,col].

Parameters

M	Matrix
row	Row index
col	Column index

Note

No bounds checks whatsoever are performed.

Examples:

testsuite/test_ple.c.

static word mzd_read_bits ( mzd_t const *  M, rci_t const  x, rci_t const  y, int const  n  )

inlinestatic

Get n bits starting a position (x,y) from the matrix M.

Parameters

M	Source matrix.
x	Starting row.
y	Starting column.
n	Number of bits (<= m4ri_radix);

static int mzd_read_bits_int ( mzd_t const *  M, rci_t const  x, rci_t const  y, int const  n  )

inlinestatic

Get n bits starting a position (x,y) from the matrix M.

This function is in principle the same as mzd_read_bits, but it explicitely returns an 'int' and is used as index into an array (Gray code).

static wi_t mzd_remaining_rows_in_block ( mzd_t const *  M, rci_t  r  )

inlinestatic

Number of rows in this block including r.

Parameters

M	Matrix
r	row

Returns

the number of rows with index >= r in this block

static word* mzd_row ( mzd_t const *  M, rci_t  row  )

inlinestatic

Get pointer to first word of row.

Parameters

M	Matrix
row	The row index.

Returns

pointer to first word of the row.

void mzd_row_add	(	mzd_t *	M,
		rci_t const	sourcerow,
		rci_t const	destrow
	)

Add the rows sourcerow and destrow and stores the total in the row destrow.

Parameters

M	Matrix
sourcerow	Index of source row
destrow	Index of target row

Note

this can be done much faster with mzd_combine.

static void mzd_row_add_offset ( mzd_t *  M, rci_t  dstrow, rci_t  srcrow, rci_t  coloffset  )

inlinestatic

Add the rows sourcerow and destrow and stores the total in the row destrow, but only begins at the column coloffset.

Parameters

M	Matrix
dstrow	Index of target row
srcrow	Index of source row
coloffset	Start column (0 <= coloffset < M->ncols)

Warning

This function expects that there is at least one word worth of work.

void mzd_row_clear_offset	(	mzd_t *	M,
		rci_t const	row,
		rci_t const	coloffset
	)

Clear the given row, but only begins at the column coloffset.

Parameters

M	Matrix
row	Index of row
coloffset	Column offset

static void mzd_row_swap ( mzd_t *  M, rci_t const  rowa, rci_t const  rowb  )

inlinestatic

Swap the two rows rowa and rowb.

Parameters

M	Matrix
rowa	Row index.
rowb	Row index.

static int mzd_row_to_block ( mzd_t const *  M, rci_t  row  )

inlinestatic

Convert row to blocks index.

Parameters

M	Matrix.
row	The row to convert.

Returns

the block number that contains this row.

static wi_t mzd_rows_in_block ( mzd_t const *  M, int  n  )

inlinestatic

Total number of rows in this block.

Should be called with a constant n=0, or with n > 0 when n is a variable, for optimization reasons.

Parameters

M	Matrix
n	The block number.

Returns

the total number of rows in this block.

void mzd_set_ui	(	mzd_t *	M,
		unsigned int const	value
	)

Set the matrix M to the value equivalent to the integer value provided.

Specifically, this function does nothing if value%2 == 0 and returns the identity matrix if value%2 == 1.

If the matrix is not square then the largest possible square submatrix is set to the identity matrix.

Parameters

M	Matrix
value	Either 0 or 1

mzd_t* mzd_stack	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B
	)

Stack A on top of B and write the result to C.

That is,

[ A ], [ B ] -> [ A ] = C
                [ B ]

The inputs are not modified but a new matrix is created.

Parameters

C	Matrix, may be NULL for automatic creation
A	Matrix
B	Matrix

mzd_t* mzd_submatrix	(	mzd_t *	S,
		mzd_t const *	M,
		rci_t const	lowr,
		rci_t const	lowc,
		rci_t const	highr,
		rci_t const	highc
	)

Copy a submatrix.

Note that the upper bounds are not included.

Parameters

S	Preallocated space for submatrix, may be NULL for automatic creation.
M	Matrix
lowr	start rows
lowc	start column
highr	stop row (this row is not included)
highc	stop column (this column is not included)

mzd_t* mzd_transpose	(	mzd_t *	DST,
		mzd_t const *	A
	)

Transpose a matrix.

This function uses the fact that:

   [ A B ]T    [AT CT]
   [ C D ]  =  [BT DT] 

and thus rearranges the blocks recursively.

Parameters

DST	Preallocated return matrix, may be NULL for automatic creation.
A	Matrix

it seems this is taken care of in the subroutines, re-enable if running into problems

static void mzd_write_bit ( mzd_t *  M, rci_t const  row, rci_t const  col, BIT const  value  )

inlinestatic

Write the bit value to position M[row,col].

Parameters

M	Matrix
row	Row index
col	Column index
value	Either 0 or 1

Note

No bounds checks whatsoever are performed.

Examples:

testsuite/bench_elimination.c, and testsuite/test_ple.c.

static void mzd_xor_bits ( mzd_t const *  M, rci_t const  x, rci_t const  y, int const  n, word  values  )

inlinestatic

XOR n bits from values to M starting a position (x,y).

Parameters

M	Source matrix.
x	Starting row.
y	Starting column.
n	Number of bits (<= m4ri_radix);
values	Word with values;