LSLXG

Solves a sparse system of linear algebraic equations by Gaussian elimination.

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)

B — Vector of length N containing the right-hand side of the linear system.   (Input)

X — 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 ATx = 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.
Default: IPARAM(1) = 0.
See Comment 3.

RPARAM — Parameter vector of length 5.   (Input/Output)
See Comment 3.

FORTRAN 90 Interface

Generic:                              CALL LSLXG (A, IROW, JCOL, B, X [,…])

Specific:                             The specific interface names are S_LSLXG and D_LSLXG.

FORTRAN 77 Interface

Single:            CALL LSLXG (N, NZ, A, IROW, JCOL, B, IPATH, IPARAM, RPARAM, X)

Double:                              The double precision name is DLSLXG.

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 LSLXG solves a system of linear algebraic equations having a real sparse coefficient matrix. It first uses the routine LFTXG to perform an LU factorization of the coefficient matrix. The solution of the linear system is then found using LFSXG.

The routine LFTXG 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 L2LXG/DL2LXG. The reference is:

CALL L2LXG (N, NZ, A, IROW, JCOL, B, IPATH, IPARAM, RPARAM, X, 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 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

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 LSLXG, then set IPARAM(1) to zero and call the routine LSLXG. Otherwise, if any nondefault parameters are desired for IPARAM or RPARAM. then the following steps should be taken before calling LSLXG.

     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.

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 L2LXG 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: 1016

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 linear system:

Let xT = (1, 2, 3, 4, 5, 6) so that Ax = (10, 7, 45, 33,−34, 31)T. The number of nonzeros in A is
nz = 15. The sparse coordinate form for A is given by:

 

 

      USE LSLXG_INT
      USE WRRRN_INT
      USE L4LXG_INT
      INTEGER    N, NZ

      PARAMETER  (N=6, NZ=15)

!

      INTEGER    IPARAM(6), IROW(NZ), JCOL(NZ)

      REAL       A(NZ), B(N), RPARAM(5), X(N)

!

      DATA A/6., 10., 15., -3., 10., -1., -1., -3., -5., 1., 10., -1.,&

          -2., -1., -2./

      DATA B/10., 7., 45., 33., -34., 31./

      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/

!
!                                 Change a default parameter

      CALL L4LXG (IPARAM, RPARAM)

      IPARAM(5) = 203

!                                 Solve for X

      CALL LSLXG (A, IROW, JCOL, B, X, IPARAM=IPARAM)

!

      CALL WRRRN (' x ', X, 1, N, 1)

      END

Output

 

                         x
    1       2       3       4       5       6
1.000   2.000   3.000   4.000   5.000   6.000

Visual Numerics, Inc.
Visual Numerics - Developers of IMSL and PV-WAVE
http://www.vni.com/
PHONE: 713.784.3131
FAX:713.781.9260