This graph shows which files directly or indirectly include this file:

Classes
struct	csr_t

struct	int_pair

Macros
#define	SWAPINT(a, b) do{ int t=a; a=b; b=t; } while(0)

#define	ERROR(fmt, ...)

#define	SETWD(pos) ((pos)>>6)

#define	SETBT(pos) ((pos)&0x3F)

#define	TIMESWORDSIZE(w) ((w)<<6) /* wWORDSIZE /

#define	FIRSTBIT(x) __builtin_ctzll(x)

Functions
size_t	mzd_weight (const mzd_t *A)
	Compute the number of set bits (Hamming weight) in a dense matrix A.

size_t	mzd_weight_naive (const mzd_t *A)
	Naive implementation to compute the Hamming weight of a dense matrix A.

size_t	mzd_weight_row (const mzd_t *A, rci_t i)
	Compute the Hamming weight of a specific row in a dense matrix.

rci_t	mzd_gauss_naive (mzd_t M, mzp_t q, int full)
	Perform Gaussian elimination (naive) and return pivot column list.

int	csr_max_row_wght (const csr_t *const p)
	Get the maximum row weight of a CSR sparse matrix.

csr_t *	csr_transpose (csr_t dst, const csr_t const p)
	Transpose a compressed CSR sparse matrix.

mzd_t *	mzd_from_csr (mzd_t dst, const csr_t p)
	Convert a CSR sparse matrix to an MZD dense matrix.

mzd_t *	mzd_generator_from_csr (mzd_t G, const csr_t const H)
	Construct the generator matrix from a parity check matrix in CSR form.

mzd_t *	csr_mzd_mul (mzd_t C, const csr_t S, const mzd_t *B, int clear)
	Multiply a sparse matrix by a dense matrix.

mzd_t *	syndrome_vector (mzd_t syndrome, mzd_t row, csr_t *spaQ, int clear)
	Calculate syndrome vector change.

size_t	product_weight_csr_mzd (const csr_t A, const mzd_t B, int transpose)
	Compute the weight of the product of a sparse matrix and a dense matrix.

int	rand_uniform (const int max)
	Return a uniformly distributed random integer in the range [0, max-1].

mzp_t *	mzp_rand_len (mzp_t *q, rci_t length)
	Generate a random permutation of a given length in-place.

void	mzp_out (mzp_t const *p)
	Print the permutation to stdout.

mzp_t *	perm_p (mzp_t q, const mzp_t p, rci_t start)
	Apply pivot permutation p to permutation q in-place starting from index.

mzp_t *	perm_p_trans (mzp_t q, const mzp_t p, const rci_t start)
	Apply transposed pivot permutation p to permutation q in-place.

csr_t *	csr_free (csr_t *p)
	Free memory allocated for a CSR sparse matrix.

csr_t *	csr_init (csr_t *mat, int rows, int cols, int nzmax)
	Initialize or reallocate a CSR sparse matrix to target size.

void	csr_compress (csr_t *mat)
	Compress CSR matrix (sort indices and remove duplicates/zeros).

csr_t *	csr_from_pairs (csr_t mat, const int nz, int_pair const prs, const int nrows, const int ncols)
	Construct a CSR sparse matrix from an array of coordinate pairs.

void	csr_out (const csr_t *mat)
	Print raw contents of a CSR matrix to stdout.

void	csr_print (const csr_t *const smat, const char str[])
	Print a CSR matrix with a label string (formatted output).

csr_t *	csr_mm_read (char fin, csr_t mat, int transpose)
	Read a sparse matrix from a Matrix Market (.mtx) file into CSR format.

csr_t *	csr_apply_perm (csr_t dst, const csr_t const src, const mzp_t *const perm)
	Permute columns of a CSR sparse matrix.

int	csr_csr_mul_non_zero (const csr_t const A, const csr_t const B)
	Check if the product of two sparse matrices A * B^T is non-zero.

int	syndrome_bit_count (const mzd_t const row, const csr_t const spaQ)
	Compute the Hamming weight of the syndrome of a dense row vector against spaQ.

int	do_reduce (mzd_t row, const mzd_t matP0, const rci_t rankP0)
	Reduce a row vector against a matrix in standard form.

void	make_err (mzd_t *row, double p)
	Generate a random binary error vector with error probability p.

int	do_dist_clus (const csr_t const P, const mzd_t const G, int debug, int wmax, int start, const int rankG)
	(Internal) Run cluster distance algorithm on matrices.

csr_t *	Lx_for_CSS_code (const csr_t const Hx, const csr_t const Hz)
	Construct the logical matrix Lx for a quantum CSS code given Hx and Hz.

Macro Definition Documentation

◆ ERROR

#define ERROR	(	fmt,
		...
	)

Value:

  do{ \
    fprintf (stderr, "%s:%d: *** ERROR in function '%s()' ***\n", __FILE__, __LINE__, __FUNCTION__); \
    fprintf(stderr, " ␛[31;1m " fmt " ␛[0m\n",##__VA_ARGS__); \
    exit(-1); \
  } \
  while(0)

Definition at line 13 of file util_m4ri.h.

◆ FIRSTBIT

#define FIRSTBIT ( x ) __builtin_ctzll(x)

Definition at line 40 of file util_m4ri.h.

◆ SETBT

#define SETBT ( pos ) ((pos)&0x3F)

Definition at line 37 of file util_m4ri.h.

◆ SETWD

#define SETWD ( pos ) ((pos)>>6)

macros from nauty.h SETWD(pos) gives the setword in which pos is located SETBT(pos) gives the location of bit pos in a setword

Definition at line 36 of file util_m4ri.h.

◆ SWAPINT

#define SWAPINT	(	a,
		b
	)	do{ int t=a; a=b; b=t; } while(0)

Definition at line 11 of file util_m4ri.h.

◆ TIMESWORDSIZE

#define TIMESWORDSIZE ( w ) ((w)<<6) /* w*WORDSIZE */

Definition at line 38 of file util_m4ri.h.

Function Documentation

◆ csr_apply_perm()

csr_t * csr_apply_perm	(	csr_t *	dst,
		const csr_t *const	src,
		const mzp_t *const	perm
	)

Permute columns of a CSR sparse matrix.

Parameters

dst	Destination sparse matrix (can be NULL).
src	Source sparse matrix.
perm	Column permutation to apply.

Returns: Pointer to the permuted sparse matrix.

Permute columns of a CSR matrix with permutation perm.

Definition at line 736 of file util_m4ri.c.

References csr_t::cols, csr_compress(), csr_init(), ERROR, csr_t::i, csr_t::nz, csr_t::nzmax, csr_t::p, and csr_t::rows.

Referenced by Lx_for_CSS_code().

◆ csr_compress()

void csr_compress ( csr_t * mat )

Compress CSR matrix (sort indices and remove duplicates/zeros).

Compresses the representation of the sparse matrix and sorts column indices within each row to ensure consistency (critical for binary search / merging).

Parameters

mat	Pointer to the CSR matrix to compress in-place.

compress a CSR matrix

Definition at line 512 of file util_m4ri.c.

References int_pair::a, int_pair::b, ERROR, csr_t::i, csr_t::nz, csr_t::p, and csr_t::rows.

Referenced by csr_apply_perm(), csr_mm_read(), and csr_transpose().

◆ csr_csr_mul_non_zero()

int csr_csr_mul_non_zero	(	const csr_t *const	A,
		const csr_t *const	B
	)

Check if the product of two sparse matrices A * B^T is non-zero.

Parameters

A	First sparse matrix.
B	Second sparse matrix.

Returns: 1 if the product is non-zero (matrices are not orthogonal), 0 otherwise.

Definition at line 309 of file util_m4ri.c.

References csr_t::cols, ERROR, csr_t::i, csr_t::nz, csr_t::p, and csr_t::rows.

Referenced by var_init().

◆ csr_free()

csr_t * csr_free ( csr_t * p )

Free memory allocated for a CSR sparse matrix.

Parameters

p	Pointer to the CSR sparse matrix to free.

Returns: Always returns NULL.

kill a CSR matrix

Definition at line 459 of file util_m4ri.c.

References p.

Referenced by do_CC_dist(), Lx_for_CSS_code(), main(), var_init(), and var_kill().

◆ csr_from_pairs()

csr_t * csr_from_pairs	(	csr_t *	mat,
		const int	nz,
		int_pair *const	prs,
		const int	nrows,
		const int	ncols
	)

Construct a CSR sparse matrix from an array of coordinate pairs.

Parameters

mat	Destination CSR matrix (can be NULL).
nz	Number of coordinate pairs.
prs	Array of row-column index pairs.
nrows	Number of rows in the matrix.
ncols	Number of columns in the matrix.

Returns: Pointer to the constructed CSR matrix.

Definition at line 535 of file util_m4ri.c.

References int_pair::b, csr_init(), csr_t::i, csr_t::nz, and csr_t::p.

Referenced by read_dem_file().

◆ csr_init()

csr_t * csr_init	(	csr_t *	mat,
		int	rows,
		int	cols,
		int	nzmax
	)

Initialize or reallocate a CSR sparse matrix to target size.

Checks dimensions and nzmax of mat, reallocating arrays if they are too small.

Parameters

mat	Existing matrix structure (can be NULL, in which case it is allocated).
rows	Target number of rows.
cols	Target number of columns.
nzmax	Target capacity (number of non-zero entries).

Returns: Pointer to the initialized/reallocated CSR matrix.

initialize a CSR matrix check existing size and (re)allocate if needded

keep allocated mat

Definition at line 476 of file util_m4ri.c.

References csr_t::cols, ERROR, csr_t::i, csr_t::nz, csr_t::nzmax, csr_t::p, and csr_t::rows.

Referenced by csr_apply_perm(), csr_from_mzd(), csr_from_pairs(), csr_mm_read(), and csr_transpose().

◆ csr_max_row_wght()

int csr_max_row_wght ( const csr_t *const p )

Get the maximum row weight of a CSR sparse matrix.

Parameters

p	Pointer to the CSR sparse matrix.

Returns: Maximum row weight.

Get the maximum row weight of a CSR sparse matrix.

Definition at line 115 of file util_m4ri.c.

References p.

Referenced by do_CC_dist(), and main().

◆ csr_mm_read()

csr_t * csr_mm_read	(	char *	fin,
		csr_t *	mat,
		int	transpose
	)

Read a sparse matrix from a Matrix Market (.mtx) file into CSR format.

Parameters

fin	Path to the Matrix Market file.
mat	Destination CSR matrix (can be NULL).
transpose	Set to 1 to transpose the matrix while reading.

Returns: Pointer to the loaded CSR matrix.

read sparse matrix into a (binary) CSR (all entries default to 1) (re)allocate mat if needed use transpose=1 to transpose.

Definition at line 593 of file util_m4ri.c.

References csr_compress(), csr_init(), ERROR, csr_t::i, mm_is_coordinate, mm_is_general, mm_is_integer, mm_is_matrix, mm_is_pattern, mm_is_symmetric, mm_read_banner(), mm_read_mtx_array_size(), mm_read_mtx_crd_size(), mm_typecode_to_str(), csr_t::nz, and csr_t::p.

Referenced by var_init().

◆ csr_mzd_mul()

mzd_t * csr_mzd_mul	(	mzd_t *	C,
		const csr_t *	S,
		const mzd_t *	B,
		int	clear
	)

Multiply a sparse matrix by a dense matrix.

Computes C = S * B (if clear is 1) or C = C + S * B (if clear is 0).

Parameters

C	Destination dense matrix (can be NULL).
S	Source sparse matrix.
B	Source dense matrix.
clear	Flag to clear C before adding the product.

Returns: Pointer to the resulting dense matrix C.

sparse-S by dense B multiplication C=C+S*B; allocate C if needed.

Definition at line 224 of file util_m4ri.c.

References csr_t::cols, ERROR, csr_t::i, csr_t::p, and csr_t::rows.

◆ csr_out()

void csr_out ( const csr_t * mat )

Print raw contents of a CSR matrix to stdout.

Parameters

mat	Pointer to the CSR matrix.

output a CSR matrix

Definition at line 554 of file util_m4ri.c.

References csr_t::cols, csr_t::i, csr_t::nz, csr_t::nzmax, csr_t::p, and csr_t::rows.

◆ csr_print()

void csr_print	(	const csr_t *const	smat,
		const char	str[]
	)

Print a CSR matrix with a label string (formatted output).

Parameters

smat	Pointer to the CSR matrix.
str	Label/name of the matrix.

Definition at line 576 of file util_m4ri.c.

References mzd_from_csr().

Referenced by do_CC_dist(), and var_init().

◆ csr_transpose()

csr_t * csr_transpose	(	csr_t *	dst,
		const csr_t *const	p
	)

Transpose a compressed CSR sparse matrix.

Transposes matrix p and stores the result in dst. (Re)allocates dst if needed.

Parameters

dst	Destination sparse matrix (can be NULL, in which case it is allocated).
p	Source sparse matrix.

Returns: Pointer to the transposed sparse matrix (dst or newly allocated).

transpose compressed CSR matrix, (re) allocate if needed return resulting matrix TODO: add code for List of Pairs

Definition at line 133 of file util_m4ri.c.

References csr_t::cols, csr_compress(), csr_init(), ERROR, csr_t::i, csr_t::nz, csr_t::nzmax, p, csr_t::p, and csr_t::rows.

Referenced by do_CC_dist(), and main().

◆ do_dist_clus()

int do_dist_clus	(	const csr_t *const	P,
		const mzd_t *const	G,
		int	debug,
		int	wmax,
		int	start,
		const int	rankG
	)

(Internal) Run cluster distance algorithm on matrices.

◆ do_reduce()

int do_reduce	(	mzd_t *	row,
		const mzd_t *	matG0,
		const rci_t	rankG0
	)

Reduce a row vector against a matrix in standard form.

Checks if row is linearly dependent on the rows of matP0 (using rankP0 rows). Modifies row in place.

Parameters

row	Dense row vector to reduce (modified in place).
matP0	Dense matrix in standard form.
rankP0	Rank of matP0 (number of active rows).

Returns: 1 if row was reduced to zero (linearly dependent), 0 otherwise.

Check if row is linearly dependent with the rows of matG0 which is assumed to be in standard form. rankG0 is the number of non-zero rows in rankG0. return: -1 if empty line after simplification otherwise position of the first non-zero bit in the simplified vector

Definition at line 770 of file util_m4ri.c.

◆ Lx_for_CSS_code()

csr_t * Lx_for_CSS_code	(	const csr_t *const	Hx,
		const csr_t *const	Hz
	)

Construct the logical matrix Lx for a quantum CSS code given Hx and Hz.

Parameters

Hx	Sparse X-check matrix.
Hz	Sparse Z-check matrix (passed as Hz).

Returns: Pointer to the constructed sparse logical matrix Lx.

Construct the logical matrix Lx for a quantum CSS code given Hx and Hz.

Given a pair of binary CSS generator matrices in CSR format, Hx*Hz^T=0, compute a sparse matrix Lx s.t. Lx*Hz^T=0 and rows of Lx be linearly independent from those of Hx. TODO: see if sparsity of Lx can be improved.

permute columns to make std form [ I C ]

verify orthogonality

Definition at line 872 of file util_m4ri.c.

References csr_t::cols, csr_apply_perm(), csr_free(), csr_from_mzd(), ERROR, mzd_from_csr(), mzd_gauss_naive(), mzd_generator_from_csr(), perm_p(), perm_p_trans(), product_weight_csr_mzd(), and csr_t::rows.

Referenced by var_init().

◆ make_err()

void make_err	(	mzd_t *	row,
		double	p
	)

Generate a random binary error vector with error probability p.

Parameters

row	Dense row vector to store the error (modified in place).
p	Bit-flip probability.

Definition at line 808 of file util_m4ri.c.

References ERROR, and p.

◆ mzd_from_csr()

mzd_t * mzd_from_csr	(	mzd_t *	dst,
		const csr_t *	p
	)

Convert a CSR sparse matrix to an MZD dense matrix.

Parameters

dst	Destination dense matrix (can be NULL or must have correct dimensions).
p	Source sparse matrix.

Returns: Pointer to the dense matrix.

Convert CSR sparse binary matrix to MZD allocate dst if needed (must be correct size or NULL)

Definition at line 156 of file util_m4ri.c.

References ERROR, and p.

Referenced by csr_print(), do_RW_dist(), Lx_for_CSS_code(), mzd_generator_from_csr(), and product_weight_csr_mzd().

◆ mzd_gauss_naive()

rci_t mzd_gauss_naive	(	mzd_t *	M,
		mzp_t *	q,
		int	full
	)

Perform Gaussian elimination (naive) and return pivot column list.

Performs row reduction on M. If full is 1, performs full row reduction (RREF), otherwise only upper triangular. Stores the pivot column indices in q.

Parameters

M	Matrix to reduce (modified in place).
q	Permutation structure to store pivot columns.
full	Flag for full reduction (1) or triangular (0).

Returns: Rank of the matrix.

Copy of mzd_gauss_delayed from mzd.c (m4ri package) except additionally returns the list of pivot columns in second argument permutation q must be initialized!

Definition at line 74 of file util_m4ri.c.

Referenced by Lx_for_CSS_code(), and mzd_generator_from_csr().

◆ mzd_generator_from_csr()

mzd_t * mzd_generator_from_csr	(	mzd_t *	G,
		const csr_t *const	H
	)

Construct the generator matrix from a parity check matrix in CSR form.

Permutes columns of H to bring it to standard form [ I C ], computes the generator matrix G = [ C^T I ], and permutes columns of G back to align with the original H.

Parameters

G	Destination dense matrix for generator (can be NULL).
H	Parity check matrix in CSR format.

Returns: Pointer to the generator matrix G.

Convert a sparse binary matrix CSR into a standard form [ I C ], with some col permutations if needed, create the dense generator [ CT I ], and permute the cols back.
(re)allocate G if needed.

Definition at line 183 of file util_m4ri.c.

References csr_t::cols, params_t::debug, mzd_from_csr(), mzd_gauss_naive(), mzp_out(), and prm.

Referenced by Lx_for_CSS_code().

◆ mzd_weight()

size_t mzd_weight ( const mzd_t * A )

Compute the number of set bits (Hamming weight) in a dense matrix A.

Parameters

A	Pointer to the dense matrix.

Returns: Hamming weight of the matrix.

Definition at line 44 of file util_m4ri.c.

Referenced by csr_from_mzd(), and product_weight_csr_mzd().

◆ mzd_weight_naive()

size_t mzd_weight_naive ( const mzd_t * A )

Naive implementation to compute the Hamming weight of a dense matrix A.

Parameters

A	Pointer to the dense matrix.

Returns: Hamming weight of the matrix.

Definition at line 16 of file util_m4ri.c.

◆ mzd_weight_row()

size_t mzd_weight_row	(	const mzd_t *	A,
		rci_t	i
	)

Compute the Hamming weight of a specific row in a dense matrix.

Parameters

A	Pointer to the dense matrix.
i	Index of the row.

Returns: Hamming weight of row i.

Definition at line 25 of file util_m4ri.c.

◆ mzp_out()

void mzp_out ( mzp_t const * p )

Print the permutation to stdout.

Parameters

p	Pointer to the permutation structure.

print out the permutation (only needed under windows)

Definition at line 412 of file util_m4ri.c.

References p.

Referenced by mzd_generator_from_csr().

◆ mzp_rand_len()

mzp_t * mzp_rand_len	(	mzp_t *	q,
		rci_t	length
	)

Generate a random permutation of a given length in-place.

Modifies the permutation q by randomizing the first 'length' positions. Uses LAPACK style pivot permutations.

Parameters

q	Permutation structure to modify.
length	Number of positions to permute.

Returns: Pointer to the modified permutation q.

replace pivot q with a random pivot smaller or equal length (second parameter); remaining positions in place, *** note: LAPACK style pivot permutations! *** return pointer to q. input: perm – existing permutation

Definition at line 396 of file util_m4ri.c.

References ERROR, and rand_uniform().

◆ perm_p()

mzp_t * perm_p	(	mzp_t *	q,
		const mzp_t *	p,
		rci_t	start
	)

Apply pivot permutation p to permutation q in-place starting from index.

Parameters

q	Destination permutation (initialized to identity if NULL).
p	Source pivot permutation.
start	Index to start applying the permutation from.

Returns: Pointer to the updated permutation q.

apply pivot p to permutation q in place from start; initialize q to identity permutation if NULL return q

Definition at line 424 of file util_m4ri.c.

References ERROR, p, and SWAPINT.

Referenced by Lx_for_CSS_code().

◆ perm_p_trans()

mzp_t * perm_p_trans	(	mzp_t *	q,
		const mzp_t *	p,
		const rci_t	start
	)

Apply transposed pivot permutation p to permutation q in-place.

Parameters

q	Destination permutation (initialized to identity if NULL).
p	Source pivot permutation.
start	Index to start applying the permutation from.

Returns: Pointer to the updated permutation q.

apply pivot p (transposed) to permutation q in place from start; initialize q to identity permutation if NULL return q

Definition at line 442 of file util_m4ri.c.

References ERROR, p, and SWAPINT.

Referenced by do_RW_dist(), and Lx_for_CSS_code().

◆ product_weight_csr_mzd()

size_t product_weight_csr_mzd	(	const csr_t *	A,
		const mzd_t *	B,
		int	transpose
	)

Compute the weight of the product of a sparse matrix and a dense matrix.

Computes Hamming weight of A * B (if transpose is 0) or A * B^T (if transpose is 1).

Parameters

A	Source sparse matrix.
B	Source dense matrix.
transpose	Flag to transpose B.

Returns: Hamming weight of the product.

helper function to compute the weight of the product A*B (transpose == 0) or A*B^T (transpose == 1) with A sparse, B dense binary matrices

Definition at line 356 of file util_m4ri.c.

References mzd_from_csr(), and mzd_weight().

Referenced by Lx_for_CSS_code().

◆ rand_uniform()

int rand_uniform ( const int max )

Return a uniformly distributed random integer in the range [0, max-1].

Parameters

max	Upper bound (exclusive).

Returns: Random integer.

return uniformly distributed random number in the range [0,...,max-1]

Definition at line 376 of file util_m4ri.c.

Referenced by mzp_rand_len().

◆ syndrome_bit_count()

int syndrome_bit_count	(	const mzd_t *const	row,
		const csr_t *const	spaQ
	)

Compute the Hamming weight of the syndrome of a dense row vector against spaQ.

Parameters

row	Dense row vector (1 row).
spaQ	Sparse check matrix.

Returns: Hamming weight of the syndrome.

just check whether syndrome is zero or not

Definition at line 333 of file util_m4ri.c.

References csr_t::i, csr_t::p, and csr_t::rows.

◆ syndrome_vector()

mzd_t * syndrome_vector	(	mzd_t *	syndrome,
		mzd_t *	row,
		csr_t *	spaQ,
		int	clear
	)

Calculate syndrome vector change.

Computes syndrome = syndrome + row * spaQ (or sets it if clear is 1).

Parameters

syndrome	Destination syndrome vector.
row	Error vector (dense, 1 row).
spaQ	Sparse check matrix.
clear	Flag to clear syndrome before accumulation.

Returns: Pointer to the updated syndrome vector.

Calculate the syndrome vector change: syndrome=syndrome +row.spaQ optionally clear the destination

Definition at line 281 of file util_m4ri.c.

References csr_t::cols, ERROR, csr_t::i, csr_t::p, and csr_t::rows.

Classes

Macros

Functions

Macro Definition Documentation

◆ ERROR

◆ FIRSTBIT

◆ SETBT

◆ SETWD

◆ SWAPINT

◆ TIMESWORDSIZE

Function Documentation

◆ csr_apply_perm()

◆ csr_compress()

◆ csr_csr_mul_non_zero()

◆ csr_free()

◆ csr_from_pairs()

◆ csr_init()

◆ csr_max_row_wght()

◆ csr_mm_read()

◆ csr_mzd_mul()

◆ csr_out()

◆ csr_print()

◆ csr_transpose()

◆ do_dist_clus()

◆ do_reduce()

◆ Lx_for_CSS_code()

◆ make_err()

◆ mzd_from_csr()

◆ mzd_gauss_naive()

◆ mzd_generator_from_csr()

◆ mzd_weight()

◆ mzd_weight_naive()

◆ mzd_weight_row()

◆ mzp_out()

◆ mzp_rand_len()

◆ perm_p()

◆ perm_p_trans()

◆ product_weight_csr_mzd()

◆ rand_uniform()

◆ syndrome_bit_count()

◆ syndrome_vector()