Integer matrix implementation. Provides matrix algebra, cofactor, adjugate and inverse computation. More...

#include "Debug.nxc"

Include dependency graph for Matrix.nxc:

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

Data Structures
struct	Matrix
	The matrix class. Don't access the members directly. Use the macros MIJ() or MI() or the methods provided instead. More...

Macros
#define	MIJ(m, i, j) m.elements[(i) * m.cols + (j)]
	Gives direct access to an element in matrix m, at row i and col j. More...

#define	MI(m, i) m.elements[i]
	Gives direct one-dimentional access to an element in matrix m, at the index i. Index i is calculated as (row * cols + col). More...

Functions
void	MatrixInit (Matrix &matrix, int rows, int cols)
	Initializes a matrix to a matrix of size rows x cols and fills it with 0s.

void	MatrixInitElements (Matrix &matrix, int rows, int cols, long &elements[])
	Initializes a matrix to a matrix of size rows x cols and fills it with elements from given array. More...

void	MatrixInitIdentity (Matrix &matrix, int rows, int cols)
	Initializes a matrix to an Identity matrix of size rows x cols, with all elements except diagonal elements set to 0s and diagonal elements set to 1s.

void	MatrixInitDiagonal (Matrix &matrix, int rows, int cols, long value)
	Initializes a matrix to a diagonal matrix of size rows x cols, with all elements except diagonal elements set to 0s and diagonal elements set to given value.

long	MatrixGet (Matrix &matrix, int row, int col)
	Returns the value of element in matrix given by row x col. This is exactly same as macro MIJ(), but in functional form.

void	MatrixSet (Matrix &matrix, int row, int col, long value)
	Sets the given value to the element in matrix given by row x col. This is exactly same as assigning to macro MIJ(), but in functional form.

bool	MatrixCompare (Matrix &matrixA, Matrix &matrixB)
	Compares the two matrixes. A and B, and returns true if they are equal otherwise returns false. Equality involves each and every element being equal.

bool	MatrixIsNull (Matrix &matrix)
	Returns true if the matrix is NULL, i.e. all elemants are 0.

void	MatrixTranspose (Matrix &matrix)
	Converts the given matrix into its Transpose, i.e. the matrix is flipped along its diagonal (top-left to bottom-right).

long	MatrixMaxima (Matrix &matrix)
	Returns the largest value of 'absolute' values of elements in the matrix. It is useful to determine the 'scale' of the matrix.

long	MatrixMinima (Matrix &matrix)
	Returns the smallest value of 'absolute' values of elements in the matrix, discounting 0s. It is useful to determine the lower 'scale' of the matrix.

void	MatrixShiftLeft (Matrix &matrix, int numShift)
	Binary shifts all elements of the matrix right by the amount numShift.

void	MatrixShiftRight (Matrix &matrix, int numShift)
	Binary shifts all elements of the matrix left by the amount numShift.

void	MatrixAdd (Matrix &matrixA, Matrix &matrixB)
	Adds matrix B to matrix A. i.e. A += B.

void	MatrixSubtract (Matrix &matrixA, Matrix &matrixB)
	Subtracts matrix B from matrix A. i.e. A -= B.

void	MatrixMultiply (Matrix &matrixA, Matrix &matrixB, Matrix &matrixC)
	Multiplies matrix A with B and stores the result in matrix C. i.e. C = A * B. Matrix C must not be same variable as matrix A or B, because all of them are passed as reference.

void	MatrixScale (Matrix &matrix, long scale)
	Scales all elements in matrix A by given scale factor. i.e. A *= scale.

void	MatrixReduce (Matrix &matrix, long scale)
	Reduces (i.e. scales down) all elements in matrix A by given reduction factor. i.e. A /= scale.

void	MatrixMinor (Matrix &matrix, int minorI, int minorJ, Matrix &matrixM)
	Computes a minor matrix, designated Minor (i,j), for the given matrix and returns it in matrixM. i.e. M(i, j) = Minor of A(i, j). MatrixM must not be the same variable as matrix because they are passed as references.

long	MatrixDeterminant3 (Matrix &matrix)
	Direct diterminat computation for matrix <= 3x3 size. For larger size, see MatrixDiterminant() below.

long	MatrixCofactorIJ (Matrix &matrixIn, int i, int j)
	Computes and returns the cofactor of row i and col j of matrixIn. More...

void	MatrixCofactor (Matrix &matrix, Matrix &retCofactor)
	Finds the cofactor matrix of a given matrix. Cofactor matrix is a matrix with each element (i,j) set to cofactor of the matrix for (i,j).

long	MatrixDeterminant (Matrix &matrix)
	Finds the determinant of a matrix. For matrix smaller than 4x4, it is exactly same as MatrixDeterminant3(). More...

void	MatrixAdjugate (Matrix &matrix, Matrix &retAdjugate)
	Finds the adjugate (aka ajoint) of a matrix. Adjugate of a matrix is basically a transpose of its cofactor matrix.

void	MatrixPrint (Matrix &matrix, string title, int pauseSecs)
	Prints the matrix on screen with the given title and follows it with a wait of pauseSecs. Useful for debugging.

long	MatrixInverse (Matrix matrix, long precision, Matrix &retInverse)
	Finds the inverse of a matrix. The inverted matix is scalled by the returned scale factor. The given precision is the amount of desired scale factor within which all element values are fitted. More...

Detailed Description

Integer matrix implementation. Provides matrix algebra, cofactor, adjugate and inverse computation.

Definition in file Matrix.nxc.

Macro Definition Documentation

#define MI	(	m,
		i
	)	m.elements[i]

Gives direct one-dimentional access to an element in matrix m, at the index i. Index i is calculated as (row * cols + col).

This access is more efficient than 2D access with MIJ() because it skips index calculation (one multiply and one addition) and is useful if all elements need to be accessed during a matrix operation (e.g. during an addition). It can be used both as left-hand and right-hand operants, i.e. 'MI(m,i) = value' or 'variable = MI(m,i)'.

Definition at line 58 of file Matrix.nxc.

Referenced by MatrixAdd(), MatrixCompare(), MatrixDeterminant3(), MatrixIsNull(), MatrixMaxima(), MatrixMinima(), MatrixReduce(), MatrixScale(), MatrixShiftLeft(), MatrixShiftRight(), and MatrixSubtract().

#define MIJ	(	m,
		i,
		j
	)	m.elements[(i) * m.cols + (j)]

Gives direct access to an element in matrix m, at row i and col j.

It can be used both as left-hand and right-hand operants. It can be used both as left-hand and right-hand operants, i.e. 'MI(m,i) = value' or 'variable = MI(m,i)'.

Definition at line 45 of file Matrix.nxc.

Function Documentation

long MatrixCofactorIJ	(	Matrix &	matrixIn,
		int	i,
		int	j
	)

Computes and returns the cofactor of row i and col j of matrixIn.

It computes the cofactor at (i,j) by recursive method. Functional recursion is not possible with NXC so it is implemented using internal stack to emulate recursion using iterative method. It's very inefficient for matrix larger than 4x4 size. It's such a mess when there is no recursive support in NXC :(

Definition at line 366 of file Matrix.nxc.

References Matrix::cols, MatrixDeterminant3(), MatrixGet(), MatrixMinor(), and Matrix::rows.

Referenced by MatrixCofactor(), and MatrixDeterminant().

long MatrixDeterminant ( Matrix & matrix )

Finds the determinant of a matrix. For matrix smaller than 4x4, it is exactly same as MatrixDeterminant3().

The determinant is computed using recursive cofactor method (the least efficient method) for matrix larger than 3x3. so be aware of performance for large matrixes. For smaller matrix (i.e. size less than or equal to 3x3, it will invoke MatrixDeterminant3() anyways which uses direct computation.

Definition at line 485 of file Matrix.nxc.

References Matrix::cols, MatrixCofactorIJ(), MatrixDeterminant3(), MatrixGet(), and Matrix::rows.

Referenced by MatrixInverse().

void MatrixInitElements	(	Matrix &	matrix,
		int	rows,
		int	cols,
		long &	elements[]
	)

Initializes a matrix to a matrix of size rows x cols and fills it with elements from given array.

The array should contain rows * cols elemements and is accessed flatly with (i * rows + cols).

Definition at line 91 of file Matrix.nxc.

References Matrix::cols, Matrix::elements, Matrix::rows, and Matrix::size.

long MatrixInverse	(	Matrix	matrix,
		long	precision,
		Matrix &	retInverse
	)

Finds the inverse of a matrix. The inverted matix is scalled by the returned scale factor. The given precision is the amount of desired scale factor within which all element values are fitted.

The returned inverse matrix is scaled by a factor value return by the function to fit all integer values in the matrix within the precision provided. That is, if the precision provided is 1000, it will produce an inverse matrix with all it's elements' absolute values within 0 to 1000.

Use the returned 'scale' value to scale down the matrix at later appropriate time. This is done because inverse of integer matrix is always less than 1 and we need to maintain the level of precision for the inverse matrix to be meaningful. It's a cheap form of maintaining floating point numbers in integer matrix. Unlike other functions, it takes matrix as value (instead of reference), because it needs to modify it without affecting the original one. As a consequence, retInverse can be the same variable as input matrix.

Implementation detail: To avoid blowing up the matrix with integer overflow, the input matrix has to be scaled down depending on the size of the matrix The determinant of the matrix has maximum order of N times the order of it's largest element. So for example, if the largest item in a 4x4 matrix is 1000, the max determinant value will take, 1000,000,000,000 – Not an easy number to fit in a 32 bit integer :).

To tame the matrix down, we scale the input matix and limit the largest element to 2^(31/N) - 1. N is the order of the matrix, and the 31 comes from the fact that 32 bit integer can't hold value larger than 2^31. So, for 1x1 matrix, input can take full range of 2^31 - 1, 2x2 can take max 2^15 - 1, and so on.

Algorithm: The larget element is first searched and bit shifted until it falls in the acceptable dynamic range of that matrix. This amount of bit shifts is performed on all elements. Some smaller elements will fall off to 0 after the shift, but there is nothing we can do about that.

Then, to neutralize the input shifts, after the adjugate is computed, either the determinanat needs to be multiplied by 2^S or (adjugate) matrix elements need to be divided by 2^S, where S is the number of bits we shifted before.

We can't do the first, because we will lose all the precision in elements. We can'd do the later either because that will overflow determinant (remember, we scaled down the input in first place to avoid this very problem).

So what we do is increse the scale factor of the matrix (the value that will be returned, which is initially set to the provided desired precision factor) by this amount. It is quite likely that we can't scale it (by right shifting it) beyond some limit without overflowing. That's when the residual scale (the remaining shiftings) is used to scale down (left shift) the matrix elements. We lose precision, but this is the last place we can scale).

Definition at line 554 of file Matrix.nxc.

References MatrixAdjugate(), MatrixDeterminant(), MatrixMaxima(), MatrixReduce(), MatrixScale(), MatrixShiftRight(), and Matrix::rows.

Referenced by KalmanFilterStep().

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

Function Documentation