LFTXG
Computes the LU factorization of a real general sparse matrix.
Required Arguments
A — 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)
NL — The number of nonzero coefficients in the triangular matrix L excluding the diagonal elements. (Output)
NFAC — On input, the dimension of vector FACT. (Input/Output)
On output, the number of nonzero coefficients in the triangular matrix L and U.
FACT — Vector of length NFAC containing the nonzero elements of L (excluding the diagonals) in the first NL locations and the nonzero elements of U in NL + 1 to NFAC locations. (Output)
IRFAC — Vector of length NFAC containing the row numbers of the corresponding elements in FACT. (Output)
JCFAC — Vector of length NFAC containing the column numbers of the corresponding elements in FACT. (Output)
IPVT — Vector of length N containing the row pivoting information for the LU factorization. (Output)
JPVT — Vector of length N containing the column pivoting information for the LU factorization. (Output)
Optional Arguments
N — Number of equations. (Input)
Default: N = size (IPVT,1).
NZ — The number of nonzero coefficients in the linear system. (Input)
Default: NZ = size (A,1).
IPARAM — Parameter vector of length 6. (Input/Output)
Set IPARAM(1) to zero for default values of IPARAM and RPARAM.
Default: IPARAM(1) = 0.
See Comment 3.
RPARAM — Parameter vector of length 5. (Input/Output)
See Comment 3.
FORTRAN 90 Interface
Generic: CALL LFTXG (A, IROW, JCOL, NL, NFAC, FACT, IRFAC, JCFAC, IPVT, JPVT [, …])
Specific: The specific interface names are S_LFTXG and D_LFTXG.
FORTRAN 77 Interface
Single: CALL LFTXG (N, NZ, A, IROW, JCOL, IPARAM, RPARAM, NFAC, NL, FACT, IRFAC, JCFAC, IPVT, JPVT)
Double: The double precision name is DLFTXG.
Description
Consider the linear equation
Ax = b
where A is a n × n sparse matrix. The sparse coordinate format for the matrix A requires one real and two integer vectors. The real 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 routine LFTXG performs an LU factorization of the coefficient matrix A. It by default uses a symmetric Markowitz strategy (Crowe et al. 1990) to choose pivots that most likely would reduce fillins 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 using
LFSXG 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 L2TXG/DL2TXG. The reference is:
CALL L2TXG (N, NZ, A, IROW, JCOL, IPARAM, RPARAM, NFAC, NL, FACT, IRFAC, JCFAC, IPVT, JPVT, WK, LWK, IWK, LIWK)
The additional arguments are as follows:
WK — Real work vector of length LWK.
LWK — The length of WK, LWK should be at least MAXNZ.
IWK — Integer work vector of length LIWK.
LIWK — The length of IWK, LIWK should be at least 15N + 4 * MAXNZ.
The workspace limit is determined by MAXNZ, where
MAXNZ = MIN0(LWK, INT(0.25(LIWK-15N)))
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. If the default parameters are desired for LFTXG, then set IPARAM(1) to zero and call the routine LFTXG. Otherwise, if any nondefault parameters are desired for IPARAM or RPARAM, then the following steps should be taken before calling LFTXG.
CALL L4LXG (IPARAM, RPARAM)
Set nondefault values for desired IPARAM, RPARAM elements.
Note that the call to L4LXG 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 L2TXG is called, the values of LWK and LIWK are used instead of IPARAM(5).
IPARAM(6) = Not used in LFTXG.
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 the lower triangular factor L 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 DL4LXG is called and RPARAM is declared double precision.
Example
As an example, consider the 6 × 6 matrix of a linear system:
The sparse coordinate form for A is given by:
USE LFTXG_INT
USE WRRRN_INT
USE WRIRN_INT
INTEGER N, NZ
PARAMETER (N=6, NZ=15)
INTEGER IROW(NZ), JCOL(NZ), NFAC, NL,&
IRFAC(3*NZ), JCFAC(3*NZ), IPVT(N), JPVT(N)
REAL A(NZ), FACT(3*NZ)
!
DATA A/6., 10., 15., -3., 10., -1., -1., -3., -5., 1., 10., -1.,&
-2., -1., -2./
DATA IROW/6, 2, 3, 2, 4, 4, 5, 5, 5, 5, 1, 6, 6, 2, 4/
DATA JCOL/6, 2, 3, 3, 4, 5, 1, 6, 4, 5, 1, 1, 2, 4, 1/
!
NFAC = 3*NZ
! Use default options
CALL LFTXG (A, IROW, JCOL, NL, NFAC, FACT, IRFAC, JCFAC, IPVT, JPVT)
!
CALL WRRRN (’ fact ’, FACT, 1, NFAC, 1)
CALL WRIRN (’ irfac ’, IRFAC, 1, NFAC, 1)
CALL WRIRN (’ jcfac ’, JCFAC, 1, NFAC, 1)
CALL WRIRN (’ p ’, IPVT, 1, N, 1)
CALL WRIRN (’ q ’, JPVT, 1, N, 1)
!
END
Output
fact
1 2 3 4 5 6 7 8 9 10
-0.10 -5.00 -0.20 -0.10 -0.10 -1.00 -0.20 4.90 -5.10 1.00
11 12 13 14 15 16
-1.00 30.00 6.00 -2.00 10.00 15.00
irfac
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 4 5 5 6 6 6 5 5 4 4 3 3 2 1
jcfac
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 3 1 4 2 5 2 6 6 5 6 4 4 3 2 1
p
1 2 3 4 5 6
3 1 6 2 5 4
q
1 2 3 4 5 6
3 1 2 6 5 4
