F04 Chapter Contents
F04 Chapter Introduction
NAG Library Manual

NAG Library Routine DocumentF04AXF

Note:  before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

1  Purpose

F04AXF calculates the approximate solution of a set of real sparse linear equations with a single right-hand side, $Ax=b$ or ${A}^{\mathrm{T}}x=b$, where $A$ has been factorized by F01BRF or F01BSF.

2  Specification

 SUBROUTINE F04AXF ( N, A, LICN, ICN, IKEEP, RHS, W, MTYPE, IDISP, RESID)
 INTEGER N, LICN, ICN(LICN), IKEEP(5*N), MTYPE, IDISP(2) REAL (KIND=nag_wp) A(LICN), RHS(N), W(N), RESID

3  Description

To solve a system of real linear equations $Ax=b$ or ${A}^{\mathrm{T}}x=b$, where $A$ is a general sparse matrix, $A$ must first be factorized by F01BRF or F01BSF. F04AXF then computes $x$ by block forward or backward substitution using simple forward and backward substitution within each diagonal block.
The method is fully described in Duff (1977).
A more recent method is available through solver routine F11MFF and factorization routine F11MEF.

4  References

Duff I S (1977) MA28 – a set of Fortran subroutines for sparse unsymmetric linear equations AERE Report R8730 HMSO

5  Parameters

1:     $\mathrm{N}$ – INTEGERInput
On entry: $n$, the order of the matrix $A$.
Constraint: ${\mathbf{N}}\ge 0$.
2:     $\mathrm{A}\left({\mathbf{LICN}}\right)$ – REAL (KIND=nag_wp) arrayInput
On entry: the nonzero elements in the factorization of the matrix $A$, as returned by F01BRF or F01BSF.
3:     $\mathrm{LICN}$ – INTEGERInput
On entry: the dimension of the arrays A and ICN as declared in the (sub)program from which F04AXF is called.
4:     $\mathrm{ICN}\left({\mathbf{LICN}}\right)$ – INTEGER arrayCommunication Array
On entry: the column indices of the nonzero elements of the factorization, as returned by F01BRF or F01BSF.
5:     $\mathrm{IKEEP}\left(5×{\mathbf{N}}\right)$ – INTEGER arrayInput
IKEEP provides, on entry, indexing information about the factorization, as returned by F01BRF or F01BSF. Used as internal workspace prior to being restored and hence is unchanged.
6:     $\mathrm{RHS}\left({\mathbf{N}}\right)$ – REAL (KIND=nag_wp) arrayInput/Output
On entry: the right-hand side vector $b$.
On exit: RHS is overwritten by the solution vector $x$.
7:     $\mathrm{W}\left({\mathbf{N}}\right)$ – REAL (KIND=nag_wp) arrayWorkspace
8:     $\mathrm{MTYPE}$ – INTEGERInput
On entry: MTYPE specifies the task to be performed.
${\mathbf{MTYPE}}=1$
Solve $Ax=b$.
${\mathbf{MTYPE}}\ne 1$
Solve ${A}^{\mathrm{T}}x=b$.
9:     $\mathrm{IDISP}\left(2\right)$ – INTEGER arrayCommunication Array
On entry: the values returned in IDISP by F01BRF.
10:   $\mathrm{RESID}$ – REAL (KIND=nag_wp)Output
On exit: the value of the maximum residual, $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(\left|{b}_{i}-\sum _{j}^{}{a}_{ij}{x}_{j}\right|\right)$, over all the unsatisfied equations, in case F01BRF or F01BSF has been used to factorize a singular or rectangular matrix.

6  Error Indicators and Warnings

If an error is detected in an input parameter F04AXF will act as if a soft noisy exit has been requested (see Section 3.3.4 in the Essential Introduction).

7  Accuracy

The accuracy of the computed solution depends on the conditioning of the original matrix. Since F04AXF is always used with either F01BRF or F01BSF, you are recommended to set ${\mathbf{GROW}}=\mathrm{.TRUE.}$ on entry to these routines and to examine the value of ${\mathbf{W}}\left(1\right)$ on exit (see F01BRF and F01BSF). For a detailed error analysis see page 17 of Duff (1977).
If storage for the original matrix is available then the error can be estimated by calculating the residual
 $r=b-Ax or ​b-ATx$
and calling F04AXF again to find a correction $\delta$ for $x$ by solving
 $Aδ=r or ​ATδ=r.$

8  Parallelism and Performance

Not applicable.

If the factorized form contains $\tau$ nonzeros (${\mathbf{IDISP}}\left(2\right)=\tau$) then the time taken is very approximately $2\tau$ times longer than the inner loop of full matrix code. Some advantage is taken of zeros in the right-hand side when solving ${A}^{\mathrm{T}}x=b$ (${\mathbf{MTYPE}}\ne 1$).

10  Example

This example solves the set of linear equations $Ax=b$ where
 $A= 5 0 0 0 0 0 0 2 -1 2 0 0 0 0 3 0 0 0 -2 0 0 1 1 0 -1 0 0 -1 2 -3 -1 -1 0 0 0 6 and b= 15 12 18 3 -6 0 .$
The nonzero elements of $A$ and indexing information are read in by the program, as described in the document for F01BRF.

10.1  Program Text

Program Text (f04axfe.f90)

10.2  Program Data

Program Data (f04axfe.d)

10.3  Program Results

Program Results (f04axfe.r)