Detailed Description

In the MeatAxe, a matrix over a finite field is represented by a Matrix_t structure. Matrices can be created in many ways, for example

by calling MatAlloc(),
by making a copy of an existing matrix with MatDup(), or
by reading a matrix from a data file with MatRead() or MatLoad().

The application is responsible for releasing matrices which are no longer needed. Matrices can consume large amounts of memory, so it always a good idea to delete a matrix as early as possible. There is only one possibility of deleting a matrix: calling MatFree().

Echelon form and pivot tables

A matrix A with entries (a_ij) is said to be in echelon form if the following conditions are satisfied:

Each row has a first non-zero element, called the pivot element. The pivot element may have any value except zero.
If a_ij is the pivot element of the i-th row, all elements below are zero, i.e., a_ik=0 for all k>i.

If a matrix is in echelon form, the column indexes of its pivot elements are called the pivot columns of the matrix. The list of all pivot columns is called the pivot table of the matrix.

The Matrix_t structure, which represents a matrix, has a PivotTable field which is used to store the pivot table. When different from 0, PivotTable is a pointer to an array of integers containing first the pivot columns and then the non-pivot columns. This means, the size of the array is always Noc: the first Nor elements contain the pivot columns and the remaining Noc-Nor elements contain the non-pivot columns in arbitrary order. Note that for a matrix in echelon form Nor is always less or equal to Noc.

Data Structures
class	Matrix_t
	A matrix over a finite field. More...

Functions
Matrix_t *	MatAdd (Matrix_t dest, const Matrix_t src)
	Sum of two matrices. More...

int	MatClean (Matrix_t mat, const Matrix_t sub)
	Clean a matrix. More...

int	MatCompare (const Matrix_t a, const Matrix_t b)
	Compare two matrices If the matrices are equal, the return value is 0. More...

int	MatCopyRegion (Matrix_t dest, int destrow, int destcol, const Matrix_t src, int row1, int col1, int nrows, int ncols)
	Copy a rectangular region of a matrix This function copies a rectangular region of src tp dest. More...

int	MatIsValid (const Matrix_t *mat)
	Check if the matrix is valid. More...

Matrix_t *	MatAlloc (int field, int nor, int noc)
	Create a new matrix. More...

PTR	MatGetPtr (const Matrix_t *mat, int row)
	Pointer to a row of a matrix. More...

void	Mat_DeletePivotTable (Matrix_t *mat)
	Delete the pivot table of a matrix. More...

int	MatFree (Matrix_t *mat)
	Delete a matrix. More...

Matrix_t *	MatCut (const Matrix_t *src, int row1, int col1, int nrows, int ncols)
	Cut a rectangle out of a matrix. More...

Matrix_t *	MatCutRows (const Matrix_t *src, int row1, int nrows)
	Copy a range of rows of a matrix. More...

Matrix_t *	MatDup (const Matrix_t *src)
	Duplicate a matrix This function creates a copy of an existing matrix. More...

int	MatEchelonize (Matrix_t *mat)
	Reduce to echelon form This function performs a Gaussian elimination on the matrix \|mat\|. More...

long	MatNullity (const Matrix_t *mat)
	Nullity of a matrix. More...

long	MatNullity__ (Matrix_t *mat)
	Nullity of a matrix. More...

Matrix_t *	MatId (int fl, int nor)
	Identity matrix This function creates an identity matrix with nor nows over GF(fl). More...

Matrix_t *	MatInsert_ (Matrix_t mat, const Poly_t pol)
	Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field, this functions calculates p(A). More...

Matrix_t *	MatInsert (const Matrix_t mat, const Poly_t pol)
	Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field, this functions calculates p(A). More...

Matrix_t *	MatInverse (const Matrix_t *mat)
	Inverse of a matrix This function calculates the inverse of a matrix. More...

Matrix_t *	MatMul (Matrix_t dest, const Matrix_t src)
	Multiply matrices This function multiplies dest from the right by src. More...

Matrix_t *	MatNullSpace_ (Matrix_t *mat, int flags)
	Null-space of a matrix This function calculates the null-space of a matrix. More...

Matrix_t *	MatNullSpace (const Matrix_t *mat)
	Null-space of a matrix This function calculates the null-space of a matrix. More...

Matrix_t *	MatNullSpace__ (Matrix_t *mat)
	Null-space of a matrix This function calculates the null-space of a matrix and deletes the original matrix. More...

int	MatOrder (const Matrix_t *mat)
	Order of a matrix. More...

int	MatPivotize (Matrix_t *mat)
	Reduce to echelon form. More...

void	MatPrint (const char name, const Matrix_t m)
	Print a Matrix on stdout. More...

Matrix_t *	MatPower (const Matrix_t *mat, long n)
	!section obj.mat Power of a matrix. More...

Matrix_t *	MatRead (FILE *f)
	Read a matrix from a file. More...

Matrix_t *	MatLoad (const char *fn)
	Read a matrix from a file. More...

Matrix_t *	MatTransposed (const Matrix_t *src)
	Transpose a matrix. More...

FEL	MatTrace (const Matrix_t *mat)
	Trace of a Matrix. More...

int	MatWrite (const Matrix_t mat, FILE f)
	Write a matrix to a file. More...

int	MatSave (const Matrix_t mat, const char fn)
	Write a matrix to a file. More...

Matrix_t *	MatMulScalar (Matrix_t *dest, FEL coeff)
	Multiply a Matrix by a Constant. More...

Matrix_t *	MatMulStrassen (Matrix_t dest, const Matrix_t A, const Matrix_t *B)
	Multiply matrices. More...

Function Documentation

void Mat_DeletePivotTable ( Matrix_t * mat )

Delete the pivot table of a matrix.

This function deletes the pivot table associated with a matrix. It is used internally, applications should never call this function directly.

Parameters

mat	Pointer to the matrix.

Matrix_t* MatAdd	(	Matrix_t *	dest,
		const Matrix_t *	src
	)

Sum of two matrices.

This function adds src to dest, overwriteing the previos value in dest. The matrices must be over the same field and have the same dimensions.

Returns: dest on success, 0 on error.

Matrix_t* MatAlloc	(	int	field,
		int	nor,
		int	noc
	)

Create a new matrix.

This function creates a new matrix with given dimensions over a given field.

Attention: To destroy a matrix, use MatFree(), not SysFree().

Parameters

field	Field order.
nor	Number of rows.
noc	Number of columns.

Returns: Pointer to the new matrix or 0 on error.

int MatClean	(	Matrix_t *	mat,
		const Matrix_t *	sub
	)

Clean a matrix.

This function "cleans" a matrix with a space, i.e., it adds suitable linear combinations of the rows in sub to the rows of mat such that all pivot columns in mat are zero. Both matrices must be over the same field and have the same number of colums. The second matrix, sub, must be in echelon form. The cleaned matrix is reduced to echelon form.

Returns: Rank of the cleaned matrix, or -1 on error.

int MatCompare	(	const Matrix_t *	a,
		const Matrix_t *	b
	)

Compare two matrices If the matrices are equal, the return value is 0.

Otherwise the return value is positive, if a is "greater" than b and negative, if a is "less" than b. The ordering matrices is defined as follows:

If the matrices are over different fields, the matrix over the smaller field is smaller.
Otherwise, if the matrices have different number of columns, the matrix with the smaller number of columns is smaller.
Otherwise, if the matrices have different number of rows, the matrix with the smaller number of rows is smaller.
Otherwise, the relation is determined by the return value of FfCmpRow() on the first row that is not equal in both matrices.

In case an error occurs, the return value is -1. But note that a return value of -1 does not necessarily mean that an error has occurred.

Parameters

a	First matrix.
b	Second matrix.

Returns: 0 if the matrices are equal, nonzero otherwise (see description), -2 on error.

int MatCopyRegion	(	Matrix_t *	dest,
		int	destrow,
		int	destcol,
		const Matrix_t *	src,
		int	row1,
		int	col1,
		int	nrows,
		int	ncols
	)

Copy a rectangular region of a matrix This function copies a rectangular region of src tp dest.

The source region is defined by its upper left corner and dimensions, the destination region is specified by its upper left corner and has the same dimensions. Both nrows and ncols can be given as -1. In this case the region extends up to the last row or last column, respectively. The two matrices must be over the same field. Both source and destination region must not exceed the matrices' dimensions. In particular, it is not possible to extend the destination matrix by using MatCopyRegion().

Parameters

dest	Pointer to the destination matrix.
destrow	Destination row.
destcol	Destination column.
src	Pointer to the source matrix.
row1	First row in region.
col1	First column in region.
nrows	Number of rows to copy. -1 means as many rows as possible.
ncols	Number of columns to copy. -1 means as many columns as possible.

Returns: 0 on success, -1 on error.

Matrix_t* MatCut	(	const Matrix_t *	src,
		int	row1,
		int	col1,
		int	nrows,
		int	ncols
	)

Cut a rectangle out of a matrix.

This function creates a new matrix containing a copy of a rectangular region of the source matrix. The region, defined by row1, col1, nrows and ncols, must not exceed the matrix. However, both nrows and ncols may be -1. In this case the region extends up to the last row or last column, respectivly. For example, to extract the first 10 rows from a matrix independently of the number of columns, you could say

1 MatCut(mat,0,0,10,-1)

See also: MatCopyRegion MatCutRows

Parameters

src	Pointer to the matrix.
row1	First row in region.
col1	First column in region.
nrows	Number of rows to cut. -1 means as many rows as possible.
ncols	Number of columns to cut. -1 means as many columns as possible.

Returns: Pointer to a new matrix containing the specified region, or 0 on error.

Matrix_t* MatCutRows	(	const Matrix_t *	src,
		int	row1,
		int	nrows
	)

Copy a range of rows of a matrix.

This function creates a new matrix containing a range of consecutive rows of the source matrix. The range must now exceed the matrix's dimensions. However, nrows may be given as -1, meaning "up to the last row".

See also: MatCopyRegion MatCutRows

Parameters

src	Pointer to the matrix.
row1	First row in region.
nrows	Number of rows to cut. -1 means as many rows as possible.

Returns: A new matrix containing the specified rows of src, or 0 on error.

Matrix_t* MatDup ( const Matrix_t * src )

Duplicate a matrix This function creates a copy of an existing matrix.

The caller is responsible for destroying the copy with MatFree() when it is no longer needed.

Returns: A copy of the source Matrix, or 0 on error.

int MatEchelonize ( Matrix_t * mat )

Reduce to echelon form This function performs a Gaussian elimination on the matrix |mat|.

On return, |mat| is in semi echelon form and a pivot table has been attatched to the matrix. If the rank of |mat| was smaller than the number of rows, some rows are removed during the process. This function can also be used to rebuild the pivot table after the matrix has been modified.

Parameters

mat	Pointer to the matrix.

Returns: Rank of mat, or -1 on error.

int MatFree ( Matrix_t * mat )

Delete a matrix.

This function frees a matrix which has beed created by MatAlloc(). Freeing includes the internal data buffers as well as the Matrix_t structure itself.

Parameters

mat	Pointer to the matrix.

Returns: 0 on success, -1 on error.

PTR MatGetPtr	(	const Matrix_t *	mat,
		int	row
	)

Pointer to a row of a matrix.

This function returns a pointer to the specified row of a matrix. Row numbers start from 0. The current row size is not changed.

Parameters

mat	Pointer to the matrix.
row	Row index.

Returns: Pointer to the selected row or 0 on error.

Matrix_t* MatId	(	int	fl,
		int	nor
	)

Identity matrix This function creates an identity matrix with nor nows over GF(fl).

Parameters

fl	Field order.
nor	Number of rows.

Returns: Pointer to the matrix, or 0 on error.

See also: MatAlloc

Matrix_t* MatInsert	(	const Matrix_t *	mat,
		const Poly_t *	pol
	)

Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field, this functions calculates p(A).

Unlike MatInsert_() this function returns a new matrix and does not modify the original matrix.

Parameters

mat	Pointer to the matrix.
pol	Pointer to the polynomial.

Returns: pol(mat), or 0 on error.

Matrix_t* MatInsert_	(	Matrix_t *	mat,
		const Poly_t *	pol
	)

Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field, this functions calculates p(A).

Unlike MatInsert() this function is destructive. The result is stored in the original matrix and the old value is lost.

Parameters

mat	Pointer to the matrix.
pol	Pointer to the polynomial.

Returns: The function returns mat, or 0 on error.

Matrix_t* MatInverse ( const Matrix_t * mat )

Inverse of a matrix This function calculates the inverse of a matrix.

mat must be a non-singular square matrix. The inverse matrix is returned in a newly allocated Matrix_t structure, and the original matrix remains unchanged.

Parameters

mat	Pointer to the matrix.

Returns: Inverse matrix or 0 on error.

int MatIsValid ( const Matrix_t * mat )

Check if the matrix is valid.

This function checks if the argument is a pointer to a valid matrix. If the matrix is o.k., the function returns 1. Otherwise, an error is signalled and, if the error handler does not terminate the program, the function returns 0.

Parameters

mat	Matrix to check.

Returns: 1 if the matrix is valid, 0 otherwise.

Matrix_t* MatLoad ( const char * fn )

Read a matrix from a file.

!synopsis Matrix_t *MatLoad(const char *fn);

Parameters

fn	File name.

Returns: Pointer to the matrix, or |NULL| on error. !description This function opens a file, reads a single matrix, and closes the file.

To read more than one matrix from a file, use |MatRead()|.

See also: MatRead

Matrix_t* MatMul	(	Matrix_t *	dest,
		const Matrix_t *	src
	)

Multiply matrices This function multiplies dest from the right by src.

The matrices must be compatible for multiplication, i.e. they must be over the same field, and the number of columns of dest must be equal to the number of rows of src. The result of the multiplication is stored in dest, overwriting the original contents.

See also: MatPower()

Parameters

dest	Left factor and result.
src	Right factor.

Returns: The function returns dest, or 0 on error.

Matrix_t* MatMulScalar	(	Matrix_t *	dest,
		FEL	coeff
	)

Multiply a Matrix by a Constant.

Parameters

dest	Pointer to the matrix.
coeff	Value to multiply with.

Returns: The function returns dest, or NULL on error in debug mode only.

Matrix_t* MatMulStrassen	(	Matrix_t *	dest,
		const Matrix_t *	A,
		const Matrix_t *	B
	)

Multiply matrices.

This function multiplies A from the right by B and writes the result into dest. The matrices must be compatible for multiplication, i.e. they must be over the same field, and the number of columns of A must be equal to the number of rows of B. Moreover, it is assumed that dest is allocated in the right dimensions. Since parts of dest are used to store temporary results, it is essential that dest initially is zero!

See also: Strassen-Winograd multiplication

Parameters

[out]	dest	Result.
	A	Left factor.
	B	Right factor

Returns: Either dest, or NULL on error.

long MatNullity ( const Matrix_t * mat )

Nullity of a matrix.

This function calculates the dimension of the null-space of a matrix. Unlike MatNullity__() this function does not modify the matrix.

Parameters

mat	Pointer to the matrix.

Returns: Nullity of the matrix, or -1 on error.

long MatNullity__ ( Matrix_t * mat )

Nullity of a matrix.

This function calculates the dimension of the null-space of a matrix and deletes the matrix.

Parameters

mat	Pointer to the matrix.

Returns: Nullity of mat, or $-1$ on error.

Matrix_t* MatNullSpace ( const Matrix_t * mat )

Null-space of a matrix This function calculates the null-space of a matrix.

Unlike MatNullSpace_() and MatNullSpace__(), this function does not change the original matrix, but it allocates a temporary copy of the matrix and thus needs more memory.

Parameters

mat	Pointer to the matrix.

Returns: Pointer to the null-space, or 0 on error.

Matrix_t* MatNullSpace_	(	Matrix_t *	mat,
		int	flags
	)

Null-space of a matrix This function calculates the null-space of a matrix.

Unlike MatNullSpace(), this function modifies the orginal matrix, but uses less memory since no temporary workspace is allocated. The result is in echelon form.

Parameters

mat	Pointer to the matrix.
flags	If nonzero, the null-space is not reduced to echelon form.

Returns: Pointer to the null-space of |mat|, or |NULL| on error.

Matrix_t* MatNullSpace__ ( Matrix_t * mat )

Null-space of a matrix This function calculates the null-space of a matrix and deletes the original matrix.

See also: MatNullSpace_(), MatNullSpace()

Parameters

mat	Pointer to the matrix.

Returns: Pointer to the null-space, or 0 on error.

int MatOrder ( const Matrix_t * mat )

Order of a matrix.

This function calculates the order of a matrix. mat must be a non-singular, square matrix. Even if mat is non-singular, the function may fail. This happens if the order is greater than 1000000, or if the order on any cyclic subspace is greater than 1000.

Parameters

mat	Pointer to the matrix.

Returns: The order of mat, or -1 on error.

int MatPivotize ( Matrix_t * mat )

Reduce to echelon form.

This function builds the pivot table of a matrix. Unlike MatEchelonize() this function assumes that mat is already in echelon form.

Parameters

mat	Pointer to the matrix.

Returns: 0 on success, -1 on error.

Matrix_t* MatPower	(	const Matrix_t *	mat,
		long	n
	)

!section obj.mat Power of a matrix.

!synopsis Matrix_t *MatPower(const Matrix_t *mat, long n);

Parameters

mat	Pointer to the matrix.
n	Exponent.

Returns: |n|-th power of |mat|, or |NULL| on error. !description This function calculates the $n$-th power of a matrix, using the binary method. This method is generally faster than multiplying the matrix $n$ times by itself. On the other hand, a third matrix is temporarily created in addition to the original matrix and the result matrix. The cases $n=0$ and $n=1$ are handled separately, avoiding unnecessary memory allocation and calculation.

Negative exponents are not allowed. To calculate a negative power, you must first invert the matrix with |MatInverse()| and then call |MatPower()| with the inverted matrix and a positive exponent.

See also: MatMul MatInverse

void MatPrint	(	const char *	name,
		const Matrix_t *	m
	)

Print a Matrix on stdout.

This function prints a matrix on the standard output in readable form. If name is not 0, the name followed by an equal sign is printed before the matrix.

Parameters

name	Name to print before the matrix, or 0.
m	Pointer to the matrix.

Matrix_t* MatRead ( FILE * f )

Read a matrix from a file.

Parameters

f	File to read from.

Returns: Pointer to the matrix, or 0 on error.

int MatSave	(	const Matrix_t *	mat,
		const char *	fn
	)

Write a matrix to a file.

This function opens a file, writes a matrix to the file, and closes the file. If a file with the specified name already exists, the old contents of the file are destroyd. To write more than one matrix to a file, use MatWrite().

Parameters

mat	Pointer to the matrix.
fn	File name.

Returns: 0 on success, -1 on error.

FEL MatTrace ( const Matrix_t * mat )

Trace of a Matrix.

This function calculates the sum of all diagonal elements of a matrix. Note that the matrix need not be square.

Parameters

mat	Pointer to the matrix.

Returns: Trace of mat, 255 on error.

Matrix_t* MatTransposed ( const Matrix_t * src )

Transpose a matrix.

Parameters

src	Pointer to the matrix.

Returns: Pointer to the transposed matrix or 0 on error.

int MatWrite	(	const Matrix_t *	mat,
		FILE *	f
	)

Write a matrix to a file.

See also: MatSave

Parameters

mat	Pointer to the matrix.
f	Pointer to the file.

Returns: 0 on success, -1 on error.

Detailed Description

Echelon form and pivot tables

Data Structures

Functions

Function Documentation