LSLZG
Solves a complex sparse system of linear equations by Gaussian elimination.
Required Arguments
A — Complex vector of length NZ containing the nonzero coefficients of the linear system. (Input)
IROW — Vector of length NZ containing the row numbers of the corresponding elements in A. (Input)
JCOL — Vector of length NZ containing the column numbers of the corresponding elements in A. (Input)
B — Complex vector of length N containing the right-hand side of the linear system. (Input)
X — Complex vector of length N containing the solution to the linear system. (Output)
Optional Arguments
N — Number of equations. (Input)
Default: N = size (B,1).
NZ — The number of nonzero coefficients in the linear system. (Input)
Default: NZ = size (A,1).
IPATH — Path indicator. (Input)
IPATH = 1 means the system Ax = b is solved.
IPATH = 2 means the system AH x = b is solved.
Default: IPATH =1.
IPARAM — Parameter vector of length 6. (Input/Output)
Set IPARAM(1) to zero for default values of IPARAM and RPARAM. See Comment 3.
Default: IPARAM = 0.
RPARAM — Parameter vector of length 5. (Input/Output)
See Comment 3
FORTRAN 90 Interface
Generic: CALL LSLZG (A, IROW, JCOL, B, X [, …])
Specific: The specific interface names are S_LSLZG and D_LSLZG.
FORTRAN 77 Interface
Single: CALL LSLZG (N, NZ, A, IROW, JCOL, B, IPATH, IPARAM, RPARAM, X)
Double: The double precision name is DLSLZG.
Description
Consider the linear equation
Ax = b
where A is a n × n complex sparse matrix. The sparse coordinate format for the matrix A requires one complex and two integer vectors. The complex array a contains all the nonzeros in A. Let the number of nonzeros be nz. The two integer arrays irow and jcol, each of length nz, contain the row and column numbers for these entries in A. That is
Airow(i), icol(i) = a(i), i = 1, …, nz
with all other entries in A zero.
The subroutine
LSLZG solves a system of linear algebraic equations having a complex sparse coefficient matrix. It first uses the routine
LFTZG to perform an
LU factorization of the coefficient matrix. The solution of the linear system is then found using
LFSZG. The routine
LFTZG by default uses a
symmetric Markowitz strategy (Crowe et al. 1990) to choose pivots that most likely would reduce fill-ins while maintaining numerical stability. Different strategies are also provided as options for row oriented or column oriented problems. The algorithm can be expressed as
P AQ = LU
where P and Q are the row and column permutation matrices determined by the Markowitz strategy (Duff et al. 1986), and L and U are lower and upper triangular matrices, respectively. Finally, the solution x is obtained by the following calculations:
1) Lz = Pb
2) Uy = z
3) x = Qy
Comments
1. Workspace may be explicitly provided, if desired, by use of L2LZG/DL2LZG. The reference is:
CALL L2LZG (N, NZ, A, IROW, JCOL, B, IPATH, IPARAM, RPARAM, X, WK, LWK, IWK, LIWK)
The additional arguments are as follows:
WK — Complex work vector of length LWK.
LWK — The length of WK, LWK should be at least 2N+ MAXNZ.
IWK — Integer work vector of length LIWK.
LIWK — The length of IWK, LIWK should be at least 17N + 4 * MAXNZ.
The workspace limit is determined by MAXNZ, where
MAXNZ = MIN0(LWK-2N, INT(0.25(LIWK-17N)))
2. Informational errors
Type | Code | Description |
|---|
3 | 1 | The coefficient matrix is numerically singular. |
3 | 2 | The growth factor is too large to continue. |
3 | 3 | The matrix is too ill-conditioned for iterative refinement. |
3. If the default parameters are desired for LSLZG, then set IPARAM(1) to zero and call the routine LSLZG. Otherwise, if any nondefault parameters are desired for IPARAM or RPARAM. then the following steps should be taken before calling LSLZG.
CALL L4LZG (IPARAM, RPARAM)
Set nondefault values for desired IPARAM, RPARAM elements.
Note that the call to L4LZG will set IPARAM and RPARAM to their default values, so only nondefault values need to be set above. The arguments are as follows: |
IPARAM — Integer vector of length 6.
IPARAM(1) = Initialization flag.
IPARAM(2) = The pivoting strategy.
IPARAM(2) | Action |
1 | Markowitz row search |
2 | Markowitz column search |
3 | Symmetric Markowitz search |
Default: 3.
IPARAM(3) = The number of rows which have least numbers of nonzero elements that will be searched for a pivotal element.
Default: 3.
IPARAM(4) = The maximal number of nonzero elements in A at any stage of the Gaussian elimination. (Output)
IPARAM(5) = The workspace limit.
IPARAM(5) | Action |
0 | Default limit, see Comment 1. |
integer | This integer value replaces the default workspace limit. |
When L2LZG is called, the values of LWK and LIWK are used instead of IPARAM(5).
Default: 0.
IPARAM(6) = Iterative refinement is done when this is nonzero.
Default: 0.
RPARAM — Real vector of length 5.
RPARAM(1) = The upper limit on the growth factor. The computation stops when the growth factor exceeds the limit.
Default: 10.
RPARAM(2) = The stability factor. The absolute value of the pivotal element must be bigger than the largest element in absolute value in its row divided by RPARAM(2).
Default: 10.0.
RPARAM(3) = Drop-tolerance. Any element in A will be removed if its absolute value becomes smaller than the drop-tolerance at any stage of the Gaussian elimination.
Default: 0.0.
RPARAM(4) = The growth factor. It is calculated as the largest element in absolute value in A at any stage of the Gaussian elimination divided by the largest element in absolute value in the original A matrix. (Output)
Large value of the growth factor indicates that an appreciable error in the computed solution is possible.
RPARAM(5) = The value of the smallest pivotal element in absolute value. (Output)
If double precision is required, then DL4LZG is called and RPARAM is declared double precision.
Example
As an example, consider the 6 × 6 linear system:
Let
xT = (1 + i, 2 + 2i, 3 + 3i, 4 + 4i, 5 + 5i, 6 + 6i)
so that
Ax = (3 + 17i, −19 + 5i, 6 + 18i, −38 + 32i, −63 + 49i, −57 + 83i)T
The number of nonzeros in A is nz = 15. The sparse coordinate form for A is given by:
USE LSLZG_INT
USE WRCRN_INT
INTEGER N, NZ
PARAMETER (N=6, NZ=15)
!
INTEGER IROW(NZ), JCOL(NZ)
COMPLEX A(NZ), B(N), X(N)
!
DATA A/(3.0,7.0), (3.0,2.0), (-3.0,0.0), (-1.0,3.0), (4.0,2.0),&
(10.0,7.0), (-5.0,4.0), (1.0,6.0), (-1.0,12.0), (-5.0,0.0),&
(12.0,2.0), (-2.0,8.0), (-2.0,-4.0), (-1.0,2.0), (-7.0,7.0)/
DATA B/(3.0,17.0), (-19.0,5.0), (6.0,18.0), (-38.0,32.0),&
(-63.0,49.0), (-57.0,83.0)/
DATA IROW/6, 2, 2, 4, 3, 1, 5, 4, 6, 5, 5, 6, 4, 2, 5/
DATA JCOL/6, 2, 3, 5, 3, 1, 1, 4, 1, 4, 5, 2, 1, 4, 6/
!
! Use default options
CALL LSLZG (A, IROW, JCOL, B, X)
!
CALL WRCRN (’X’, X)
END
Output
X
1 ( 1.000, 1.000)
2 ( 2.000, 2.000)
3 ( 3.000, 3.000)
4 ( 4.000, 4.000)
5 ( 5.000, 5.000)
6 ( 6.000, 6.000)
