M4RI  1.0.1
Data Structures | Defines | Typedefs | Functions | Variables
packedmatrix.h File Reference

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

#include "m4ri_config.h"
#include <math.h>
#include <assert.h>
#include <stdio.h>
#include <emmintrin.h>
#include "misc.h"
#include "debug_dump.h"

Go to the source code of this file.

Data Structures

struct  mzd_block_t
struct  mzd_t
 Dense matrices over GF(2). More...

Defines

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

Typedefs

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

Functions

static int mzd_is_windowed (mzd_t const *M)
 Test if a matrix is windowed.
static int mzd_owns_blocks (mzd_t const *M)
 Test if this mzd_t should free blocks.
static wordmzd_first_row (mzd_t const *M)
 Get a pointer the first word.
static wordmzd_first_row_next_block (mzd_t const *M, int n)
 Get a pointer to the first word in block n.
static int mzd_row_to_block (mzd_t const *M, rci_t row)
 Convert row to blocks index.
static wi_t mzd_rows_in_block (mzd_t const *M, int n)
 Total number of rows in this block.
static wordmzd_row (mzd_t const *M, rci_t row)
 Get pointer to first word of row.
mzd_tmzd_init (rci_t const r, rci_t const c)
 Create a new matrix of dimension r x c.
void mzd_free (mzd_t *A)
 Free a matrix created with mzd_init.
mzd_tmzd_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.
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.
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.
static void mzd_row_swap (mzd_t *M, rci_t const rowa, rci_t const rowb)
 Swap the two rows rowa and rowb.
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.
void mzd_col_swap (mzd_t *M, rci_t const cola, rci_t const colb)
 Swap the two columns cola and colb.
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.
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].
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].
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).
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).
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).
void mzd_print (mzd_t const *M)
 Print a matrix to stdout.
void mzd_print_tight (mzd_t const *M)
 Print the matrix to stdout.
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.
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.
mzd_tmzd_transpose (mzd_t *DST, mzd_t const *A)
 Transpose a matrix.
mzd_tmzd_mul_naive (mzd_t *C, mzd_t const *A, mzd_t const *B)
 Naive cubic matrix multiplication.
mzd_tmzd_addmul_naive (mzd_t *C, mzd_t const *A, mzd_t const *B)
 Naive cubic matrix multiplication and addition.
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.
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.
void mzd_randomize (mzd_t *M)
 Fill matrix M with uniformly distributed bits.
void mzd_set_ui (mzd_t *M, unsigned int const value)
 Set the matrix M to the value equivalent to the integer value provided.
rci_t mzd_gauss_delayed (mzd_t *M, rci_t const startcol, int const full)
 Gaussian elimination.
rci_t mzd_echelonize_naive (mzd_t *M, int const full)
 Gaussian elimination.
int mzd_equal (mzd_t const *A, mzd_t const *B)
 Return TRUE if A == B.
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.
mzd_tmzd_copy (mzd_t *DST, mzd_t const *A)
 Copy matrix A to DST.
mzd_tmzd_concat (mzd_t *C, mzd_t const *A, mzd_t const *B)
 Concatenate B to A and write the result to C.
mzd_tmzd_stack (mzd_t *C, mzd_t const *A, mzd_t const *B)
 Stack A on top of B and write the result to C.
mzd_tmzd_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.
mzd_tmzd_invert_naive (mzd_t *INV, mzd_t const *A, mzd_t const *I)
 Invert the matrix target using Gaussian elimination.
mzd_tmzd_add (mzd_t *C, mzd_t const *A, mzd_t const *B)
 Set C = A+B.
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.
static word mzd_read_bits (mzd_t const *M, rci_t const x, rci_t const y, int const n)
void mzd_combine (mzd_t *DST, rci_t const row3, wi_t const startblock3, mzd_t const *SC1, rci_t const row1, wi_t const startblock1, mzd_t const *SC2, rci_t const row2, wi_t const startblock2)
 row3[col3:] = row1[col1:] + row2[col2:]
static void mzd_combine_weird (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 different offsets
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
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
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.
int mzd_is_zero (mzd_t const *A)
 Zero test for matrix.
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.
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.
double mzd_density (mzd_t const *A, wi_t res)
 Return the number of nonzero entries divided by nrows * ncols.
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).
rci_t mzd_first_zero_row (mzd_t const *A)
 Return the first row with all zero entries.

Variables

static wi_t const mzd_paddingwidth = 3
 The minimum width where padding occurs.
static uint8_t const mzd_flag_nonzero_offset = 0x1
static uint8_t const mzd_flag_nonzero_excess = 0x2
static uint8_t const mzd_flag_windowed_zerooffset = 0x4
static uint8_t const mzd_flag_windowed_zeroexcess = 0x8
static uint8_t const mzd_flag_windowed_ownsblocks = 0x10
static uint8_t const mzd_flag_multiple_blocks = 0x20

Detailed Description

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

Author:
Gregory Bard <bard@fordham.edu>
Martin Albrecht <M.R.Albrecht@rhul.ac.uk>
Carlo Wood <carlo@alinoe.com>

Define 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_L2_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 __M4RI_SSE2_CUTOFF   10

SSE2 cutoff in words.

Cutoff in words after which row length SSE2 instructions should be used.

#define _mzd_sub   _mzd_add

Same as mzd_sub but without any checks on the input.

Parameters:
CPreallocated difference matrix, may be NULL for automatic creation.
AMatrix
BMatrix
Ignores offset atrtribute of packedmatrix.
#define mzd_free_window   mzd_free

Free a matrix window created with mzd_init_window.

Parameters:
AMatrix
#define mzd_sub   mzd_add

Same as mzd_add.

Parameters:
CPreallocated difference matrix, may be NULL for automatic creation.
AMatrix
BMatrix
Ignores offset atrtribute of packedmatrix.

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:
CPreallocated sum matrix, may be NULL for automatic creation.
AMatrix
BMatrix
Ignores offset atrtribute of packedmatrix.
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:
AMatrix
resResolution of sampling (in words)
rRow to start counting
cColumn 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:
CPreallocated product matrix.
AInput matrix A.
BPre-transposed input matrix B.
clearWhether 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:
CPreallocated product matrix.
vInput matrix v.
AInput matrix A.
clearIf 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 
) [inline, static]

Swap the two rows rowa and rowb starting at startblock.

Parameters:
MMatrix with a zero offset.
rowaRow index.
rowbRow index.
startblockStart 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:
CPreallocated sum matrix, may be NULL for automatic creation.
AMatrix
BMatrix
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:
CPreallocated product matrix.
AInput matrix A.
BInput 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 
) [inline, static]

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

Parameters:
MSource matrix.
xStarting row.
yStarting column.
nNumber of bits (<= m4ri_radix);
valuesWord with values;
static void mzd_clear_bits ( mzd_t const *  M,
rci_t const  x,
rci_t const  y,
int const  n 
) [inline, static]

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

Parameters:
MSource matrix.
xStarting row.
yStarting column.
nNumber of bits (0 < n <= m4ri_radix);
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:
AMatrix.
BMatrix.
Note:
This comparison is not well defined mathematically and relatively arbitrary since elements of GF(2) don't have an ordering.
Ignores offset atrtribute of packedmatrix.
void mzd_col_swap ( mzd_t M,
rci_t const  cola,
rci_t const  colb 
)

Swap the two columns cola and colb.

Parameters:
MMatrix.
colaColumn index.
colbColumn 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 
) [inline, static]

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

Parameters:
MMatrix.
colaColumn index.
colbColumn index.
start_rowRow index.
stop_rowRow index (exclusive).
void mzd_combine ( mzd_t DST,
rci_t const  row3,
wi_t const  startblock3,
mzd_t const *  SC1,
rci_t const  row1,
wi_t const  startblock1,
mzd_t const *  SC2,
rci_t const  row2,
wi_t const  startblock2 
)

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:
DSTdestination matrix
row3destination row for matrix dst
startblock3starting block to work on in matrix dst
SC1source matrix
row1source row for matrix sc1
startblock1starting block to work on in matrix sc1
SC2source matrix
startblock2starting block to work on in matrix sc2
row2source row for matrix sc2
Todo:
respect ncols at the end
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 
) [inline, static]

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:
Cdestination matrix
c_rowdestination row for matrix C
c_startblockstarting block to work on in matrix C
Asource matrix
a_rowsource row for matrix A
a_startblockstarting block to work on in matrix A
Bsource matrix
b_rowsource row for matrix B
b_startblockstarting block to work on in matrix B

check alignments

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 
) [inline, static]

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:
Adestination matrix
a_rowdestination row for matrix C
a_startblockstarting block to work on in matrix C
Bsource matrix
b_rowsource row for matrix B
b_startblockstarting block to work on in matrix B

check alignments

static void mzd_combine_weird ( 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 
) [inline, static]

c_row[c_startblock:] = a_row[a_startblock:] + b_row[b_startblock:] for different offsets

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:
Cdestination matrix
c_rowdestination row for matrix C
c_startblockstarting block to work on in matrix C
Asource matrix
a_rowsource row for matrix A
a_startblockstarting block to work on in matrix A
Bsource matrix
b_rowsource row for matrix B
b_startblockstarting 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:
CMatrix, may be NULL for automatic creation
AMatrix
BMatrix
Note:
This is sometimes called augment.
Ignores offset atrtribute of packedmatrix.
mzd_t* mzd_copy ( mzd_t DST,
mzd_t const *  A 
)

Copy matrix A to DST.

Parameters:
DSTMay be NULL for automatic creation.
ASource matrix.
Examples:
testsuite/test_elimination.c, testsuite/test_multiplication.c, and testsuite/test_pluq.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:
BTarget matrix.
iTarget row index.
ASource matrix.
jSource 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:
AMatrix
resResolution 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:
MMatrix
fullGauss-Jordan style or upper triangular form only.
Ignores offset atrtribute of packedmatrix.
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:
AMatrix
BMatrix
Ignores offset atrtribute of packedmatrix.
Examples:
testsuite/test_elimination.c, and testsuite/test_multiplication.c.
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:
MMatrix
start_rowIndex of row where to start search
start_colIndex of column where to start search
rRow index updated if pivot is found
cColumn index updated if pivot is found
static word* mzd_first_row ( mzd_t const *  M) [inline, static]

Get a pointer the first word.

Parameters:
MMatrix
Returns:
a pointer to the first word of the first row.
static word* mzd_first_row_next_block ( mzd_t const *  M,
int  n 
) [inline, static]

Get a pointer to the first word in block n.

Use mzd_first_row for block number 0.

Parameters:
MMatrix
nThe 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:
AMatrix
void mzd_free ( mzd_t A)

Free a matrix created with mzd_init.

Parameters:
AMatrix
Examples:
testsuite/bench_elimination.c, testsuite/test_elimination.c, testsuite/test_multiplication.c, and testsuite/test_pluq.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:
MMatrix
startcolFirst column to consider for reduction.
fullGauss-Jordan style or upper triangular form only.
Ignores offset atrtribute of packedmatrix.
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:
rNumber of rows
cNumber of columns
Examples:
testsuite/bench_elimination.c, testsuite/test_elimination.c, testsuite/test_multiplication.c, and testsuite/test_pluq.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:
MMatrix
lowrStarting row (inclusive)
lowcStarting column (inclusive)
highrEnd row (exclusive)
highcEnd 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 
) [inline, static]

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:
INVPreallocated space for inversion matrix, may be NULL for automatic creation.
AMatrix to be reduced.
IIdentity matrix.
Ignores offset atrtribute of packedmatrix.
static int mzd_is_windowed ( mzd_t const *  M) [inline, static]

Test if a matrix is windowed.

Parameters:
MMatrix
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:
AInput 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:
CPreallocated product matrix, may be NULL for automatic creation.
AInput matrix A.
BInput 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) [inline, static]

Test if this mzd_t should free blocks.

Parameters:
MMatrix
Returns:
TRUE iff blocks is non-zero and should be freed upon a call to mzd_free.
void mzd_print ( mzd_t const *  M)

Print a matrix to stdout.

The output will contain colons between every 4-th column.

Parameters:
MMatrix
void mzd_print_tight ( mzd_t const *  M)

Print the matrix to stdout.

Parameters:
MMatrix
void mzd_randomize ( mzd_t M)

Fill matrix M with uniformly distributed bits.

Parameters:
MMatrix
Todo:
Allow the user to provide a RNG callback.
Ignores offset atrtribute of packedmatrix.
Examples:
testsuite/bench_elimination.c, testsuite/test_elimination.c, testsuite/test_multiplication.c, and testsuite/test_pluq.c.
static BIT mzd_read_bit ( mzd_t const *  M,
rci_t const  row,
rci_t const  col 
) [inline, static]

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

Parameters:
MMatrix
rowRow index
colColumn index
Note:
No bounds checks whatsoever are performed.
Examples:
testsuite/test_pluq.c.
static word mzd_read_bits ( mzd_t const *  M,
rci_t const  x,
rci_t const  y,
int const  n 
) [inline, static]

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

Parameters:
MSource matrix.
xStarting row.
yStarting column.
nNumber 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 
) [inline, static]

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 word* mzd_row ( mzd_t const *  M,
rci_t  row 
) [inline, static]

Get pointer to first word of row.

Parameters:
MMatrix
rowThe 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:
MMatrix
sourcerowIndex of source row
destrowIndex 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 
) [inline, static]

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

Parameters:
MMatrix
dstrowIndex of target row
srcrowIndex of source row
coloffsetStart column (0 <= coloffset < M->ncols)
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:
MMatrix
rowIndex of row
coloffsetColumn offset
static void mzd_row_swap ( mzd_t M,
rci_t const  rowa,
rci_t const  rowb 
) [inline, static]

Swap the two rows rowa and rowb.

Parameters:
MMatrix
rowaRow index.
rowbRow index.
static int mzd_row_to_block ( mzd_t const *  M,
rci_t  row 
) [inline, static]

Convert row to blocks index.

Parameters:
MMatrix.
rowThe row to convert.
Returns:
the block number that contains this row.
static wi_t mzd_rows_in_block ( mzd_t const *  M,
int  n 
) [inline, static]

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:
MMatrix
nThe 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:
MMatrix
valueEither 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:
CMatrix, may be NULL for automatic creation
AMatrix
BMatrix
Ignores offset atrtribute of packedmatrix.
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:
SPreallocated space for submatrix, may be NULL for automatic creation.
MMatrix
lowrstart rows
lowcstart column
highrstop row (this row is not included)
highcstop 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:
DSTPreallocated return matrix, may be NULL for automatic creation.
AMatrix

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 
) [inline, static]

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

Parameters:
MMatrix
rowRow index
colColumn index
valueEither 0 or 1
Note:
No bounds checks whatsoever are performed.
Examples:
testsuite/bench_elimination.c, and testsuite/test_pluq.c.
static void mzd_xor_bits ( mzd_t const *  M,
rci_t const  x,
rci_t const  y,
int const  n,
word  values 
) [inline, static]

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

Parameters:
MSource matrix.
xStarting row.
yStarting column.
nNumber of bits (<= m4ri_radix);
valuesWord with values;