UT_MatrixSolver Class Reference

#include <UT_MatrixSolver.h>

List of all members.

Public Member Functions

int LUDecompOld (UT_Matrix &a, UT_Permutation &index, float &d, float tol=1e-20F)
void LUBackSubOld (const UT_Matrix &a, const UT_Permutation &index, UT_Vector &b)
int LUDecomp (UT_Matrix &a, UT_Permutation &index, float &d, float tol=1e-20F)
void LUBackSub (const UT_Matrix &a, const UT_Permutation &index, UT_Vector &b)
int LUDecompRect (UT_Matrix &A, UT_Permutation &pivots, float &detsign, float tol=1e-6F)
void LUDecompBackSub (const UT_Matrix &A, const UT_Permutation &pivots, UT_Vector &b)
int LUDecompCompanion (const UT_Matrix &P, float a, float b, UT_Matrix &R, UT_Permutation &index, float tol=1e-20F)
void LUBackSubCompanion (const UT_Matrix &R, float a, float b, const UT_Permutation &index, UT_Vector &y)
int choleskyDecomp (UT_Matrix &a, UT_Vector &d, float tol=1e-5F)
int choleskyBackSub (const UT_Matrix &a, const UT_Vector &d, const UT_Vector &b, UT_Vector &x, float tol=1e-5F)
int inversePowerIterate (const UT_Matrix &C1, const UT_Matrix &C2, UT_Matrix &R, UT_Matrix &tmp, UT_Permutation &index, float s, float &s1, float &s2, UT_Vector &q, UT_Vector &Aq, float starttol=1e-2F, int startiter=5, float finaltol=1e-5F, float doubletol=1e-4F, int finaliter=50)
void inverse (UT_Matrix &a, UT_Permutation &index, UT_Matrix &ia)
int findLinIndRows (UT_Matrix &A, UT_Permutation &index, float tol=1E-6F)
void fullGaussianElimination (UT_Matrix &G, UT_Matrix &Gu, UT_Matrix &Gv, UT_Permutation &rowperm, UT_Permutation &colperm, float &detsign)
void detWithPartials (const UT_Matrix &G, const UT_Matrix &Gu, const UT_Matrix &Gv, const UT_Permutation &rowperm, const UT_Permutation &colperm, float detsign, float &retdet, float &detu, float &detv)
float det (UT_Matrix &a, float d)
float det3x3 (const UT_Matrix &A, const UT_Matrix &B, const UT_Matrix &C, int p, int q, int r, int s, int t, int u)
void condEstimate (const UT_Matrix &A, UT_Vector &y)
 Estimates condtion number of upper triangular matrix:.
float getConditionLUD (const UT_Matrix &A, const UT_Permutation &index, float anorm)
void house (const UT_Vector &x, UT_Vector &v, float &b)
 Find householder vector of x.
void house (const UT_Matrix &x, UT_Vector &v, float &b)
void findGivens (float a, float b, float &c, float &s, float zerotol=1e-20F)
 Finds the givens rotation required to 0 b:.
int findHalfGivens (const UT_Matrix &A, float &c, float &s, float tol=0.0F)
void triangularize (UT_Matrix &A, UT_Matrix &B, UT_Matrix *Q=0)
void hessentri (UT_Matrix &A, UT_Matrix &B)
 Transforms A into upper hessenburg and B into upper triangular.
int realSchurFormQZ (UT_Matrix &oA, UT_Matrix &oB, float tol=1e-6F, int maxIteration=30)
void hessenberg (UT_Matrix &A)
void hessenberg (UT_Matrix &A, UT_Matrix &P)
 Computes P st A' = P^T A P.
int bidiagonalize (UT_Matrix &A)
 Transforms A into a bidiagonal matrix via householder transformations.
int realSchurForm (UT_Matrix &A, UT_Matrix *Q=0, float tol=1E-6F, int maxIteration=30)
int gkSVD (UT_Matrix &A, float tol=1e-6F, int maxIteration=30)
int SVDDecomp (UT_Matrix &a, UT_Vector &w, UT_Matrix &v, int maxIterstion=30)
int SVDBackSub (UT_Matrix &u, UT_Vector &w, UT_Matrix &v, UT_Vector &b, UT_Vector &x, float tol=1e-6F)
void findEigenValues (const UT_Matrix &A, UT_Vector &vreal, UT_Vector &vimg)
 Finds eigenvalues from a real schur form matrix:.
void findEigenValues (const UT_Matrix &A, const UT_Matrix &B, UT_Vector &sreal, UT_Vector &simg, UT_Vector &treal, UT_Vector &timg)
 Finds eigenvalues from generalized system (A - lambdaB).
int findUVfromEigenvector (const UT_Vector &vect, int udeg, int vdeg, int tdeg, float &u, float &v)
void findRightEigenVector (const UT_Matrix &A, const UT_Matrix &Q, UT_Vector &vector, int i)

Detailed Description

Definition at line 33 of file UT_MatrixSolver.h.

Member Function Documentation

int UT_MatrixSolver::bidiagonalize ( UT_Matrix &  A  ) 

Transforms A into a bidiagonal matrix via householder transformations.

int UT_MatrixSolver::choleskyBackSub ( const UT_Matrix &  a,
const UT_Vector &  d,
const UT_Vector &  b,
UT_Vector &  x,
float  tol = 1e-5F 
)

Solves the set of n linear equations, A.x = b, where a is a nonnegative definite symmetric matrix. Input: a[1..n][1..n] and d[1..n] as output from choleskyDecomp() above. Only the lower triangle of a is read from. b[1..n] is the right-hand side of A.x = b to solve for tol is the tolerance check for when an element of d is deemed 0 Output: x[1..n], the solution of A.x = b Returns the number of articial zero's placed into x.

int UT_MatrixSolver::choleskyDecomp ( UT_Matrix &  a,
UT_Vector &  d,
float  tol = 1e-5F 
)

Cholesky factorization

To solve a full rank system A . x = b where A can be undertermined (ie. A has less rows than columns), we can make use of the Cholesky factorization functions below by way of the normal equations like so: 1. Left multiply both sides by the tranpose of A, A^T to get (A^T . A) . x = (A^T . b) 2. Now solve for x using P . x = c where P = A^T . A and c = A^T . b This is done by first calling choleskyDecomp() using P since it will be symmetric non-negative definite. Then use choleskyBackSub() to obtain x for particular values of c. Performs a Cholesky decomposition of the symmetric non-negative definite matrix A such that A = L . L^T where L^T is tranpose of the lower triangular matrix L. Input: Symmetric non-negative definite matrix a[1..n][1..n]. Only the upper triangle of a is read from. tol is the tolerance check for when a sum is deemed 0 Output: Cholesky factor L is returned in the lower triangle of A, except for its diagonal elements which is returned in d[1..n] Returns the number of articial zero's placed into d. If we encounter negative diagonal values, they are zeroed out and we return -N where N is the number of negative values found.

void UT_MatrixSolver::condEstimate ( const UT_Matrix &  A,
UT_Vector &  y 
)

Estimates condtion number of upper triangular matrix:.

float UT_MatrixSolver::det ( UT_Matrix &  a,
float  d 
)

Compute the determinant of a LU decomposed matrix. The d is what one gets from LU decomposition.

float UT_MatrixSolver::det3x3 ( const UT_Matrix &  A,
const UT_Matrix &  B,
const UT_Matrix &  C,
int  p,
int  q,
int  r,
int  s,
int  t,
int  u 
) [inline]

Find the determiment: (A(p,q), B(r,s), C(t,u)))

Definition at line 248 of file UT_MatrixSolver.h.

void UT_MatrixSolver::detWithPartials ( const UT_Matrix &  G,
const UT_Matrix &  Gu,
const UT_Matrix &  Gv,
const UT_Permutation &  rowperm,
const UT_Permutation &  colperm,
float  detsign,
float &  retdet,
float &  detu,
float &  detv 
)

After full Gaussian Elimination, this finds the determinant and partials thereof:

void UT_MatrixSolver::findEigenValues ( const UT_Matrix &  A,
const UT_Matrix &  B,
UT_Vector &  sreal,
UT_Vector &  simg,
UT_Vector &  treal,
UT_Vector &  timg 
)

Finds eigenvalues from generalized system (A - lambdaB).

void UT_MatrixSolver::findEigenValues ( const UT_Matrix &  A,
UT_Vector &  vreal,
UT_Vector &  vimg 
)

Finds eigenvalues from a real schur form matrix:.

void UT_MatrixSolver::findGivens ( float  a,
float  b,
float &  c,
float &  s,
float  zerotol = 1e-20F 
)

Finds the givens rotation required to 0 b:.

int UT_MatrixSolver::findHalfGivens ( const UT_Matrix &  A,
float &  c,
float &  s,
float  tol = 0.0F 
)

Find half givens, return 0 if success, otherwise the required rotation is impossible (ie:complex eigenvalue)

int UT_MatrixSolver::findLinIndRows ( UT_Matrix &  A,
UT_Permutation &  index,
float  tol = 1E-6F 
)

Finds all linearly independent rows in A, does NOT require A to be any particular shape. Returns the number of independent rows & first entries of index are their indices in the original matrix. Destroys A.

void UT_MatrixSolver::findRightEigenVector ( const UT_Matrix &  A,
const UT_Matrix &  Q,
UT_Vector &  vector,
int  i 
)

Finds a specified eigenvector from a real schur form matrix. The eigenvector must be real!

int UT_MatrixSolver::findUVfromEigenvector ( const UT_Vector &  vect,
int  udeg,
int  vdeg,
int  tdeg,
float &  u,
float &  v 
)

Finds the u & v eigenvalues from an eigenvector, whose udeg, vdeg, and tdeg are as specified. Returns 0 if fails. NB: Does the s/(1+s) transformation!

void UT_MatrixSolver::fullGaussianElimination ( UT_Matrix &  G,
UT_Matrix &  Gu,
UT_Matrix &  Gv,
UT_Permutation &  rowperm,
UT_Permutation &  colperm,
float &  detsign 
)

Similar to findLinIndRows, performs gaussian elimination with full pivoting on G. Updates as well Gu, and Gv, the partial derivitive matrix of G(u, v). After this is done, the determinant of G & partials of the determinant can be computed.

float UT_MatrixSolver::getConditionLUD ( const UT_Matrix &  A,
const UT_Permutation &  index,
float  anorm 
)

Finds the condition number of a LUDecomposed matrix. This is just an approximation You must provide the infinite norm of A before LUDecomposition.

int UT_MatrixSolver::gkSVD ( UT_Matrix &  A,
float  tol = 1e-6F,
int  maxIteration = 30 
)

Golub-Kahan SVD algorithm. Resulting SVD matrix found in diaganol of A.

void UT_MatrixSolver::hessenberg ( UT_Matrix &  A,
UT_Matrix &  P 
)

Computes P st A' = P^T A P.

void UT_MatrixSolver::hessenberg ( UT_Matrix &  A  ) 

Transform A into a hessenberg matrix through a series of householder reflections.

void UT_MatrixSolver::hessentri ( UT_Matrix &  A,
UT_Matrix &  B 
)

Transforms A into upper hessenburg and B into upper triangular.

void UT_MatrixSolver::house ( const UT_Matrix &  x,
UT_Vector &  v,
float &  b 
)

void UT_MatrixSolver::house ( const UT_Vector &  x,
UT_Vector &  v,
float &  b 
)

Find householder vector of x.

void UT_MatrixSolver::inverse ( UT_Matrix &  a,
UT_Permutation &  index,
UT_Matrix &  ia 
)

Compute the inverse of a LU decomposed matrix. If you want to solve systems of equations AX=B, where B is a matrix. It is better (faster) to do a LU decomposition and use back substituation for columns of B.

int UT_MatrixSolver::inversePowerIterate ( const UT_Matrix &  C1,
const UT_Matrix &  C2,
UT_Matrix &  R,
UT_Matrix &  tmp,
UT_Permutation &  index,
float  s,
float &  s1,
float &  s2,
UT_Vector &  q,
UT_Vector &  Aq,
float  starttol = 1e-2F,
int  startiter = 5,
float  finaltol = 1e-5F,
float  doubletol = 1e-4F,
int  finaliter = 50 
)

Performs inverse iteration to find the closest eigenvalue(s) to s. Does a two pass method, first using single iterations until starttol is reached, in which case singles are used to achieve final tolerance. If starttol is not reached in startiter iterations, uses double method to find using final tolerance/iterations.

The vector q is updated with the newest eigenvector. Source matrices are: [1 0 0] [0 1 0] C1' = [0 1 0] C2' = [0 0 1] [0 0 C1] [ C2 ] Thus, the initial sizes of the matrices/vectors are (row*col): C1: n*n, C2: n*(n*deg), R: n*(n*deg), tmp: n*(n*deg), index: n, q: n*deg, Aq: n*deg The result code determines how s1 & s2 are to be interpreted: Result: 0 - One eigenvalue found at s1, eigenvector q. 1 - Two real eigenvalues found: s1 & s2. 2 - Complex conjugate eigenvalues found: s1 +- s2i. -1 - Failed to converge to final tolerance using single method. -2 - Failed to converge to final tolerance using double method.

void UT_MatrixSolver::LUBackSub ( const UT_Matrix &  a,
const UT_Permutation &  index,
UT_Vector &  b 
) [inline]

Definition at line 69 of file UT_MatrixSolver.h.

void UT_MatrixSolver::LUBackSubCompanion ( const UT_Matrix &  R,
float  a,
float  b,
const UT_Permutation &  index,
UT_Vector &  y 
)

This takes the result of the previous operation and does a back substitution.

void UT_MatrixSolver::LUBackSubOld ( const UT_Matrix &  a,
const UT_Permutation &  index,
UT_Vector &  b 
)

Solve Ax=b a[1..n][1..n] is a LU Decomposition of matrix A (eg. from LUDecomp()) index describes the row permutations as output from LUDecomp() b[1..n] is input as rhs, and on output contains the solution x

int UT_MatrixSolver::LUDecomp ( UT_Matrix &  a,
UT_Permutation &  index,
float &  d,
float  tol = 1e-20F 
) [inline]

Definition at line 64 of file UT_MatrixSolver.h.

void UT_MatrixSolver::LUDecompBackSub ( const UT_Matrix &  A,
const UT_Permutation &  pivots,
UT_Vector &  b 
)

Performs back substitution using the output of LUDecomp() for a square matrix. Input: A[1..n][1..n] and pivots as output from LUDecompRect() b[1..n] is the right hand side for solving A.x = b Output: b is modified to contain the solution x

int UT_MatrixSolver::LUDecompCompanion ( const UT_Matrix &  P,
float  a,
float  b,
UT_Matrix &  R,
UT_Permutation &  index,
float  tol = 1e-20F 
)

LU decompose a companion matrix The matrix given is the base of the companion matrix: [aI bI 0 0 ] [0 aI bI 0 ] [0 0 aI bI] [P1 P2 P3 P4] ie: [P1 P2 P3 P4] The resulting LU decompostion is written into the R matrix and is: [aI 0 0 0] [I b/aI 0 0 ] [0 aI 0 0] [0 I b/aI 0 ] [0 0 aI 0] [0 0 I b/aI] [R1 R2 R3 L] [0 0 0 U ] LU is stored in the last portion of the matrix & index is the permuation that resulted in it. Thus, index should be the height of P, NOT the entire companion matrix.

Return 0 on success, -1 for singular, and -2 for singular to machine precision (As judged by tol), and -3 for a being near zero.

int UT_MatrixSolver::LUDecompOld ( UT_Matrix &  a,
UT_Permutation &  index,
float &  d,
float  tol = 1e-20F 
)

LU Decomposition of a[1..n][1..n] where a has full rank. Output: index[1..n] is the row permutation d = +/-1 indicating row interchanges was even or odd, resp. return 0 if the matrix is truly singular 1 on success 2 if the matrix is singular to the precision of the algorithm, where tol is the zero tolerance.

int UT_MatrixSolver::LUDecompRect ( UT_Matrix &  A,
UT_Permutation &  pivots,
float &  detsign,
float  tol = 1e-6F 
)

LU decomposition of rectangular A[1..m][1..n] with partial pivoting. Unlike LUDecomp(), this handles pivot values of 0. ie. it performs the decomposition of A = P.L.U for unit lower triangular L and upper triangular U. Input: A[1..m][1..n] Output: A contains the matrices L and U in compact form, without the unit diagonal. L is of size min(m,n) by n. U is of size m by min(m,n) pivots[1..n] is the row permulation P tol is scaled by the largest pivot element detsign is the sign of the determinant used by det() its +1 if row interchanges was even, -1 if odd Returns 0 if the matrix is truly singular 1 on success 2 if the matrix is singular to the precision of the algorithm, where tol is the zero tolerance. This algorithm takes roughly O(m*n^2 - n^3/3) flops

int UT_MatrixSolver::realSchurForm ( UT_Matrix &  A,
UT_Matrix *  Q = 0,
float  tol = 1E-6F,
int  maxIteration = 30 
)

Reduces the matrix to real Schur form: Orthogonal transform responible for getting to real schur form is accumulated in Q, if it is non-zero.

int UT_MatrixSolver::realSchurFormQZ ( UT_Matrix &  oA,
UT_Matrix &  oB,
float  tol = 1e-6F,
int  maxIteration = 30 
)

Converts A into quasi upper triangular & B into upper triangular form using the QZ algorithm.

int UT_MatrixSolver::SVDBackSub ( UT_Matrix &  u,
UT_Vector &  w,
UT_Matrix &  v,
UT_Vector &  b,
UT_Vector &  x,
float  tol = 1e-6F 
)

Perform back substitution on an SVD decomposed matrix. Solves equation Ax = b.

int UT_MatrixSolver::SVDDecomp ( UT_Matrix &  a,
UT_Vector &  w,
UT_Matrix &  v,
int  maxIterstion = 30 
)

Use Numerical Recipes method for SVD decomposition, with results that are suitable for doing back substitution. NOTE: The UT_Matrix should start with 1,1!

Decomposition a = u * w * v^T a[1..m][1..n] also stores the result u[1..m][1..n] w[1..n][1..n] is a diagonal matrix, stored as a vector v[1..n][1..n]

void UT_MatrixSolver::triangularize ( UT_Matrix &  A,
UT_Matrix &  B,
UT_Matrix *  Q = 0 
)

Upper triangulizes A with householder transforms, applying simultaneously to A and optionally Q.

The documentation for this class was generated from the following file:
Generated on Fri May 25 00:10:51 2012 for HDK by  doxygen 1.5.9