#include <m4ri/m4ri.h>
#include <m4ri/mzd.h>
#include <stdio.h>
#include <ctype.h>
#include "mmio.h"
#include "util_m4ri.h"

Include dependency graph for util_m4ri.c:

Functions
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 *const A, const rci_t i)
	Compute the Hamming weight of a specific row in a dense matrix.

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

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)
	return max row weight of CSR matrix p TODO: add code for List of Pairs

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.

void	addto (mzd_t row, const csr_t spaQ, const int i)

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

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.

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	do_reduce (mzd_t row, const mzd_t matG0, const rci_t rankG0)
	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.

csr_t *	csr_from_mzd (csr_t mat, const mzd_t const orig)
	convert `m4ri` dense matrix to `csr`

csr_t *	Lx_for_CSS_code (const csr_t const Hx, const csr_t const Hz)
	Compute logical generator matrix Lx for a CSS code.

Function Documentation

◆ addto()

void addto	(	mzd_t *	row,
		const csr_t *	spaQ,
		const int	i
	)

Add row=i of sparse matrix spaQ to row. no range check is done

Definition at line 247 of file util_m4ri.c.

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

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

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

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.

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_mzd()

csr_t * csr_from_mzd	(	csr_t *	mat,
		const mzd_t *const	orig
	)

convert m4ri dense matrix to csr

Optimized for sparse matrices.

Parameters

mat	pointer to existing matrix or NULL

will reallocate if needed

optimized version

Definition at line 837 of file util_m4ri.c.

References csr_init(), csr_t::i, mzd_weight(), csr_t::nz, csr_t::p, and csr_t::rows.

Referenced by Lx_for_CSS_code().

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

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 )

return max row weight of CSR matrix p TODO: add code for List of Pairs

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.

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.

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.

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.

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

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
	)

Compute logical generator matrix Lx for a CSS code.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

Functions

Function Documentation

◆ addto()

◆ csr_apply_perm()

◆ csr_compress()

◆ csr_csr_mul_non_zero()

◆ csr_free()

◆ csr_from_mzd()

◆ csr_from_pairs()

◆ csr_init()

◆ csr_max_row_wght()

◆ csr_mm_read()

◆ csr_mzd_mul()

◆ csr_out()

◆ csr_print()

◆ csr_transpose()

◆ 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()