M4RI
1.0.1
|
Dense matrices over GF(2) represented as a bit field. More...
#include <m4ri/m4ri_config.h>
#include <math.h>
#include <assert.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 |
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) |
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:] More... | |
static void | mzd_combine_weird (mzd_t *C, rci_t const c_row, mzd_t const *A, rci_t const a_row, mzd_t const *B, rci_t const b_row) |
c_row[c_startblock:] = a_row[a_startblock:] + b_row[b_startblock:] for different offsets More... | |
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 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 = 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 |
Dense matrices over GF(2) represented as a bit field.
#define __M4RI_MAX_MZD_BLOCKSIZE (((size_t)1) << 27) |
Maximum number of words allocated for one mzd_t block.
#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.
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.
A | Matrix |
#define mzd_sub mzd_add |
Same as mzd_add.
C | Preallocated difference matrix, may be NULL for automatic creation. |
A | Matrix |
B | Matrix |
Dense matrices over GF(2).
The most fundamental data type in this library.
Same as mzd_add but without any checks on the input.
C | Preallocated sum matrix, may be NULL for automatic creation. |
A | Matrix |
B | Matrix |
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).
A | Matrix |
res | Resolution of sampling (in words) |
r | Row to start counting |
c | Column to start counting |
Naive cubic matrix multiplication with the pre-transposed B.
That is, compute C such that C == AB^t.
C | Preallocated product matrix. |
A | Input matrix A. |
B | Pre-transposed input matrix B. |
clear | Whether to clear C before accumulating AB |
Matrix multiplication optimized for v*A where v is a vector.
C | Preallocated product matrix. |
v | Input matrix v. |
A | Input matrix A. |
clear | If set clear C first, otherwise add result to C. |
|
inlinestatic |
Swap the two rows rowa and rowb starting at startblock.
M | Matrix with a zero offset. |
rowa | Row index. |
rowb | Row index. |
startblock | Start swapping only in this block. |
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.
C | Preallocated sum matrix, may be NULL for automatic creation. |
A | Matrix |
B | Matrix |
Naive cubic matrix multiplication and addition.
That is, compute C such that C == C + AB.
C | Preallocated product matrix. |
A | Input matrix A. |
B | Input matrix B. |
|
inlinestatic |
AND n bits from values to M starting a position (x,y).
M | Source matrix. |
x | Starting row. |
y | Starting column. |
n | Number of bits (<= m4ri_radix); |
values | Word with values; |
|
inlinestatic |
Clear n bits in M starting a position (x,y).
M | Source matrix. |
x | Starting row. |
y | Starting column. |
n | Number of bits (0 < n <= m4ri_radix); |
Return -1,0,1 if if A < B, A == B or A > B respectively.
A | Matrix. |
B | Matrix. |
Swap the two columns cola and colb.
M | Matrix. |
cola | Column index. |
colb | Column index. |
|
inlinestatic |
Swap the two columns cola and colb but only between start_row and stop_row.
M | Matrix. |
cola | Column index. |
colb | Column index. |
start_row | Row index. |
stop_row | Row 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.
DST | destination matrix |
row3 | destination row for matrix dst |
startblock3 | starting block to work on in matrix dst |
SC1 | source matrix |
row1 | source row for matrix sc1 |
startblock1 | starting block to work on in matrix sc1 |
SC2 | source matrix |
startblock2 | starting block to work on in matrix sc2 |
row2 | source row for matrix sc2 |
|
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.
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 |
|
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.
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 |
|
inlinestatic |
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.
C | destination matrix |
c_row | destination row for matrix C |
A | source matrix |
a_row | source row for matrix A |
B | source matrix |
b_row | source row for matrix 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.
C | Matrix, may be NULL for automatic creation |
A | Matrix |
B | Matrix |
Copy matrix A to DST.
DST | May be NULL for automatic creation. |
A | Source matrix. |
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.
B | Target matrix. |
i | Target row index. |
A | Source matrix. |
j | Source row index. |
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).
A | Matrix |
res | Resolution of sampling (in words) |
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.
M | Matrix |
full | Gauss-Jordan style or upper triangular form only. |
Return TRUE if A == B.
A | Matrix |
B | Matrix |
Return lower triangular submatrix of A
L | Output matrix, if NULL a new matrix will be returned |
A | Source matrix |
Return upper triangular submatrix of A
U | Output matrix, if NULL a new matrix will be returned |
A | Source matrix |
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.
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 |
Get a pointer the first word.
M | Matrix |
Get a pointer to the first word in block n.
Use mzd_first_row for block number 0.
M | Matrix |
n | The block number. Must be larger than 0. |
Return the first row with all zero entries.
If no such row can be found returns nrows.
A | Matrix |
void mzd_free | ( | mzd_t * | A) |
Free a matrix created with mzd_init.
A | Matrix |
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.
M | Matrix |
startcol | First column to consider for reduction. |
full | Gauss-Jordan style or upper triangular form only. |
Return hash value for matrix.
A | Matrix |
Create a new matrix of dimension r x c.
Use mzd_free to kill it.
r | Number of rows |
c | Number of columns |
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.
M | Matrix |
lowr | Starting row (inclusive) |
lowc | Starting column (inclusive) |
highr | End row (exclusive) |
highc | End column (exclusive) |
|
inlinestatic |
Create a const window/view into a const matrix M.
See mzd_init_window, but for constant M.
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.
INV | Preallocated space for inversion matrix, may be NULL for automatic creation. |
A | Matrix to be reduced. |
I | Identity matrix. |
|
inlinestatic |
Test if a matrix is windowed.
M | Matrix |
int mzd_is_zero | ( | mzd_t const * | A) |
Zero test for matrix.
A | Input matrix. |
Naive cubic matrix multiplication.
That is, compute C such that C == AB.
C | Preallocated product matrix, may be NULL for automatic creation. |
A | Input matrix A. |
B | Input matrix B. |
|
inlinestatic |
Test if this mzd_t should free blocks.
M | Matrix |
void mzd_randomize | ( | mzd_t * | M) |
Fill matrix M with uniformly distributed bits.
M | Matrix |
Read the bit at position M[row,col].
M | Matrix |
row | Row index |
col | Column index |
|
inlinestatic |
Get n bits starting a position (x,y) from the matrix M.
M | Source matrix. |
x | Starting row. |
y | Starting column. |
n | Number of bits (<= m4ri_radix); |
|
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).
Number of rows in this block including r.
M | Matrix |
rci_t | row |
Get pointer to first word of row.
M | Matrix |
row | The row index. |
Add the rows sourcerow and destrow and stores the total in the row destrow.
M | Matrix |
sourcerow | Index of source row |
destrow | Index of target row |
|
inlinestatic |
Add the rows sourcerow and destrow and stores the total in the row destrow, but only begins at the column coloffset.
M | Matrix |
dstrow | Index of target row |
srcrow | Index of source row |
coloffset | Start column (0 <= coloffset < M->ncols) |
Clear the given row, but only begins at the column coloffset.
M | Matrix |
row | Index of row |
coloffset | Column offset |
Swap the two rows rowa and rowb.
M | Matrix |
rowa | Row index. |
rowb | Row index. |
Convert row to blocks index.
M | Matrix. |
row | The row to convert. |
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.
M | Matrix |
n | The block number. |
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.
M | Matrix |
value | Either 0 or 1 |
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.
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.
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) |
Transpose a matrix.
This function uses the fact that:
[ A B ]T [AT CT] [ C D ] = [BT DT]
and thus rearranges the blocks recursively.
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
|
inlinestatic |
Write the bit value to position M[row,col].
M | Matrix |
row | Row index |
col | Column index |
value | Either 0 or 1 |