Direct Sparse Solver (Multicore Analysis and Sparse Matrix Toolkit)
- Updated2023-02-21
- 3 minute(s) read
Solving a system of sparse linear equations depends on the matrix type. The following table shows the sparse solver method to use for different matrix types.
| Matrix Type | Sparse Solver Method |
|---|---|
| Lower triangular matrix | Forward substitution |
| Upper triangular matrix | Backward substitution |
| General sparse matrix | Reordering, symbolic factorization, numerical factorization, and forward and backward substitution |
If A is a sparse triangular matrix, to solve the sparse linear equations is straightforward. When A is a lower triangular matrix, the system can be solved by forward substitution. When A is an upper triangular matrix, the system can be solved by backward substitution. You can use the Solve Triangular Equations VI to solve a system if A is a sparse triangular matrix.
If matrix A is a general sparse matrix, you complete the following typical tasks to solve the system of general sparse linear equations.
Reordering
Decomposing a sparse matrix into its lower and upper triangular matrices tends to induce new nonzero elements into the decomposed triangular matrices. Those new nonzero elements, which are not in the original matrix A, are called fill-in. Fill-in can impact the sparse solver performance, because the larger the number of fill-in, the more difficult it is to store and operate the decomposed triangular matrices.
The following figure shows an example of fill-in.
Matrix A has 13 nonzero elements. After decomposing matrix A intro its lower and upper triangular matrices L and U, all elements become nonzero.
Reordering is a process that reorders the rows and columns in matrix A. Reordering minimizes the fill-in in the decomposed matrices. Reordering involves the graph or sparsity pattern of the matrix. The actual values of nonzero elements in A are not important when reordering. Graph theory and algorithms, such as minimum degree method, determine the reordering strategy. The following figure illustrates one reordering strategy where no fill-in is induced in the decomposition.
Symbolic Factorization
The purpose of symbolic factorization is to determine the sparsity pattern in the decomposed lower and upper triangular matrices. Symbolic factorization simulates the decomposition process given the pre-defined reordering strategy. Symbolic factorization also allocates the appropriate structure and workspace for numerical factorization. Similar to reordering, symbolic factorization involves only the sparsity pattern of the original matrix A. Therefore, you can apply symbolic factorization to a set of matrices with the same sparsity pattern.
Numerical Factorization
Numerical factorization performs the actual factorization on the original matrix A or a sparse matrix which has the same sparsity pattern as A. Numerical factorization follows the simulated decomposition process by using the pre-defined reordering strategy in symbolic factorization. Also, the pre-allocated structure and workspace store the nonzero elements induced in the decomposed triangular matrices.
Forward and Backward Substitution
You can solve the decomposed triangular equations by forward and backward substitution. You must reorder the solution of the decomposed triangular equations to solve the original linear equations. You can repeat forward and backward substitution by using different right-hand side values of b. Optionally, you can improve the solution by iterative refinement.