SuperLU Class

Computes the LU factorization of a general sparse matrix of type SparseMatrix by a column method and solves the real sparse linear system of equations .

For a list of all members of this type, see SuperLU Members.

System.Object
Imsl.Math.SuperLU

public class SuperLU

Thread Safety

Public static (Shared in Visual Basic) members of this type are safe for multithreaded operations. Instance members are not guaranteed to be thread-safe.

Remarks

Consider the sparse linear system of equations

Here, A is a general square, nonsingular, n by n sparse matrix, and x and b are vectors of length n. All entries in A, x and b are of type double.

Gaussian elimination, applied to the system above, can be shortly described as follows:

1. Compute a triangular factorization . Here, and are positive definite diagonal matrices to equilibrate the system and and are permutation matrices to ensure numerical stability and preserve sparsity. L is a unit lower triangular matrix and U is an upper triangular matrix.

2. Solve by evaluating

$x=A^{-1}b=D_c(P_c(U^{-1}(L^{-1}(P_r(D_rb))))) \,.$

This is done efficiently by multiplying from right to left in the last expression: Scale the rows of b by

. Multiplying

means permuting the rows of

. Multiplying $L^{-1}(P_rD_rb)$ means solving the triangular system of equations with matrix L by substitution. Similarly, multiplying $U^{-1}(L^{-1}(P_rD_rb))$ means solving the triangular system with U.

Class SuperLU handles step 1 above in the Solve method if it has not been computed prior to step 2. More precisely, before is solved the following steps are performed:

Equilibrate matrix A, i.e. compute diagonal matrices and so that $\hat{A}=D_rAD_c$ is "better conditioned" than A, i.e. $\hat{A}^{-1}$ is less sensitive to perturbations in $\hat{A}$ than $A^{-1}$ is to perturbations in A.
Order the columns of $\hat{A}$ to increase the sparsity of the computed L and U factors, i.e. replace $\hat{A}$ by $\hat{A}P_c$ where is a column permutation matrix.
Compute the LU factorization of $\hat{A}P_c$ . For numerical stability, the rows of $\hat{A}P_c$ are eventually permuted through the factorization process by scaled partial pivoting, leading to the decomposition $\tilde{A}:=P_r\hat{A}P_c=LU$ . The LU factorization is done by a left looking supernode-panel algorithm with 2-D blocking. See Demmel, Eisenstat, Gilbert et al. (1999) for further information on this technique.
Compute the reciprocal pivot growth factor
$\max_{1 \le j \le n} \frac{\|\tilde{A}_j\|_\infty}{\|U_j\|_\infty} \,$
where $\tilde{A}_j$ and denote the j-th column of matrices $\tilde{A}$ and U, respectively.
Estimate the reciprocal of the condition number of matrix $\tilde{A}$ .

Method Solve uses this information to perform the following steps:

Solve the system using the computed triangular factors.
Iteratively refine the solution, again using the computed triangular factors. This is equivalent to Newton's method.
Compute forward and backward error bounds for the solution vector x.

Some of the steps mentioned above are optional. Their settings can be controlled by the Set methods and properties of class SuperLU.

Class SuperLU is based on the SuperLU code written by Demmel, Gilbert, Li et al. For more detailed explanations of the factorization and solve steps, see the SuperLU Users' Guide (1999).

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

(1) Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

(2) Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

(3) Neither the name of Lawrence Berkeley National Laboratory, U.S. Dept. of Energy nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Requirements

Namespace: Imsl.Math

Assembly: ImslCS (in ImslCS.dll)

SuperLU Class

Thread Safety

Remarks

Requirements

See Also