libnxter
0.1

Integer matrix implementation. Provides matrix algebra, cofactor, adjugate and inverse computation. More...
#include "Debug.nxc"
Go to the source code of 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 onedimentional 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 (topleft to bottomright).  
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...  
Integer matrix implementation. Provides matrix algebra, cofactor, adjugate and inverse computation.
Definition in file Matrix.nxc.
#define MI  (  m,  
i  
)  m.elements[i] 
Gives direct onedimentional 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 lefthand and righthand 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 lefthand and righthand operants. It can be used both as lefthand and righthand operants, i.e. 'MI(m,i) = value' or 'variable = MI(m,i)'.
Definition at line 45 of file Matrix.nxc.
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.
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().