Click or drag to resize
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 Ax=b.
Inheritance Hierarchy
SystemObject
  Imsl.MathSuperLU

Namespace: Imsl.Math
Assembly: ImslCS (in ImslCS.dll) Version: 6.5.2.0
Syntax
[SerializableAttribute]
public class SuperLU

The SuperLU type exposes the following members.

Constructors
  NameDescription
Public methodSuperLU
Constructor for SuperLU.
Top
Methods
  NameDescription
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetHashCode
Serves as a hash function for a particular type.
(Inherited from Object.)
Public methodGetPerformanceTuningParameters
Returns a performance tuning parameter value.
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Public methodSetPerformanceTuningParameters
Sets performance tuning parameters.
Public methodSolve
Computation of the solution vector for the system  Ax = b.
Public methodSolveTranspose
Computation of the solution vector for the system  A^Tx = b.
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Top
Properties
  NameDescription
Public propertyColumnOrderingMethod
The method used to permute the columns of the input matrix.
Public propertyConditionNumber
The estimate of the reciprocal condition number of the matrix A.
Public propertyDiagonalPivotThreshold
The threshold used for a diagonal entry to be an acceptable pivot.
Public propertyEquilibrate
Specifies if input matrix A is equilibrated before factorization.
Public propertyEquilibrationMethod
The type of equilibration used before matrix factorization.
Public propertyForwardErrorBound
The estimated forward error bound for the solution vector.
Public propertyIterativeRefinement
The iterative refinement option.
Public propertyPivotGrowth
Specifies whether to compute the reciprocal pivot growth factor.
Public propertyReciprocalPivotGrowthFactor
The reciprocal pivot growth factor.
Public propertyRelativeBackwardError
The componentwise relative backward error of the solution vector.
Public propertySymmetricMode
The symmetric mode option.
Top
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.

See Also

Reference

Other Resources