NAG Library Routine Document
f01brf (real_gen_sparse_lu)
1
Purpose
f01brf factorizes a real sparse matrix. The routine either forms the $LU$ factorization of a permutation of the entire matrix, or, optionally, first permutes the matrix to block lower triangular form and then only factorizes the diagonal blocks.
2
Specification
Fortran Interface
Subroutine f01brf ( 
n, nz, a, licn, irn, lirn, icn, pivot, ikeep, iw, w, lblock, grow, abort, idisp, ifail) 
Integer, Intent (In)  ::  n, nz, licn, lirn  Integer, Intent (Inout)  ::  irn(lirn), icn(licn), ifail  Integer, Intent (Out)  ::  ikeep(5*n), iw(8*n), idisp(10)  Real (Kind=nag_wp), Intent (In)  ::  pivot  Real (Kind=nag_wp), Intent (Inout)  ::  a(licn)  Real (Kind=nag_wp), Intent (Out)  ::  w(n)  Logical, Intent (In)  ::  lblock, grow, abort(4) 

C Header Interface
#include nagmk26.h
void 
f01brf_ (const Integer *n, const Integer *nz, double a[], const Integer *licn, Integer irn[], const Integer *lirn, Integer icn[], const double *pivot, Integer ikeep[], Integer iw[], double w[], const logical *lblock, const logical *grow, const logical abort[], Integer idisp[], Integer *ifail) 

3
Description
Given a real sparse matrix
$A$,
f01brf may be used to obtain the
$LU$ factorization of a permutation of
$A$,
where
$P$ and
$Q$ are permutation matrices,
$L$ is unit lower triangular and
$U$ is upper triangular. The routine uses a sparse variant of Gaussian elimination, and the pivotal strategy is designed to compromise between maintaining sparsity and controlling loss of accuracy through roundoff.
Optionally the routine first permutes the matrix into block lower triangular form and then only factorizes the diagonal blocks. For some matrices this gives a considerable saving in storage and execution time.
Extensive data checks are made; duplicated nonzeros can be accumulated.
The factorization is intended to be used by
f04axf to solve sparse systems of linear equations
$Ax=b$ or
${A}^{\mathrm{T}}x=b$. If several matrices of the same sparsity pattern are to be factorized,
f01bsf should be used for the second and subsequent matrices.
The method is fully described in
Duff (1977).
A more recent algorithm for the same calculation is provided by
f11mef.
4
References
Duff I S (1977) MA28 – a set of Fortran subroutines for sparse unsymmetric linear equations AERE Report R8730 HMSO
5
Arguments
 1: $\mathbf{n}$ – IntegerInput

On entry: $n$, the order of the matrix $A$.
Constraint:
${\mathbf{n}}>0$.
 2: $\mathbf{nz}$ – IntegerInput

On entry: the number of nonzero elements in the matrix $A$.
Constraint:
${\mathbf{nz}}>0$.
 3: $\mathbf{a}\left({\mathbf{licn}}\right)$ – Real (Kind=nag_wp) arrayInput/Output

On entry: ${\mathbf{a}}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,{\mathbf{nz}}$, must contain the nonzero elements of the sparse matrix $A$. They can be in any order since f01brf will reorder them.
On exit: the nonzero elements in the
$LU$ factorization. The array must
not be changed by you between a call of
f01brf and a call of
f04axf.
 4: $\mathbf{licn}$ – IntegerInput

On entry: the dimension of the arrays
a and
icn as declared in the (sub)program from which
f01brf is called. Since the factorization is returned in
a and
icn,
licn should be large enough to accommodate this and should ordinarily be
$2$ to
$4$ times as large as
nz.
Constraint:
${\mathbf{licn}}\ge {\mathbf{nz}}$.
 5: $\mathbf{irn}\left({\mathbf{lirn}}\right)$ – Integer arrayInput/Output

On entry: ${\mathbf{irn}}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,{\mathbf{nz}}$, must contain the row index of the nonzero element stored in ${\mathbf{a}}\left(i\right)$.
On exit:
irn is overwritten and is not needed for subsequent calls of
f01bsf or
f04axf.
 6: $\mathbf{lirn}$ – IntegerInput

On entry: the dimension of the array
irn as declared in the (sub)program from which
f01brf is called. It need not be as large as
licn; normally it will not need to be very much greater than
nz.
Constraint:
${\mathbf{lirn}}\ge {\mathbf{nz}}$.
 7: $\mathbf{icn}\left({\mathbf{licn}}\right)$ – Integer arrayCommunication Array

${\mathbf{icn}}\left(\mathit{i}\right)$, for
$\mathit{i}=1,2,\dots ,{\mathbf{nz}}$, must contain, on entry, the column index of the nonzero element stored in
${\mathbf{a}}\left(i\right)$.
icn contains, on exit, the column indices of the nonzero elements in the factorization. The array must
not be changed by you between a call of
f01brf and subsequent calls of
f01bsf or
f04axf.
 8: $\mathbf{pivot}$ – Real (Kind=nag_wp)Input

On entry: should have a value in the range
$0.0\le {\mathbf{pivot}}\le 0.9999$ and is used to control the choice of pivots. If
${\mathbf{pivot}}<0.0$, the value
$0.0$ is assumed, and if
${\mathbf{pivot}}>0.9999$, the value
$0.9999$ is assumed. When searching a row for a pivot, any element is excluded which is less than
pivot times the largest of those elements in the row available as pivots. Thus decreasing
pivot biases the algorithm to maintaining sparsity at the expense of stability.
Suggested value:
${\mathbf{pivot}}=0.1$ has been found to work well on test examples.
 9: $\mathbf{ikeep}\left(5\times {\mathbf{n}}\right)$ – Integer arrayCommunication Array

On exit: indexing information about the factorization.
You must
not change
ikeep between a call of
f01brf and subsequent calls to
f01bsf or
f04axf.
 10: $\mathbf{iw}\left(8\times {\mathbf{n}}\right)$ – Integer arrayWorkspace

 11: $\mathbf{w}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: if
${\mathbf{grow}}=\mathrm{.TRUE.}$,
${\mathbf{w}}\left(1\right)$ contains an estimate (an upper bound) of the increase in size of elements encountered during the factorization (see
grow); the rest of the array is used as workspace.
If ${\mathbf{grow}}=\mathrm{.FALSE.}$, the array is not used.
 12: $\mathbf{lblock}$ – LogicalInput

On entry: if ${\mathbf{lblock}}=\mathrm{.TRUE.}$, the matrix is preordered into block lower triangular form before the $LU$ factorization is performed; otherwise the entire matrix is factorized.
Suggested value:
${\mathbf{lblock}}=\mathrm{.TRUE.}$ unless the matrix is known to be irreducible, or is singular and an upper bound on the rank is required.
 13: $\mathbf{grow}$ – LogicalInput

On entry: if
${\mathbf{grow}}=\mathrm{.TRUE.}$, then on exit
${\mathbf{w}}\left(1\right)$ contains an estimate (an upper bound) of the increase in size of elements encountered during the factorization. If the matrix is wellscaled (see
Section 9.2), then a high value for
${\mathbf{w}}\left(1\right)$ indicates that the
$LU$ factorization may be inaccurate and you should be wary of the results and perhaps increase the argument
pivot for subsequent runs (see
Section 7).
Suggested value:
${\mathbf{grow}}=\mathrm{.TRUE.}$.
 14: $\mathbf{abort}\left(4\right)$ – Logical arrayInput

On entry: if
${\mathbf{abort}}\left(1\right)=\mathrm{.TRUE.}$,
f01brf will exit immediately on detecting a structural singularity (one that depends on the pattern of nonzeros) and return
${\mathbf{ifail}}={\mathbf{1}}$; otherwise it will complete the factorization (see
Section 9.3).
If
${\mathbf{abort}}\left(2\right)=\mathrm{.TRUE.}$,
f01brf will exit immediately on detecting a numerical singularity (one that depends on the numerical values) and return
${\mathbf{ifail}}={\mathbf{2}}$; otherwise it will complete the factorization (see
Section 9.3).
If
${\mathbf{abort}}\left(3\right)=\mathrm{.TRUE.}$,
f01brf will exit immediately (with
${\mathbf{ifail}}={\mathbf{5}}$) when the arrays
a and
icn are filled up by the previously factorized, active and unfactorized parts of the matrix; otherwise it continues so that better guidance on necessary array sizes can be given in
${\mathbf{idisp}}\left(6\right)$ and
${\mathbf{idisp}}\left(7\right)$, and will exit with
ifail in the range
$4$ to
$6$. Note that there is always an immediate error exit if the array
irn is too small.
If ${\mathbf{abort}}\left(4\right)=\mathrm{.TRUE.}$, f01brf exits immediately (with ${\mathbf{ifail}}={\mathbf{13}}$) if it finds duplicate elements in the input matrix.
If
${\mathbf{abort}}\left(4\right)=\mathrm{.FALSE.}$,
f01brf proceeds using a value equal to the sum of the duplicate elements. In either case details of each duplicate element are output on the current advisory message unit (see
x04abf), unless suppressed by the value of
ifail on entry.
Suggested values:
 ${\mathbf{abort}}\left(1\right)=\mathrm{.TRUE.}$;
 ${\mathbf{abort}}\left(2\right)=\mathrm{.TRUE.}$;
 ${\mathbf{abort}}\left(3\right)=\mathrm{.FALSE.}$;
 ${\mathbf{abort}}\left(4\right)=\mathrm{.TRUE.}$.
 15: $\mathbf{idisp}\left(10\right)$ – Integer arrayCommunication Array

On exit: contains information about the factorization.
${\mathbf{idisp}}\left(1\right)$ and
${\mathbf{idisp}}\left(2\right)$ indicate the position in arrays
a and
icn of the first and last elements in the
$LU$ factorization of the diagonal blocks. (
${\mathbf{idisp}}\left(2\right)$ gives the number of nonzeros in the factorization.)
${\mathbf{idisp}}\left(1\right)$ and
${\mathbf{idisp}}\left(2\right)$ must not be changed by you between a call of
f01brf and subsequent calls to
f01bsf or
f04axf.
${\mathbf{idisp}}\left(3\right)$ and
${\mathbf{idisp}}\left(4\right)$ monitor the adequacy of ‘elbow room’ in the arrays
irn and
a (and
icn) respectively, by giving the number of times that the data in these arrays has been compressed during the factorization to release more storage. If either
${\mathbf{idisp}}\left(3\right)$ or
${\mathbf{idisp}}\left(4\right)$ is quite large (say greater than
$10$), it will probably pay you to increase the size of the corresponding array(s) for subsequent runs. If either is very low or zero, then you can perhaps save storage by reducing the size of the corresponding array(s).
${\mathbf{idisp}}\left(5\right)$, when ${\mathbf{lblock}}=\mathrm{.FALSE.}$, gives an upper bound on the rank of the matrix; when ${\mathbf{lblock}}=\mathrm{.TRUE.}$, gives an upper bound on the sum of the ranks of the lower triangular blocks.
${\mathbf{idisp}}\left(6\right)$ and
${\mathbf{idisp}}\left(7\right)$ give the minimum size of arrays
irn and
a (and
icn) respectively which would enable a successful run on an identical matrix (but some ‘elbowroom’ should be allowed – see
Section 9).
${\mathbf{idisp}}\left(8\right)$ to
$\left(10\right)$ are only used if
${\mathbf{lblock}}=\mathrm{.TRUE.}$.
 ${\mathbf{idisp}}\left(8\right)$ gives the structural rank of the matrix.
 ${\mathbf{idisp}}\left(9\right)$ gives the number of diagonal blocks.
 ${\mathbf{idisp}}\left(10\right)$ gives the size of the largest diagonal block.
You must
not change
idisp between a call of
f01brf and subsequent calls to
f01bsf or
f04axf.
 16: $\mathbf{ifail}$ – IntegerInput/Output

For this routine, the normal use of
ifail is extended to control the printing of error and warning messages as well as specifying hard or soft failure (see
Section 3.4 in How to Use the NAG Library and its Documentation).
On entry:
ifail must be set to a value with the decimal expansion
$\mathit{cba}$, where each of the decimal digits
$c$,
$b$ and
$a$ must have a value of
$0$ or
$1$.
$a=0$ 
specifies hard failure, otherwise soft failure; 
$b=0$ 
suppresses error messages, otherwise error messages will be printed (see Section 6); 
$c=0$ 
suppresses warning messages, otherwise warning messages will be printed (see Section 6). 
The recommended value for inexperienced users is $110$ (i.e., hard failure with all messages printed).
On exit:
${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see
Section 6).
6
Error Indicators and Warnings
If on entry
${\mathbf{ifail}}=0$ or
$1$, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
 ${\mathbf{ifail}}=2$

Successful factorization of a numerically singular matrix (which may also be structurally singular) (see
Section 9.3).
 ${\mathbf{ifail}}=1$

Successful factorization of a structurally singular matrix (see
Section 9.3).
 ${\mathbf{ifail}}=1$

The matrix is structurally singular and the factorization has been abandoned (${\mathbf{abort}}\left(1\right)$ was .TRUE. on entry).
 ${\mathbf{ifail}}=2$

The matrix is numerically singular and the factorization has been abandoned (${\mathbf{abort}}\left(2\right)$ was .TRUE. on entry).
 ${\mathbf{ifail}}=3$

lirn is too small: there is not enough space in the array
irn to continue the factorization. You are recommended to try again with
lirn (and the length of
irn) equal to at least
${\mathbf{idisp}}\left(6\right)+{\mathbf{n}}/2$.
 ${\mathbf{ifail}}=4$

licn is much too small: there is much too little space in the arrays
a and
icn to continue the factorization.
 ${\mathbf{ifail}}=5$

licn is too small: there is not enough space in the arrays
a and
icn to store the factorization. If
${\mathbf{abort}}\left(3\right)$ was .FALSE. on entry, the factorization has been completed but some of the
$LU$ factors have been discarded to create space;
${\mathbf{idisp}}\left(7\right)$ then gives the minimum value of
licn (i.e., the minimum length of
a and
icn) required for a successful factorization of the same matrix.
 ${\mathbf{ifail}}=6$

licn and
lirn are both too small: effectively this is a combination of
${\mathbf{ifail}}={\mathbf{3}}$ and
${\mathbf{5}}$ (with
${\mathbf{abort}}\left(3\right)=\mathrm{.FALSE.}$).
 ${\mathbf{ifail}}=7$

licn is too small: there is not enough space in the arrays
a and
icn for the permutation to block triangular form.
 ${\mathbf{ifail}}=8$

On entry,  ${\mathbf{n}}\le 0$. 
 ${\mathbf{ifail}}=9$

On entry,  ${\mathbf{nz}}\le 0$. 
 ${\mathbf{ifail}}=10$

On entry,  ${\mathbf{licn}}<{\mathbf{nz}}$. 
 ${\mathbf{ifail}}=11$

On entry,  ${\mathbf{lirn}}<{\mathbf{nz}}$. 
 ${\mathbf{ifail}}=12$

On entry, an element of the input matrix has a row or column index (i.e., an element of
irn or
icn) outside the range
$1$ to
n.
 ${\mathbf{ifail}}=13$

Duplicate elements have been found in the input matrix and the factorization has been abandoned (${\mathbf{abort}}\left(4\right)=\mathrm{.TRUE.}$ on entry).
 ${\mathbf{ifail}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 3.9 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 3.8 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=999$
Dynamic memory allocation failed.
See
Section 3.7 in How to Use the NAG Library and its Documentation for further information.
7
Accuracy
The factorization obtained is exact for a perturbed matrix whose $\left(i,j\right)$th element differs from ${a}_{ij}$ by less than $3\epsilon \rho {m}_{ij}$ where $\epsilon $ is the machine precision, $\rho $ is the growth value returned in ${\mathbf{w}}\left(1\right)$ if ${\mathbf{grow}}=\mathrm{.TRUE.}$, and ${m}_{ij}$ the number of Gaussian elimination operations applied to element $\left(i,j\right)$. The value of ${m}_{ij}$ is not greater than $n$ and is usually much less. Small $\rho $ values therefore guarantee accurate results, but unfortunately large $\rho $ values may give a very pessimistic indication of accuracy.
8
Parallelism and Performance
f01brf is not threaded in any implementation.
The time required may be estimated very roughly from the number
$\tau $ of nonzeros in the factorized form (output as
${\mathbf{idisp}}\left(2\right)$) and for
f01brf and its associates is
f01brf: 
$5{\tau}^{2}/n$ units 
f01bsf: 
${\tau}^{2}/n$ units 
f04axf: 
$2\tau $ units 
where our unit is the time for the inner loop of a full matrix code (e.g., solving a full set of equations takes about
$\frac{1}{3}{n}^{3}$ units). Note that the faster
f01bsf time makes it well worthwhile to use this for a sequence of problems with the same pattern.
It should be appreciated that
$\tau $ varies widely from problem to problem. For network problems it may be little greater than
nz, the number of nonzeros in
$A$; for discretization of twodimensional and threedimensional partial differential equations it may be about
$3n{\mathrm{log}}_{2}n$ and
$\frac{1}{2}{n}^{5/3}$, respectively.
The time taken by f01brf to find the block lower triangular form (${\mathbf{lblock}}=\mathrm{.TRUE.}$) is typically $5\u201315\%$ of the time taken by the routine when it is not found (${\mathbf{lblock}}=\mathrm{.FALSE.}$). If the matrix is irreducible (${\mathbf{idisp}}\left(9\right)=1$ after a call with ${\mathbf{lblock}}=\mathrm{.TRUE.}$) then this time is wasted. Otherwise, particularly if the largest block is small (${\mathbf{idisp}}\left(10\right)\ll n$), the consequent savings are likely to be greater.
The time taken to estimate growth (${\mathbf{grow}}=\mathrm{.TRUE.}$) is typically under $20\%$ of the overall time.
The overall time may be substantially increased if there is inadequate ‘elbowroom’ in the arrays
a,
irn and
icn. When the sizes of the arrays are minimal (
${\mathbf{idisp}}\left(6\right)$ and
${\mathbf{idisp}}\left(7\right)$) it can execute as much as three times slower. Values of
${\mathbf{idisp}}\left(3\right)$ and
${\mathbf{idisp}}\left(4\right)$ greater than about
$10$ indicate that it may be worthwhile to increase array sizes.
The use of a relative pivot tolerance
pivot essentially presupposes that the matrix is wellscaled, i.e., that the matrix elements are broadly comparable in size. Practical problems are often naturally wellscaled but particular care is needed for problems containing mixed types of variables (for example millimetres and neutron fluxes).
It is envisaged that
f01brf will almost always be called for square nonsingular matrices and that singularity indicates an error condition. However, even if the matrix is singular it is possible to complete the factorization. It is even possible for
f04axf to solve a set of equations whose matrix is singular provided the set is consistent.
Two forms of singularity are possible. If the matrix would be singular for any values of the nonzeros (e.g., if it has a whole row of zeros), then we say it is structurally singular, and continue only if ${\mathbf{abort}}\left(1\right)=\mathrm{.FALSE.}$. If the matrix is nonsingular by virtue of the particular values of the nonzeros, then we say that it is numerically singular and continue only if ${\mathbf{abort}}\left(2\right)=\mathrm{.FALSE.}$, in which case an upper bound on the rank of the matrix is returned in ${\mathbf{idisp}}\left(5\right)$ when ${\mathbf{lblock}}=\mathrm{.FALSE.}$.
Rectangular matrices may be treated by setting
n to the larger of the number of rows and numbers of columns and setting
${\mathbf{abort}}\left(1\right)=\mathrm{.FALSE.}$.
Note: the soft
failure option should be used (last digit of ${\mathbf{ifail}}={\mathbf{1}}$) if you wish to factorize singular matrices with ${\mathbf{abort}}\left(1\right)$ or ${\mathbf{abort}}\left(2\right)$ set to .FALSE..
The matrix $A$ may consist of a sum of contributions from different subsystems (for example finite elements). In such cases you may rely on f01brf to perform assembly, since duplicated elements are summed.
The following code may be used to compute the determinant of
$A$ (as the real variable
DET) after a call of
f01brf:
det = 1.0
id = idisp(1)
Do 10 i = 1, n
idg = id + ikeep(3*n+i)
det = det*a(idg)
If (ikeep(n+i).ne.i)det = det
If (ikeep(2*n+i).ne.i)det = det
id = id + ikeep(i)
10 Continue
10
Example
This example factorizes the real sparse matrix:
This example program simply prints out some information about the factorization as returned by
f01brf in
${\mathbf{w}}\left(1\right)$ and
idisp. Normally the call of
f01brf would be followed by a call of
f04axf (see
Section 10 in
f04axf).
10.1
Program Text
Program Text (f01brfe.f90)
10.2
Program Data
Program Data (f01brfe.d)
10.3
Program Results
Program Results (f01brfe.r)