public class TriangularSolver_DSCC
extends java.lang.Object
Constructor and Description |
---|
TriangularSolver_DSCC() |
Modifier and Type | Method and Description |
---|---|
static double[] |
adjust(org.ejml.data.DGrowArray gwork,
int desired)
Resizes the array to ensure that it is at least of length desired and returns its internal array
|
static int[] |
adjust(org.ejml.data.IGrowArray gwork,
int desired)
Resizes the array to ensure that it is at least of length desired and returns its internal array
|
static int[] |
adjust(org.ejml.data.IGrowArray gwork,
int desired,
int zeroToM) |
static int[] |
adjustClear(org.ejml.data.IGrowArray gwork,
int desired) |
static void |
eliminationTree(org.ejml.data.DMatrixSparseCSC A,
boolean ata,
int[] parent,
org.ejml.data.IGrowArray gwork)
If ata=false then it computes the elimination tree for sparse lower triangular square matrix
generated from Cholesky decomposition.
|
protected static int |
postorder_dfs(int j,
int k,
int[] w,
int[] post,
int N)
Depth First Search used inside of
postorder(int[], int, int[], org.ejml.data.IGrowArray) . |
static void |
postorder(int[] parent,
int N,
int[] post,
org.ejml.data.IGrowArray gwork)
Sorts an elimination tree
eliminationTree(org.ejml.data.DMatrixSparseCSC, boolean, int[], org.ejml.data.IGrowArray) into postorder. |
static double |
qualityTriangular(org.ejml.data.DMatrixSparseCSC T)
Computes the quality of a triangular matrix, where the quality of a matrix
is defined in
LinearSolver.quality() . |
static int |
searchNzRowsElim(org.ejml.data.DMatrixSparseCSC A,
int k,
int[] parent,
int[] s,
int[] w)
Given an elimination tree compute the non-zero elements in the specified row of L given the
symmetric A matrix.
|
static int |
searchNzRowsInB(org.ejml.data.DMatrixSparseCSC G,
org.ejml.data.DMatrixSparseCSC B,
int colB,
int[] pinv,
int[] xi,
org.ejml.data.IGrowArray gwork)
Determines which elements in 'X' will be non-zero when the system below is solved for.
|
static void |
solve(org.ejml.data.DMatrixSparseCSC G,
boolean lower,
org.ejml.data.DMatrixSparseCSC B,
org.ejml.data.DMatrixSparseCSC X,
org.ejml.data.DGrowArray g_x,
org.ejml.data.IGrowArray g_xi,
org.ejml.data.IGrowArray g_w)
Computes the solution to the triangular system.
|
static int |
solve(org.ejml.data.DMatrixSparseCSC G,
boolean lower,
org.ejml.data.DMatrixSparseCSC B,
int colB,
double[] x,
int[] pinv,
org.ejml.data.IGrowArray g_xi,
org.ejml.data.IGrowArray g_w)
Computes the solution to a triangular system with (optional) pivots.
|
static void |
solveL(org.ejml.data.DMatrixSparseCSC L,
double[] x)
Solves for a lower triangular matrix against a dense matrix.
|
static void |
solveTranL(org.ejml.data.DMatrixSparseCSC L,
double[] x)
Solves for the transpose of a lower triangular matrix against a dense matrix.
|
static void |
solveU(org.ejml.data.DMatrixSparseCSC U,
double[] x)
Solves for an upper triangular matrix against a dense vector.
|
public static void solveL(org.ejml.data.DMatrixSparseCSC L, double[] x)
L
- Lower triangular matrix. Diagonal elements are assumed to be non-zerox
- (Input) Solution matrix 'b'. (Output) matrix 'x'public static void solveTranL(org.ejml.data.DMatrixSparseCSC L, double[] x)
L
- Lower triangular matrix. Diagonal elements are assumed to be non-zerox
- (Input) Solution matrix 'b'. (Output) matrix 'x'public static void solveU(org.ejml.data.DMatrixSparseCSC U, double[] x)
U
- Upper triangular matrix. Diagonal elements are assumed to be non-zerox
- (Input) Solution matrix 'b'. (Output) matrix 'x'public static void solve(org.ejml.data.DMatrixSparseCSC G, boolean lower, org.ejml.data.DMatrixSparseCSC B, org.ejml.data.DMatrixSparseCSC X, org.ejml.data.DGrowArray g_x, org.ejml.data.IGrowArray g_xi, org.ejml.data.IGrowArray g_w)
G
- (Input) Lower or upper triangular matrix. diagonal elements must be non-zero. Not modified.lower
- true for lower triangular and false for upperB
- (Input) Matrix. Not modified.X
- (Output) Solutiong_x
- (Optional) Storage for workspace.g_xi
- (Optional) Storage for workspace.g_w
- (Optional) Storage for workspace.public static int solve(org.ejml.data.DMatrixSparseCSC G, boolean lower, org.ejml.data.DMatrixSparseCSC B, int colB, double[] x, int[] pinv, org.ejml.data.IGrowArray g_xi, org.ejml.data.IGrowArray g_w)
G
- (Input) Lower or upper triangular matrix. diagonal elements must be non-zero and last
or first entry in a column. Not modified.lower
- true for lower triangular and false for upperB
- (Input) Matrix. Not modified.colB
- The column in B which is solved forx
- (Output) Storage for dense solution. length = G.numRowspinv
- (Input, Optional) Permutation vector. Maps col j to G. Null if no pivots.g_xi
- (Optional) Storage for workspace. Will contain nonzero pattern.
See searchNzRowsInB(DMatrixSparseCSC, DMatrixSparseCSC, int, int[], int[], IGrowArray)
g_w
- (Optional) Storage for workspace.public static int searchNzRowsInB(org.ejml.data.DMatrixSparseCSC G, org.ejml.data.DMatrixSparseCSC B, int colB, int[] pinv, int[] xi, org.ejml.data.IGrowArray gwork)
Determines which elements in 'X' will be non-zero when the system below is solved for.
G*X = Bxi will contain a list of ordered row indexes in B which will be modified starting at xi[top] to xi[n-1]. top is the value returned by this function.
See cs_reach in dsparse library to understand the algorithm. This code follow the spirit but not the details because of differences in the contract.
G
- (Input) Lower triangular system matrix. Diagonal elements are assumed to be not zero. Not modified.B
- (Input) Matrix B. Not modified.colB
- Column in B being solved forpinv
- (Input, Optional) Column pivots in G. Null if no pivots.xi
- (Output) List of row indices in B which are non-zero in graph order. Must have length B.numRowsgwork
- workspace array used internally. Can be null.public static void eliminationTree(org.ejml.data.DMatrixSparseCSC A, boolean ata, int[] parent, org.ejml.data.IGrowArray gwork)
If ata=false then it computes the elimination tree for sparse lower triangular square matrix generated from Cholesky decomposition. If ata=true then it computes the elimination tree of ATA without forming ATA explicitly. In an elimination tree the parent of node 'i' is 'j', where the first off-diagonal non-zero in column 'i' has row index 'j'; j > i for which l[k,i] != 0.
This tree encodes the non-zero elements in L given A, e.g. L*L' = A, and enables faster to compute solvers than the general purpose implementations.
Functionally identical to cs_etree in csparse
A
- (Input) M by N sparse upper triangular matrix. If ata is false then M=N otherwise M ≥ Nata
- If true then it computes elimination treee of A'A without forming A'A otherwise computes elimination
tree for cholesky factorizationparent
- (Output) Parent of each node in tree. This is the elimination tree. -1 if no parent. Size N.gwork
- (Optional) Internal workspace. Can be null.public static void postorder(int[] parent, int N, int[] post, org.ejml.data.IGrowArray gwork)
Sorts an elimination tree eliminationTree(org.ejml.data.DMatrixSparseCSC, boolean, int[], org.ejml.data.IGrowArray)
into postorder. In a postoredered tree, the d proper
descendants of any node k are numbered k-d through k-1. Non-recursive implementation for better performance.
post[k] = i means node 'i' of the original tree is node 'k' in the postordered tree.
See page 44
parent
- (Input) The elimination tree.N
- Number of elements in parentpost
- (Output) Postordering permutation.gwork
- (Optional) Internal workspace. Can be nullprotected static int postorder_dfs(int j, int k, int[] w, int[] post, int N)
postorder(int[], int, int[], org.ejml.data.IGrowArray)
.public static int searchNzRowsElim(org.ejml.data.DMatrixSparseCSC A, int k, int[] parent, int[] s, int[] w)
Given an elimination tree compute the non-zero elements in the specified row of L given the symmetric A matrix. This is in general much faster than general purpose algorithms
Functionally equivalent to cs_ereach() in csparse
A
- Symmetric matrix.k
- Row in A being processed.parent
- elimination tree.s
- (Output) s[top:(n-1)] = pattern of L[k,:]. Must have length A.numColsw
- workspace array used internally. All elements must be ≥ 0 on input. Must be of size A.numColspublic static int[] adjust(org.ejml.data.IGrowArray gwork, int desired)
public static int[] adjust(org.ejml.data.IGrowArray gwork, int desired, int zeroToM)
public static int[] adjustClear(org.ejml.data.IGrowArray gwork, int desired)
public static double[] adjust(org.ejml.data.DGrowArray gwork, int desired)
public static double qualityTriangular(org.ejml.data.DMatrixSparseCSC T)
LinearSolver.quality()
. In
this situation the quality os the absolute value of the product of
each diagonal element divided by the magnitude of the largest diagonal element.
If all diagonal elements are zero then zero is returned.T
- A matrix.