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(5n), iw(8n), 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 <nag.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)

The routine may be called by the names f01brf or nagf_matop_real_gen_sparse_lu.

3 Description

Given a real sparse matrix

A

, f01brf may be used to obtain the

L U

factorization of a permutation of

A

P A Q = L U

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 round-off.

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

A x = b

A^{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: $n$ – Integer Input

On entry:

n

, the order of the matrix

A

Constraint:

n > 0

2: $nz$ – Integer Input

On entry: the number of nonzero elements in the matrix

A

Constraint:

nz > 0

3: $a (licn)$ – Real (Kind=nag_wp) array Input/Output

On entry:

a (i)

, for

i = 1, 2, \dots, 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

L U

factorization. The array must not be changed by you between a call of f01brf and a call of f04axf.

4: $licn$ – Integer Input

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

4

times as large as nz.

Constraint:

licn \geq nz

5: $irn (lirn)$ – Integer array Input/Output

On entry:

irn (i)

, for

i = 1, 2, \dots, nz

, must contain the row index of the nonzero element stored in

a (i)

On exit: irn is overwritten and is not needed for subsequent calls of f01bsf or f04axf.

6: $lirn$ – Integer Input

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:

lirn \geq nz

7: $icn (licn)$ – Integer array Communication Array

On entry:

icn (i)

, for

i = 1, 2, \dots, nz

, must contain the column index of the nonzero element stored in

a (i)

On exit: icn contains 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: $pivot$ – Real (Kind=nag_wp) Input

On entry: should have a value in the range

0.0 \leq pivot \leq 0.9999

and is used to control the choice of pivots. If

pivot < 0.0

, the value

0.0

is assumed, and if

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:

pivot = 0.1

has been found to work well on test examples.

9: $ikeep (5 \times n)$ – Integer array Communication 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: $iw (8 \times n)$ – Integer array Workspace

11: $w (n)$ – Real (Kind=nag_wp) array Output

On exit: if

grow = .TRUE.

w (1)

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.

grow = .FALSE.

, the array is not used.

12: $lblock$ – Logical Input

On entry: if

lblock = .TRUE.

, the matrix is preordered into block lower triangular form before the

L U

factorization is performed; otherwise the entire matrix is factorized.

Suggested value:

lblock = .TRUE.

unless the matrix is known to be irreducible, or is singular and an upper bound on the rank is required.

13: $grow$ – Logical Input

On entry: if

grow = .TRUE.

, then on exit

w (1)

contains an estimate (an upper bound) of the increase in size of elements encountered during the factorization. If the matrix is well-scaled (see Section 9.2), then a high value for

w (1)

indicates that the

L U

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:

grow = .TRUE.

14: $abort (4)$ – Logical array Input

On entry: if

abort (1) = .TRUE.

, f01brf will exit immediately on detecting a structural singularity (one that depends on the pattern of nonzeros) and return

ifail = 1

; otherwise it will complete the factorization (see Section 9.3).

abort (2) = .TRUE.

, f01brf will exit immediately on detecting a numerical singularity (one that depends on the numerical values) and return

ifail = 2

; otherwise it will complete the factorization (see Section 9.3).

abort (3) = .TRUE.

, f01brf will exit immediately (with

ifail = 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

idisp (6)

and

idisp (7)

, and will exit with ifail in the range

4

6

. Note that there is always an immediate error exit if the array irn is too small.

abort (4) = .TRUE.

, f01brf exits immediately (with

ifail = 13

) if it finds duplicate elements in the input matrix.

abort (4) = .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:

$abort (1) = .TRUE.$ ;
$abort (2) = .TRUE.$ ;
$abort (3) = .FALSE.$ ;
$abort (4) = .TRUE.$ .

15: $idisp (10)$ – Integer array Communication Array

On exit: contains information about the factorization.

idisp (1)

and

idisp (2)

indicate the position in arrays a and icn of the first and last elements in the

L U

factorization of the diagonal blocks. (

idisp (2)

gives the number of nonzeros in the factorization.)

idisp (1)

and

idisp (2)

must not be changed by you between a call of f01brf and subsequent calls to f01bsf or f04axf.

idisp (3)

and

idisp (4)

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

idisp (3)

idisp (4)

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).

idisp (5)

, when

lblock = .FALSE.

, gives an upper bound on the rank of the matrix; when

lblock = .TRUE.

, gives an upper bound on the sum of the ranks of the lower triangular blocks.

idisp (6)

and

idisp (7)

give the minimum size of arrays irn and a (and icn) respectively which would enable a successful run on an identical matrix (but some ‘elbow-room’ should be allowed – see Section 9).

idisp (8)

(10)

are only used if

lblock = .TRUE.

$idisp (8)$ gives the structural rank of the matrix.
$idisp (9)$ gives the number of diagonal blocks.
$idisp (10)$ 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: $ifail$ – Integer Input/Output

This routine uses an ifail input value codification that differs from the normal case to distinguish between errors and warnings (see Section 4 in the Introduction to the NAG Library FL Interface).

On entry: ifail must be set to one of the values below to set behaviour on detection of an error; these values have no effect when no error is detected. The behaviour relate to whether or not program execution is halted and whether or not messages are printed when an error or warning is detected.

ifail	Execution	Error Printing	Warning Printed
$0$	halted	No	No
$1$	continue	No	No
$10$	halted	Yes	No
$11$	continue	Yes	No
$100$	halted	No	Yes
$101$	continue	No	Yes
$110$	halted	Yes	Yes
$111$	continue	Yes	Yes

For environments where it might be inappropriate to halt program execution when an error is detected, the value

1

11

101

111

is recommended. If the printing of messages is undesirable, then the value

1

is recommended. Otherwise, the recommended value is

110

. When the value $1$ , $11$ , $101$ or $111$ is used it is essential to test the value of ifail on exit.

On exit:

ifail = 0

unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry

ifail = 0

- 1

, explanatory error messages are output on the current error message unit (as defined by x04aaf).

Errors or warnings detected by the routine:

$ifail = 1$: Matrix is structurally singular – decomposition aborted.

Matrix is structurally singular – decomposition aborted $RANK = ⟨ value ⟩$ .

$ifail = 2$: Matrix is numerically singular – decomposition aborted.

$ifail = 3$: lirn too small. Decomposition aborted at stage $⟨ value ⟩$ in block $⟨ value ⟩$ with first row $⟨ value ⟩$ and last row $⟨ value ⟩$ .

lirn too small. Decomposition aborted at stage $⟨ value ⟩$ in block $⟨ value ⟩$ with first row $⟨ value ⟩$ and last row $⟨ value ⟩$ . To continue set lirn to at least $⟨ value ⟩$ .

$ifail = 4$: licn much too small. Decomposition aborted at stage $⟨ value ⟩$ in block $⟨ value ⟩$ with first row $⟨ value ⟩$ and last row $⟨ value ⟩$ .

licn much too small. Decomposition aborted at stage $⟨ value ⟩$ in block $⟨ value ⟩$ with first row $⟨ value ⟩$ and last row $⟨ value ⟩$ . To continue set licn to at least $⟨ value ⟩$ .

$ifail = 5$: licn too small. Decomposition aborted at stage $⟨ value ⟩$ in block $⟨ value ⟩$ with first row $⟨ value ⟩$ and last row $⟨ value ⟩$ .

licn too small. Decomposition aborted at stage $⟨ value ⟩$ in block $⟨ value ⟩$ with first row $⟨ value ⟩$ and last row $⟨ value ⟩$ . To continue set licn to at least $⟨ value ⟩$ .

licn too small. For successful decomposition set licn to at least $⟨ value ⟩$ .

$ifail = 6$: licn and lirn too small. Decomposition aborted at stage $⟨ value ⟩$ in block $⟨ value ⟩$ with first row $⟨ value ⟩$ and last row $⟨ value ⟩$ .

licn and lirn too small. Decomposition aborted at stage $⟨ value ⟩$ in block $⟨ value ⟩$ with first row $⟨ value ⟩$ and last row $⟨ value ⟩$ . To continue set lirn to at least $⟨ value ⟩$ .

$ifail = 7$: licn not big enough for permutation – increase by $⟨ value ⟩$ .

$ifail = 8$: On entry, $n = ⟨ value ⟩$ .
Constraint: $n > 0$ .

$ifail = 9$: On entry, $nz = ⟨ value ⟩$ .
Constraint: $nz > 0$ .

$ifail = 10$: On entry, $licn = ⟨ value ⟩$ and $nz = ⟨ value ⟩$ .
Constraint: $licn \geq nz$ .

$ifail = 11$: On entry, $lirn = ⟨ value ⟩$ and $nz = ⟨ value ⟩$ .
Constraint: $lirn \geq nz$ .

$ifail = 12$: On entry, $irn (I)$ or $icn (I)$ is out of range: $I = ⟨ value ⟩$ , $a (I) = ⟨ value ⟩$ $irn (I) = ⟨ value ⟩$ , $icn (I) = ⟨ value ⟩$ .

$ifail = 13$: On entry, duplicate elements found – see advisory messages.

$ifail = - 1$: Matrix is structurally singular – decomposition completed.

$ifail = - 2$: Matrix is numerically singular – decomposition completed.

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.

$ifail = - 999$: Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

The factorization obtained is exact for a perturbed matrix whose

(i, j)

th element differs from

a_{i j}

by less than

3 ε ρ m_{i j}

where

ε

is the machine precision,

ρ

is the growth value returned in

w (1)

grow = .TRUE.

, and

m_{i j}

the number of Gaussian elimination operations applied to element

(i, j)

. The value of

m_{i j}

is not greater than

n

and is usually much less. Small

ρ

values, therefore, guarantee accurate results, but unfortunately large

ρ

values may give a very pessimistic indication of accuracy.

8 Parallelism and Performance

f01brf is not threaded in any implementation.

9 Further Comments

9.1 Timing

The time required may be estimated very roughly from the number

τ

of nonzeros in the factorized form (output as

idisp (2)

) and for f01brf and its associates is

f01brf:	$5 τ^{2} / n$ units
f01bsf:	$τ^{2} / n$ units
f04axf:	$2 τ$ 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

τ

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 two-dimensional and three-dimensional partial differential equations it may be about

3 n \log_{2} n

and

\frac{1}{2} n^{5 / 3}

, respectively.

The time taken by f01brf to find the block lower triangular form (

lblock = .TRUE.

) is typically

5 - 15 %

of the time taken by the routine when it is not found (

lblock = .FALSE.

). If the matrix is irreducible (

idisp (9) = 1

after a call with

lblock = .TRUE.

) then this time is wasted. Otherwise, particularly if the largest block is small (

idisp (10) ≪ n

), the consequent savings are likely to be greater.

The time taken to estimate growth (

grow = .TRUE.

) is typically under

20 %

of the overall time.

The overall time may be substantially increased if there is inadequate ‘elbow-room’ in the arrays a, irn and icn. When the sizes of the arrays are minimal (

idisp (6)

and

idisp (7)

) it can execute as much as three times slower. Values of

idisp (3)

and

idisp (4)

greater than about

10

indicate that it may be worthwhile to increase array sizes.

9.2 Scaling

The use of a relative pivot tolerance pivot essentially presupposes that the matrix is well-scaled, i.e., that the matrix elements are broadly comparable in size. Practical problems are often naturally well-scaled but particular care is needed for problems containing mixed types of variables (for example millimetres and neutron fluxes).

9.3 Singular and Rectangular Systems

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

abort (1) = .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

abort (2) = .FALSE.

, in which case an upper bound on the rank of the matrix is returned in

idisp (5)

when

lblock = .FALSE.

Rectangular matrices may be treated by setting n to the larger of the number of rows and numbers of columns and setting

abort (1) = .FALSE.

Note: the soft failure option should be used (last digit of

ifail = 1

) if you wish to factorize singular matrices with

abort (1)

abort (2)

set to .FALSE..

9.4 Duplicated Nonzeros

The matrix

A

may consist of a sum of contributions from different sub-systems (for example finite elements). In such cases you may rely on f01brf to perform assembly, since duplicated elements are summed.

9.5 Determinant

To compute the determinant of

A

after a call of f01brf, the following code may be used to

   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

the real variable det will then hold the determinant.

10 Example

This example factorizes the real sparse matrix:

(\begin{array}{r} 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 \end{array}) .

This example program simply prints out some information about the factorization as returned by f01brf in

w (1)

and idisp. Normally the call of f01brf would be followed by a call of f04axf (see f04axf).

f01br: FL CL CPP AD

NAG FL Interfacef01brf (real_​gen_​sparse_​lu)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

9.1 Timing

9.2 Scaling

9.3 Singular and Rectangular Systems

9.4 Duplicated Nonzeros

9.5 Determinant

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG FL Interface
f01brf (real_gen_sparse_lu)