linear_algebra.c File Reference

#include "linear_algebra_internal.h"
#include "listmatrix.h"
#include "sort.h"
#include "env_internal.h"
#include <assert.h>
#include <stdint.h>
#include <limits.h>

Classes
struct	_RowInfo64

Typedefs
typedef struct _RowInfo64	RowInfo64

Functions
static int64_t	gcdExt (int64_t a, int64_t b, int64_t *ps, int64_t *pt)
	Computes the gcd of a and b along with the Bezout coefficients. More...
static int	compareOtherRows64 (const void *first, const void *second)
CMR_ERROR	CMRintmatComputeUpperDiagonal (CMR *cmr, CMR_INTMAT *matrix, bool invert, size_t *prank, CMR_SUBMAT **ppermutations, CMR_INTMAT **presult, CMR_INTMAT **ptranspose)
	Transforms matrix into a new matrix by applying integer row operations and row- and column swaps to find an upper-diagonal basis matrix. More...
CMR_ERROR	CMRintmatDeterminant (CMR *cmr, CMR_INTMAT *matrix, int64_t *pdeterminant)
	Computes the determinant of an int matrix. More...
CMR_ERROR	CMRchrmatDeterminant (CMR *cmr, CMR_CHRMAT *matrix, int64_t *pdeterminant)
	Computes the determinant of an 8-bit integer matrix. More...

Typedef Documentation

RowInfo64

typedef struct _RowInfo64 RowInfo64

Function Documentation

CMRchrmatDeterminant()

CMR_ERROR CMRchrmatDeterminant	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		int64_t *	pdeterminant
	)

Computes the determinant of an 8-bit integer matrix.

Parameters

cmr	CMR environment.
matrix	Matrix.
pdeterminant	Pointer for storing the determinant.

CMRintmatComputeUpperDiagonal()

CMR_ERROR CMRintmatComputeUpperDiagonal	(	CMR *	cmr,
		CMR_INTMAT *	matrix,
		bool	invert,
		size_t *	prank,
		CMR_SUBMAT **	ppermutations,
		CMR_INTMAT **	presult,
		CMR_INTMAT **	ptranspose
	)

Transforms matrix into a new matrix by applying integer row operations and row- and column swaps to find an upper-diagonal basis matrix.

The rank \( r \) is stored in *prank and the row- and column permutations are stored in *ppermutations, such that the first \( r \) rows and columns of the resulting matrix form an invertible upper-diagonal matrix. If invert is true then in this \( r \)-by- \( r \) submatrix, the largest (in terms of absolute value) entry in each column is on the diagonal.

Parameters

cmr	CMR environment.
matrix	A matrix
invert	Whether the transformed basis columns shall be strictly diagonally dominant.
prank	Pointer for storing the rank of the basis matrix.
ppermutations	Pointer for storing the row- and column permutations applied to matrix (may be NULL).
presult	Pointer for storing the resulting int matrix (may be NULL).
ptranspose	Pointer for storing the transpose of the result int matrix (may be NULL).

CMRintmatDeterminant()

CMR_ERROR CMRintmatDeterminant	(	CMR *	cmr,
		CMR_INTMAT *	matrix,
		int64_t *	pdeterminant
	)

Computes the determinant of an int matrix.

Parameters

cmr	CMR environment.
matrix	Matrix.
pdeterminant	Pointer for storing the determinant.

compareOtherRows64()

static int compareOtherRows64 ( const void *  first, const void *  second  )

static

gcdExt()

static int64_t gcdExt ( int64_t  a, int64_t  b, int64_t *  ps, int64_t *  pt  )

static

Computes the gcd of a and b along with the Bezout coefficients.

TODO: Implement (transposed) HNF according to

‘Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix’

Runs the extended Euclidean algorithm. For the gcd \( g \), we will have \( g = s a + t b. \). We are guaranteed to have \( t \neq 0 \).

Parameters

a	First number .
b	Second number.
ps	Pointer for storing the first Bezout coefficient.
pt	Pointer for storing the second Bezout coefficient.