mat.h File Reference

Matrix struct and operations. More...

Go to the source code of this file.

Data Structures
struct	cfe_mat

Typedefs
typedef struct cfe_mat	cfe_mat

Functions
void	cfe_mat_init (cfe_mat *m, size_t rows, size_t cols)
void	cfe_mat_inits (size_t rows, size_t cols, cfe_mat *m,...)
void	cfe_mat_set_const (cfe_mat *m, mpz_t c)
void	cfe_mat_copy (cfe_mat *res, cfe_mat *m)
void	cfe_mat_free (cfe_mat *m)
void	cfe_mat_frees (cfe_mat *m,...)
void	cfe_mat_print (cfe_mat *m)
void	cfe_mat_add (cfe_mat *res, cfe_mat *m1, cfe_mat *m2)
void	cfe_mat_neg (cfe_mat *res, cfe_mat *m)
void	cfe_mat_dot (mpz_t res, cfe_mat *m1, cfe_mat *m2)
void	cfe_mat_mod (cfe_mat *res, cfe_mat *m, mpz_t modulo)
void	cfe_mat_mul_vec (cfe_vec *res, cfe_mat *m, cfe_vec *v)
void	cfe_mat_mul (cfe_mat *res, cfe_mat *m1, cfe_mat *m2)
bool	cfe_mat_check_bound (cfe_mat *m, mpz_t bound)
void	cfe_mat_get (mpz_t res, cfe_mat *m, size_t i, size_t j)
void	cfe_mat_get_col (cfe_vec *res, cfe_mat *m, size_t i)
void	cfe_mat_get_row (cfe_vec *res, cfe_mat *m, size_t i)
cfe_vec *	cfe_mat_get_row_ptr (cfe_mat *m, size_t i)
void	cfe_mat_set (cfe_mat *m, mpz_t el, size_t i, size_t j)
void	cfe_mat_set_vec (cfe_mat *m, cfe_vec *v, size_t i)
void	cfe_mat_to_vec (cfe_vec *res, cfe_mat *m)
void	cfe_mat_from_vec (cfe_mat *m, cfe_vec *v)
void	cfe_mat_transpose (cfe_mat *t, cfe_mat *m)
void	cfe_mat_extract_submatrix (cfe_mat *m, cfe_mat *min, size_t i, size_t j)
void	cfe_mat_determinant (mpz_t det, cfe_mat *m)
cfe_error	cfe_mat_inverse_mod (cfe_mat *inverse_mat, cfe_mat *m, mpz_t mod)
void	cfe_mat_mul_x_mat_y (mpz_t res, cfe_mat *mat, cfe_vec *x, cfe_vec *y)
void	cfe_mat_mul_scalar (cfe_mat *res, cfe_mat *mat, mpz_t s)
void	cfe_mat_gaussian_elimination (cfe_mat *res, cfe_mat *mat, mpz_t p)
cfe_error	cfe_mat_inverse_mod_gauss (cfe_mat *res, mpz_t det, cfe_mat *m, mpz_t p)
void	cfe_mat_determinant_gauss (mpz_t det, cfe_mat *m, mpz_t p)
cfe_error	cfe_gaussian_elimination_solver (cfe_vec *res, cfe_mat *mat, cfe_vec *vec, mpz_t p)

Detailed Description

Matrix struct and operations.

As in GMP library, all functions except initialization functions presume that all of the parameters are properly initialized.

All functions (unless otherwise specified) store their results (either a GMP integer, a vector or a matrix) to a parameter and do not modify the original matrix. Thus, the "result" passed as a parameter must also be properly initialized.

Typedef Documentation

cfe_mat

typedef struct cfe_mat cfe_mat

Matrix of arbitrary precision (GMP) integers. It represents a row-major matrix. A matrix of dimensions i, j consists of i vectors, each consisting of j elements.

Function Documentation

cfe_mat_init()

void cfe_mat_init	(	cfe_mat *	m,
		size_t	rows,
		size_t	cols
	)

Initializes a matrix.

Parameters

m	A pointer to the uninitialized matrix
rows	The number of rows
cols	The number of columns

cfe_mat_inits()

void cfe_mat_inits	(	size_t	rows,
		size_t	cols,
		cfe_mat *	m,
			...
	)

Variadic version of cfe_mat_init. Initializes a NULL-terminated list of matrices.

cfe_mat_set_const()

void cfe_mat_set_const	(	cfe_mat *	m,
		mpz_t	c
	)

Sets all the entries of a matrix to equal the given constant.

Parameters

m	A pointer to an initialized matrix
c	The constant that the entries equal to

cfe_mat_copy()

void cfe_mat_copy	(	cfe_mat *	res,
		cfe_mat *	m
	)

Copies all the entries of a matrix to another matrix. The matrices must have equal dimensions.

Parameters

res	A pointer to an initialized matrix, matrix will be copied here
m	A pointer to the matrix that will be copied

cfe_mat_free()

void cfe_mat_free

(

cfe_mat *

m

)

Frees the memory occupied by the contents of the matrix.

cfe_mat_frees()

void cfe_mat_frees	(	cfe_mat *	m,
			...
	)

Variadic version of cfe_mat_free. Frees a NULL-terminated list of matrices.

cfe_mat_print()

void cfe_mat_print

(

cfe_mat *

m

)

Prints a matrix to standard output.

cfe_mat_add()

void cfe_mat_add	(	cfe_mat *	res,
		cfe_mat *	m1,
		cfe_mat *	m2
	)

Adds two matrices.

cfe_mat_neg()

void cfe_mat_neg	(	cfe_mat *	res,
		cfe_mat *	m
	)

Negative of a matrix.

cfe_mat_dot()

void cfe_mat_dot	(	mpz_t	res,
		cfe_mat *	m1,
		cfe_mat *	m2
	)

Calculates the dot (inner) product of matrices.

cfe_mat_mod()

void cfe_mat_mod	(	cfe_mat *	res,
		cfe_mat *	m,
		mpz_t	modulo
	)

Component-wise modulo.

cfe_mat_mul_vec()

void cfe_mat_mul_vec	(	cfe_vec *	res,
		cfe_mat *	m,
		cfe_vec *	v
	)

Multiplication of a matrix by a vector.

cfe_mat_mul()

void cfe_mat_mul	(	cfe_mat *	res,
		cfe_mat *	m1,
		cfe_mat *	m2
	)

Matrix multiplication.

cfe_mat_check_bound()

bool cfe_mat_check_bound	(	cfe_mat *	m,
		mpz_t	bound
	)

Checks if all elements are < bound.

Returns

false if any element is >= bound, true otherwise

cfe_mat_get()

void cfe_mat_get	(	mpz_t	res,
		cfe_mat *	m,
		size_t	i,
		size_t	j
	)

Sets res to the j-th element of the i-th row of the matrix.

cfe_mat_get_col()

void cfe_mat_get_col	(	cfe_vec *	res,
		cfe_mat *	m,
		size_t	i
	)

Sets res to the i-th column of the matrix.

cfe_mat_get_row()

void cfe_mat_get_row	(	cfe_vec *	res,
		cfe_mat *	m,
		size_t	i
	)

Sets res to the i-th row of the matrix.

cfe_mat_get_row_ptr()

cfe_vec* cfe_mat_get_row_ptr	(	cfe_mat *	m,
		size_t	i
	)

Returs the pointer to the i-th row of the matrix.

cfe_mat_set()

void cfe_mat_set	(	cfe_mat *	m,
		mpz_t	el,
		size_t	i,
		size_t	j
	)

Sets the j-th element of the i-th row of the matrix to el.

cfe_mat_set_vec()

void cfe_mat_set_vec	(	cfe_mat *	m,
		cfe_vec *	v,
		size_t	i
	)

Sets the i-th row of the matrix to v.

cfe_mat_to_vec()

void cfe_mat_to_vec	(	cfe_vec *	res,
		cfe_mat *	m
	)

Creates a vector from matrix elements by concatenating rows into a single vector.

cfe_mat_from_vec()

void cfe_mat_from_vec	(	cfe_mat *	m,
		cfe_vec *	v
	)

Constructs a matrix of dimensions rows * cols from v. The vector must hold exactly rows * cols elements.

cfe_mat_transpose()

void cfe_mat_transpose	(	cfe_mat *	t,
		cfe_mat *	m
	)

Transposes the matrix.

cfe_mat_extract_submatrix()

void cfe_mat_extract_submatrix	(	cfe_mat *	m,
		cfe_mat *	min,
		size_t	i,
		size_t	j
	)

Returns a matrix obtained from m by removing row i and column j. It returns an error if i >= number of rows of m, or if j >= number of columns of m.

cfe_mat_determinant()

void cfe_mat_determinant	(	mpz_t	det,
		cfe_mat *	m
	)

Determinant of a square matrix.

cfe_mat_inverse_mod()

cfe_error cfe_mat_inverse_mod	(	cfe_mat *	inverse_mat,
		cfe_mat *	m,
		mpz_t	mod
	)

Inverse of a matrix over a modular field Z_mod.

cfe_mat_mul_x_mat_y()

void cfe_mat_mul_x_mat_y	(	mpz_t	res,
		cfe_mat *	mat,
		cfe_vec *	x,
		cfe_vec *	y
	)

Calcualtes x^T * mat * y, for x, y vectors and mat a matrix.

cfe_mat_mul_scalar()

void cfe_mat_mul_scalar	(	cfe_mat *	res,
		cfe_mat *	mat,
		mpz_t	s
	)

Multiplication of a matrix mat and a scalar s.

cfe_mat_gaussian_elimination()

void cfe_mat_gaussian_elimination	(	cfe_mat *	res,
		cfe_mat *	mat,
		mpz_t	p
	)

cfe_gaussian_elimination transforms a matrix to an equivalent upper triangular matrix over field Z_p, where p should be a prime number.

Parameters

res	A pointer to an initialized matrix where the result will be saved
mat	A pointer to a matrix to be transformed
p	Modulus for the computations

cfe_mat_inverse_mod_gauss()

cfe_error cfe_mat_inverse_mod_gauss	(	cfe_mat *	res,
		mpz_t	det,
		cfe_mat *	m,
		mpz_t	p
	)

cfe_mat_inverse_mod_gauss calculates the inverse of a matrix over field Z_p, using Gaussian elimination. The latter is faster than the naive (analytic) algorithm. Additionally the determinant of the matrix is returned.

Parameters

res	A pointer to an initialized matrix where the result will be saved
det	Determinant will be saved here; if not needed this should be NULL
m	A pointer to a matrix
p	Modulus for the computations

cfe_mat_determinant_gauss()

void cfe_mat_determinant_gauss	(	mpz_t	det,
		cfe_mat *	m,
		mpz_t	p
	)

cfe_mat_determinant_gauss calculates the determinant of a matrix over field Z_p, using Gaussian elimination. The latter is faster than the naive (analytic) algorithm.

Parameters

det	The result will be saved
m	A pointer to a matrix
p	Modulus for the computations

cfe_gaussian_elimination_solver()

cfe_error cfe_gaussian_elimination_solver	(	cfe_vec *	res,
		cfe_mat *	mat,
		cfe_vec *	vec,
		mpz_t	p
	)

cfe_gaussian_elimination_solver solves a matrix vector equation mat * x = v and finds vector x, using Gaussian elimination. Arithmetic operations are considered to be over Z_p, where p should be a prime number. If such x does not exist, then the function returns an 1, else 0.

Parameters

res	A pointer to an uninitialized vector where the result will be saved
mat	A pointer to the matrix for the equation
vec	A pointer to the right-hand side vector in the equation
p	Modulus for the computations

Returns

Returns CFE_ERR_NO_SOLUTION_EXISTS error if the solution does not exist, else CFE_ERR_NONE for no error