This subroutine solves a general or symmetric sparse linear system of equations, using an iterative algorithm, with or without preconditioning. The methods include conjugate gradient (CG), conjugate gradient squared (CGS), generalized minimum residual (GMRES), more smoothly converging variant of the CGS method (Bi-CGSTAB), or transpose-free quasi-minimal residual method (TFQMR). The preconditioners include an incomplete LU factorization, an incomplete Cholesky factorization (for positive definite symmetric matrices), diagonal scaling, or symmetric successive over-relaxation (SSOR) with two possible choices for the diagonal matrix: one uses the absolute values sum of the input matrix, and the other uses the diagonal obtained from the LU factorization. The sparse matrix is stored using storage-by-rows for general matrices and upper- or lower-storage-by-rows for symmetric matrices. Matrix A and vectors x and b are used:
where A, x, and b contain long-precision real numbers.
Fortran | CALL DSRIS (stor, init, n, ar, ja, ia, b, x, iparm, rparm, aux1, naux1, aux2, naux2) |
C and C++ | dsris (stor, init, n, ar, ja, ia, b, x, iparm, rparm, aux1, naux1, aux2, naux2); |
PL/I | CALL DSRIS (stor, init, n, ar, ja, ia, b, x, iparm, rparm, aux1, naux1, aux2, naux2); |
If stor = 'G', A is a general sparse matrix, stored using storage-by-rows.
If stor = 'U', A is a symmetric sparse matrix, stored using upper-storage-by-rows.
If stor = 'L', A is a symmetric sparse matrix, stored using lower-storage-by-rows.
Specified as: a single character. It must be 'G', 'U', or 'L'.
If init = 'I', the preconditioning matrix is computed, the internal representation of the sparse matrix is generated, and the iteration procedure is performed. The coefficient matrix and preconditioner in internal format are saved in aux1.
If init = 'S', the iteration procedure is performed using the coefficient matrix and the preconditioner in internal format, stored in aux1, created in a preceding call to this subroutine with init = 'I'. You use this option to solve the same matrix for different right-hand sides, b, optimizing your performance. As long as you do not change the coefficient matrix and preconditioner in aux1, any number of calls can be made with init = 'S'.
Specified as: a single character. It must be 'I' or 'S'.
If IPARM(1) > 0, IPARM(1) is the maximum number of iterations allowed.
If IPARM(1) = 0, the following default values are used:
If IPARM(2) = 1, the conjugate gradient (CG) method is used. Note that this algorithm should only be used with positive definite symmetric matrices.
If IPARM(2) = 2, the conjugate gradient squared (CGS) method is used.
If IPARM(2) = 3, the generalized minimum residual (GMRES) method, restarted after k steps, is used.
If IPARM(2) = 4, the more smoothly converging variant of the CGS method (Bi-CGSTAB) is used.
If IPARM(2) = 5, the transpose-free quasi-minimal residual method (TFQMR) is used.
If IPARM(2) <> 3, then IPARM(3) is not used.
If IPARM(2) = 3, then IPARM(3) = k, where k is the number of steps after which the generalized minimum residual method is restarted. A value for k in the range of 5 to 10 is suitable for most problems.
If IPARM(4) = 1, the system is not preconditioned.
If IPARM(4) = 2, the system is preconditioned by a diagonal matrix.
If IPARM(4) = 3, the system is preconditioned by SSOR splitting with the diagonal given by the absolute values sum of the input matrix.
If IPARM(4) = 4, the system is preconditioned by an incomplete LU factorization.
If IPARM(4) = 5, the system is preconditioned by SSOR splitting with the diagonal given by the incomplete LU factorization.
If IPARM(5) = 1, the iterative method is stopped when:
If IPARM(5) = 2, the iterative method is stopped when:
If IPARM(5) = 3, the iterative method is stopped when:
Specified as: an array of (at least) length 6, containing fullword integers, where:
RPARM(1) is the relative accuracy epsilon used in the stopping criterion. See Notes.
RPARM(2), see On Return.
RPARM(3) has the following meaning, where:
Specified as: a one-dimensional array of (at least) length 3, containing long-precision real numbers, where:
If init = 'I', the working storage is computed. It can contain any values.
If init = 'S', the working storage is used in solving the linear system. It contains the coefficient matrix and preconditioner in internal format, computed in an earlier call to this subroutine.
Specified as: an area of storage, containing naux1 long-precision real numbers.
Specified as: a fullword integer, where:
In these formulas nw has the following value:
If naux2 = 0 and error 2015 is unrecoverable, aux2 is ignored.
Otherwise, it is working storage used by this subroutine that is available for use by the calling program between calls to this subroutine.
Specified as: an area of storage, containing naux2 long-precision real numbers.
If naux2 = 0 and error 2015 is unrecoverable, DSRIS dynamically allocates the work area used by this subroutine. The work area is deallocated before control is returned to the calling program.
Otherwise,
Returned as: a one-dimensional array, containing long-precision real numbers. The number of elements in this array can be determined by subtracting 1 from the value in IA(n+1).
Returned as: a one-dimensional array, containing fullword integers; 1 <= (JA elements) <= n. The number of elements in this array can be determined by subtracting 1 from the value in IA(n+1).
IPARM(1) through IPARM(5) are unchanged.
IPARM(6) contains the number of iterations performed by this subroutine.
Returned as: a one-dimensional array of length 6, containing fullword integers.
RPARM(1) is unchanged.
RPARM(2) contains the estimate of the error of the solution. If the process converged, RPARM(2) <= epsilon.
RPARM(3) is unchanged.
Returned as: a one-dimensional array of length 3, containing long-precision real numbers.
In some cases, you can specify a different algorithm in IPARM(2) when making calls with init = 'S'. (See Example 2.) However, DSRIS sometimes needs different information in aux1 for different algorithms. When this occurs, DSRIS issues an attention message, continues processing the computation, and then resets the contents of aux1. Your performance is not improved in this case, which is functionally equivalent to calling DSRIS with init = 'I'.
For the stopping criteria specified in IPARM(5), the relative accuracy epsilon (in RPARM(1)) must be specified reasonably (10-4 to 10-8). If you specify a larger epsilon, the algorithm takes fewer iterations to converge to a solution. If you specify a smaller epsilon, the algorithm requires more iterations and computer time, but converges to a more precise solution. If the value you specify is unreasonably small, the algorithm may fail to converge within the number of iterations it is allowed to perform.
The linear system:
is solved using one of the following methods: conjugate gradient (CG), conjugate gradient squared (CGS), generalized minimum residual (GMRES), more smoothly converging variant of the CGS method (Bi-CGSTAB), or transpose-free quasi-minimal residual method (TFQMR), where:
One of the following preconditioners is used:
See references [36], [56], [82], [86], [89], and [95].
When you call this subroutine to solve a system for the first time, you specify init = 'I'. After that, you can solve the same system any number of times by calling this subroutine each time with init = 'S'. These subsequent calls use the coefficient matrix and preconditioner, stored in internal format in aux1. You optimize performance by doing this, because certain portions of the computation have already been performed.
Error 2015 is unrecoverable, naux2 = 0, and unable to allocate work area.
The following errors, with their corresponding return codes, can occur in this subroutine. For details on error handling, see What Can You Do about ESSL Computational Errors?.
This example finds the solution of the linear system Ax = b for the sparse matrix A, which is stored by rows in arrays AR, IA, and JA. The system is solved using the Bi-CGSTAB algorithm. The iteration is stopped when the norm of the residual is less than the given threshold specified in RPARM(1). The algorithm is allowed to perform 20 iterations. The process converges after 9 iterations. Matrix A is:
* * | 2.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 | | 0.0 2.0 -1.0 0.0 0.0 0.0 0.0 0.0 0.0 | | 0.0 1.0 2.0 0.0 0.0 0.0 0.0 0.0 0.0 | | 1.0 0.0 0.0 2.0 -1.0 0.0 0.0 0.0 0.0 | | 0.0 0.0 0.0 1.0 2.0 -1.0 0.0 0.0 0.0 | | 0.0 0.0 0.0 0.0 1.0 2.0 -1.0 0.0 0.0 | | 0.0 0.0 0.0 0.0 0.0 1.0 2.0 -1.0 0.0 | | 0.0 0.0 0.0 0.0 0.0 0.0 1.0 2.0 -1.0 | | 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 2.0 | * *
STOR INIT N AR JA IA B X IPARM RPARM AUX1 NAUX1 AUX2 NAUX2 | | | | | | | | | | | | | | CALL DSRIS( 'G' , 'I' , 9 , AR , JA , IA , B , X , IPARM , RPARM , AUX1 , 98 , AUX2 , 63 )
AR = (2.0, 2.0, -1.0, 1.0, 2.0, 1.0, 2.0, -1.0, 1.0, 2.0, -1.0, 1.0, 2.0, -1.0, 1.0, 2.0, -1.0, 1.0, 2.0, -1.0, 1.0, 2.0) JA = (1, 2, 3, 2, 3, 1, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9) IA = (1, 2, 4, 6, 9, 12, 15, 18, 21, 23) B = (2.0, 1.0, 3.0, 2.0, 2.0, 2.0, 2.0, 2.0, 3.0) X = (0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0) IPARM(1) = 20 IPARM(2) = 4 IPARM(3) = 0 IPARM(4) = 1 IPARM(5) = 10 RPARM(1) = 1.D-7 RPARM(3) = 1.0
X = (1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0) IPARM(6) = 9 RPARM(2) = 0.29D-16
This example finds the solution of the linear system Ax = b for the same sparse matrix A used in Example 1. It also uses the same right-hand side in b and the same initial guesses in x. However, the system is solved using a different algorithm, conjugate gradient squared (CGS). Because INIT is 'S', the best performance is achieved. The iteration is stopped when the norm of the residual is less than the given threshold specified in RPARM(1). The algorithm is allowed to perform 20 iterations. The process converges after 9 iterations.
STOR INIT N AR JA IA B X IPARM RPARM AUX1 NAUX1 AUX2 NAUX2 | | | | | | | | | | | | | | CALL DSRIS( 'G' , 'S' , 9 , AR , JA , IA , B , X , IPARM , RPARM , AUX1 , 98 , AUX2 , 63 )
X = (1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0) IPARM(6) = 9 RPARM(2) = 0.42D-19
This example finds the solution of the linear system Ax = b for the sparse matrix A, which is stored by rows in arrays AR, IA, and JA. The system is solved using the two-term conjugate gradient method (CG), preconditioned by incomplete LU factorization. The iteration is stopped when the norm of the residual is less than the given threshold specified in RPARM(1). The algorithm is allowed to perform 20 iterations. The process converges after 1 iteration. Matrix A is:
* * | 2.0 0.0 -1.0 0.0 0.0 0.0 0.0 0.0 0.0 | | 0.0 2.0 0.0 -1.0 0.0 0.0 0.0 0.0 0.0 | | -1.0 0.0 2.0 0.0 -1.0 0.0 0.0 0.0 0.0 | | 0.0 -1.0 0.0 2.0 0.0 -1.0 0.0 0.0 0.0 | | 0.0 0.0 -1.0 0.0 2.0 0.0 -1.0 0.0 0.0 | | 0.0 0.0 0.0 -1.0 0.0 2.0 0.0 -1.0 0.0 | | 0.0 0.0 0.0 0.0 -1.0 0.0 2.0 0.0 -1.0 | | 0.0 0.0 0.0 0.0 0.0 -1.0 0.0 2.0 0.0 | | 0.0 0.0 0.0 0.0 0.0 0.0 -1.0 0.0 2.0 | * *
STOR INIT N AR JA IA B X IPARM RPARM AUX1 NAUX1 AUX2 NAUX2 | | | | | | | | | | | | | | CALL DSRIS( 'G' , 'I' , 9 , AR , JA , IA , B , X , IPARM , RPARM , AUX1 , 223 , AUX2 , 36 )
AR = (2.0, -1.0, 2.0, -1.0, -1.0, 2.0, -1.0, -1.0, 2.0, -1.0, -1.0, 2.0, -1.0, -1.0, 2.0, -1.0, -1.0, 2.0, -1.0, -1.0, 2.0, -1.0, 2.0) JA = (1, 3, 2, 4, 1, 3, 5, 2, 4, 6, 3, 5, 7, 4, 6, 8, 5, 7, 9, 6, 8, 7, 9) IA = (1, 3, 5, 8, 11, 14, 17, 20, 22, 24) B = (1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0) X = (0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0) IPARM(1) = 20 IPARM(2) = 1 IPARM(3) = 0 IPARM(4) = 4 IPARM(5) = 1 RPARM(1) = 1.D-7 RPARM(3) = 1.0
X = (1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0) IPARM(6) = 1 RPARM(2) = 0.16D-15
This example finds the solution of the linear system Ax = b for the same sparse matrix A used in Example 3. However, matrix A is stored using upper-storage-by-rows in arrays AR, IA, and JA. The system is solved using the generalized minimum residual (GMRES), restarted after 5 steps and preconditioned with SSOR splitting. The iteration is stopped when the norm of the residual is less than the given threshold specified in RPARM(1). The algorithm is allowed to perform 20 iterations. The process converges after 12 iterations.
STOR INIT N AR JA IA B X IPARM RPARM AUX1 NAUX1 AUX2 NAUX2 | | | | | | | | | | | | | | CALL DSRIS( 'U' , 'I' , 9 , AR , JA , IA , B , X , IPARM , RPARM , AUX1 , 219 , AUX2 , 109 )
AR = (2.0, -1.0, 2.0, -1.0, 2.0, -1.0, 2.0, -1.0, 2.0, -1.0, 2.0, -1.0, 2.0, -1.0, 2.0, 2.0) JA = (1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8, 7, 9, 8, 9) IA = (1, 3, 5, 7, 9, 11, 13, 15, 16, 17) B = (1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0) X = (0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0) IPARM(1) = 20 IPARM(2) = 3 IPARM(3) = 5 IPARM(4) = 3 IPARM(5) = 1 RPARM(1) = 1.D-7 RPARM(3) = 2.0
X = (1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0) IPARM(6) = 12 RPARM(2) = 0.33D-7