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 Ax=b.

Namespace: Imsl.Math
Assembly: ImslCS (in ImslCS.dll) Version: 6.5.0.0

Syntax

C#
[SerializableAttribute]
public class SuperLU
Visual Basic (Declaration)
<SerializableAttribute> _
Public Class SuperLU
Visual C++
[SerializableAttribute]
public ref class SuperLU

Remarks

Consider the sparse linear system of equations

Ax=b.
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 P_rD_rAD_cP_c=LU. Here, D_r and D_c are positive definite diagonal matrices to equilibrate the system and P_r and P_c 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 Ax=b 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 D_r. Multiplying P_r(D_rb) means permuting the rows of D_rb. 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 Ax=b is solved the following steps are performed:

  1. Equilibrate matrix A, i.e. compute diagonal matrices D_r and D_c 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.
  2. 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 P_c is a column permutation matrix.
  3. 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.
  4. 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 U_j denote the j-th column of matrices \tilde{A} and U, respectively.
  5. Estimate the reciprocal of the condition number of matrix \tilde{A}.
Method Solve uses this information to perform the following steps:
  1. Solve the system Ax=b using the computed triangular factors.
  2. Iteratively refine the solution, again using the computed triangular factors. This is equivalent to Newton's method.
  3. 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).

Copyright (c) 2003, The Regents of the University of California, through Lawrence Berkeley National Laboratory (subject to receipt of any required approvals from U.S. Dept. of Energy)

All rights reserved.

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.

Inheritance Hierarchy

System..::.Object
Imsl.Math..::.SuperLU

See Also