naginterfaces.library.matop.real_​gen_​sparse_​lu

naginterfaces.library.matop.real_gen_sparse_lu(n, nz, warnlev, errlev, a, irn, icn, abort, pivot=0.1, lblock=True, grow=True, io_manager=None)

real_gen_sparse_lu factorizes a real sparse matrix. The function 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.

For full information please refer to the NAG Library document for f01br

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/f01/f01brf.html

Parameters

nint

$n$, the order of the matrix $A$.

nzint

The number of nonzero elements in the matrix $A$.

warnlevint

Setting $warnlev=0$ disables output of warning messages during the process of the computation. Setting $warnlev=1$ enables these messages.

errlevint

Setting $errlev=0$ disables output of error messages during the process of the computation. Setting $errlev=1$ enables these messages.

afloat, array-like, shape $\left(\text{licn}\right)$

$a[\text{i}-1]$, for $\text{i}=1,2,\dots ,nz$, must contain the nonzero elements of the sparse matrix $A$. They can be in any order since real_gen_sparse_lu will reorder them.

irnint, array-like, shape $\left(\text{lirn}\right)$

$irn[\text{i}-1]$, for $\text{i}=1,2,\dots ,nz$, must contain the row index of the nonzero element stored in $a[i-1]$.

icnint, array-like, shape $\left(\text{licn}\right)$

$icn[\text{i}-1]$, for $\text{i}=1,2,\dots ,nz$, must contain the column index of the nonzero element stored in $a[i-1]$.

abortbool, array-like, shape $\left(4\right)$

If $abort\left[0\right]=True$, real_gen_sparse_lu will exit immediately on detecting a structural singularity (one that depends on the pattern of nonzeros) and return $errno$ = 1; otherwise it will complete the factorization (see Singular and Rectangular Systems).

If $abort\left[1\right]=True$, real_gen_sparse_lu will exit immediately on detecting a numerical singularity (one that depends on the numerical values) and return $errno$ = 2; otherwise it will complete the factorization (see Singular and Rectangular Systems).

If $abort\left[2\right]=True$, real_gen_sparse_lu will exit immediately (with $errno$ = 5) when the arrays $a$ and $comm$[‘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 $comm{[}^{\prime }idis{p}^{\prime }\left]\right[5]$ and $comm{[}^{\prime }idis{p}^{\prime }\left]\right[6]$, and will exit with $\text{errno}$ in the range $4$ to $6$.

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

If $abort\left[3\right]=True$, real_gen_sparse_lu exits immediately (with $errno$ = 13) if it finds duplicate elements in the input matrix.

If $abort\left[3\right]=False$, real_gen_sparse_lu proceeds using a value equal to the sum of the duplicate elements.

In either case details of each duplicate element are output on the file object associated with the advisory I/O unit (see FileObjManager), unless suppressed by the value of $\text{errno}$ on entry.

Suggested value:

$abort\left[0\right]=True$

$abort\left[1\right]=True$

$abort\left[2\right]=False$

$abort\left[3\right]=True$

pivotfloat, optional

Should have a value in the range $0.0\le pivot\le 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.

lblockbool, optional

If $lblock=True$, the matrix is preordered into block lower triangular form before the $LU$ factorization is performed; otherwise the entire matrix is factorized.

growbool, optional

If $grow=True$, then on exit $increase$ contains an estimate (an upper bound) of the increase in size of elements encountered during the factorization. If the matrix is well-scaled (see Further Comments), then a high value for $increase$ 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 Accuracy).

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

afloat, ndarray, shape $\left(\text{licn}\right)$

The nonzero elements in the $LU$ factorization. The array must not be changed by you between a call of real_gen_sparse_lu and a call of linsys.real_sparse_fac_solve.

irnint, ndarray, shape $\left(\text{lirn}\right)$

$irn$ is overwritten and is not needed for subsequent calls of real_gen_sparse_lu_reuse() or linsys.real_sparse_fac_solve.

commdict, communication object

Information about the factorization for subsequent communication to real_gen_sparse_lu_reuse() or linsys.real_sparse_fac_solve.

increaseNone or float

If $grow=True$, $increase$ contains an estimate (an upper bound) of the increase in size of elements encountered during the factorization (see $grow$).

Raises

NagValueError

(errno $1$)

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

(errno $1$)

Matrix is structurally singular – decomposition aborted.

(errno $2$)

Matrix is numerically singular – decomposition aborted.

(errno $3$)

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

(errno $3$)

$\text{lirn}$ too small. Decomposition aborted at stage $⟨value⟩$ in block $⟨value⟩$ with first row $⟨value⟩$ and last row $⟨value⟩$.

(errno $4$)

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

(errno $4$)

$\text{licn}$ much too small. Decomposition aborted at stage $⟨value⟩$ in block $⟨value⟩$ with first row $⟨value⟩$ and last row $⟨value⟩$.

(errno $5$)

$\text{licn}$ too small. Decomposition aborted at stage $⟨value⟩$ in block $⟨value⟩$ with first row $⟨value⟩$ and last row $⟨value⟩$.

(errno $5$)

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

(errno $5$)

$\text{licn}$ too small. For successful decomposition set $\text{licn}$ to at least $⟨value⟩$.

(errno $6$)

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

(errno $6$)

$\text{licn}$ and $\text{lirn}$ too small. Decomposition aborted at stage $⟨value⟩$ in block $⟨value⟩$ with first row $⟨value⟩$ and last row $⟨value⟩$.

(errno $7$)

$\text{licn}$ not big enough for permutation – increase by $⟨value⟩$.

(errno $8$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $9$)

On entry, $nz=⟨value⟩$.

Constraint: $nz>0$.

(errno $10$)

On entry, $\text{licn}=⟨value⟩$ and $nz=⟨value⟩$.

Constraint: $\text{licn}\ge nz$.

(errno $11$)

On entry, $\text{lirn}=⟨value⟩$ and $nz=⟨value⟩$.

Constraint: $\text{lirn}\ge nz$.

(errno $12$)

On entry, $irn[I-1]$ or $icn[I-1]$ is out of range: $I=⟨value⟩$, $a[I-1]=⟨value⟩$ $irn[I-1]=⟨value⟩$, $icn[I-1]=⟨value⟩$.

(errno $13$)

On entry, duplicate elements found – see advisory messages.

(errno $14$)

On entry, $warnlev=⟨value⟩$.

Constraint: $warnlev=0$ or $1$.

(errno $15$)

On entry, $errlev=⟨value⟩$.

Constraint: $errlev=0$ or $1$.

Warns

NagAlgorithmicWarning

(errno $-2$)

Matrix is numerically singular – decomposition completed.

(errno $-1$)

Matrix is structurally singular – decomposition completed.

Notes

No equivalent traditional C interface for this routine exists in the NAG Library.

Given a real sparse matrix $A$, real_gen_sparse_lu may be used to obtain the $LU$ factorization of a permutation of $A$,

$$PAQ=LU$$

where $P$ and $Q$ are permutation matrices, $L$ is unit lower triangular and $U$ is upper triangular. The function 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 function 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 linsys.real_sparse_fac_solve to solve sparse systems of linear equations $Ax=b$ or $A^{T}x=b$. If several matrices of the same sparsity pattern are to be factorized, real_gen_sparse_lu_reuse() 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 sparse.direct_real_gen_lu.

References

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