naginterfaces.library.sparse.real_​gen_​precon_​ilu

naginterfaces.library.sparse.real_gen_precon_ilu(nnz, a, irow, icol, n=None, lfill=0, dtol=0.0, pstrat='C', milu='N', ipivp=None, ipivq=None)

real_gen_precon_ilu computes an incomplete $LU$ factorization of a real sparse nonsymmetric matrix, represented in coordinate storage format. This factorization may be used as a preconditioner in combination with real_gen_solve_ilu() or real_gen_basic_solver().

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

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/f11/f11daf.html

Parameters

nnzint

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

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

The nonzero elements in the matrix $A$, ordered by increasing row index, and by increasing column index within each row. Multiple entries for the same row and column indices are not permitted. The function real_gen_sort() may be used to order the elements in this way.

irowint, array-like, shape $\left(\text{la}\right)$

The row indices of the nonzero elements supplied in $a$.

icolint, array-like, shape $\left(\text{la}\right)$

The column indices of the nonzero elements supplied in $a$.

nNone or int, optional

Note: if this argument is None then a default value will be used, determined as follows: $ipivp.shape\left[0\right]$.

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

lfillint, optional

If $lfill\ge 0$ its value is the maximum level of fill allowed in the decomposition (see Further Comments). A negative value of $lfill$ indicates that $dtol$ will be used to control the fill instead.

dtolfloat, optional

If $lfill<0$, $dtol$ is used as a drop tolerance to control the fill-in (see Further Comments); otherwise $dtol$ is not referenced.

pstratstr, length 1, optional

Specifies the pivoting strategy to be adopted.

$pstrat=\text{'N'}$

No pivoting is carried out.

$pstrat=\text{'U'}$

Pivoting is carried out according to the user-defined input values of $ipivp$ and $ipivq$.

$pstrat=\text{'P'}$

Partial pivoting by columns for stability is carried out.

$pstrat=\text{'C'}$

Complete pivoting by rows for sparsity, and by columns for stability, is carried out.

milustr, length 1, optional

Indicates whether or not the factorization should be modified to preserve row-sums (see Choice of Arguments).

$milu=\text{'M'}$

The factorization is modified.

$milu=\text{'N'}$

The factorization is not modified.

ipivpNone or int, array-like, shape $\left(n\right)$, optional

If $pstrat=\text{'U'}$, $ipivp[k-1]$ and $ipivq[k-1]$ must specify the row and column indices of the element used as a pivot at elimination stage $k$. Otherwise $ipivp$ and $ipivq$ need not be initialized.

ipivqNone or int, array-like, shape $\left(n\right)$, optional

If $pstrat=\text{'U'}$, $ipivp[k-1]$ and $ipivq[k-1]$ must specify the row and column indices of the element used as a pivot at elimination stage $k$. Otherwise $ipivp$ and $ipivq$ need not be initialized.

Returns

afloat, ndarray, shape $(nnz+nnzc)$

The first $nnz$ entries of $a$ contain the nonzero elements of $A$ and the next $nnzc$ entries contain the elements of the matrix $C$. Matrix elements are ordered by increasing row index, and by increasing column index within each row.

irowint, ndarray, shape $(nnz+nnzc)$

The row indices of the nonzero elements returned in $a$.

icolint, ndarray, shape $(nnz+nnzc)$

The column indices of the nonzero elements returned in $a$.

ipivpint, ndarray, shape $\left(n\right)$

The pivot indices. If $ipivp[k-1]=i$ and $ipivq[k-1]=j$ then the element in row $i$ and column $j$ was used as the pivot at elimination stage $k$.

ipivqint, ndarray, shape $\left(n\right)$

The pivot indices. If $ipivp[k-1]=i$ and $ipivq[k-1]=j$ then the element in row $i$ and column $j$ was used as the pivot at elimination stage $k$.

istrint, ndarray, shape $(n+1)$

$istr[\text{i}-1]-1$, for $\text{i}=1,2,\dots ,n$, is the starting address in the arrays $a$, $irow$ and $icol$ of row $i$ of the matrix $C$. $istr\left[n\right]-1$ is the address of the last nonzero element in $C$ plus one.

idiagint, ndarray, shape $\left(n\right)$

$idiag[\text{i}-1]$, for $\text{i}=1,2,\dots ,n$, holds the index of arrays $a$, $irow$ and $icol$ which holds the diagonal element in row $i$ of the matrix $C$.

nnzcint

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

npivmint

If $npivm>0$ it gives the number of pivots which were modified during the factorization to ensure that $M$ exists.

If $npivm=-1$ no pivot modifications were required, but a local restart occurred (see Algorithmic Details).

The quality of the preconditioner will generally depend on the returned value of $npivm$.

If $npivm$ is large the preconditioner may not be satisfactory.

In this case it may be advantageous to call real_gen_precon_ilu again with an increased value of $lfill$, a reduced value of $dtol$, or set $pstrat=\text{'C'}$.

See also Further Comments.

Raises

NagValueError

(errno $1$)

On entry, $nnz=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $nnz\le n^2$.

(errno $1$)

On entry, $nnz=⟨value⟩$.

Constraint: $nnz\ge 1$.

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 1$.

(errno $1$)

On entry, $milu=⟨value⟩$.

Constraint: $milu=\text{'M'}$ or $\text{'N'}$.

(errno $1$)

On entry, $pstrat=⟨value⟩$.

Constraint: $pstrat=\text{'N'}$, $\text{'U'}$, $\text{'P'}$ or $\text{'C'}$.

(errno $1$)

On entry, $dtol=⟨value⟩$.

Constraint: $dtol\ge 0.0$.

(errno $1$)

On entry, $\text{la}=⟨value⟩$ and $nnz=⟨value⟩$.

Constraint: $\text{la}\ge 2\times nnz$.

(errno $2$)

On entry, the location $\left(irow\right[i-1],icol[i-1\left]\right)$ is a duplicate: $i=⟨value⟩$.

(errno $2$)

On entry, $a[i-1]$ is out of order: $i=⟨value⟩$.

(errno $2$)

On entry, $i=⟨value⟩$, $icol[i-1]=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $icol[i-1]\ge 1$ and $icol[i-1]\le n$.

(errno $2$)

On entry, $i=⟨value⟩$, $irow[i-1]=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $irow[i-1]\ge 1$ and $irow[i-1]\le n$.

(errno $3$)

On entry, a user-supplied value of $ipivq$ is repeated.

(errno $3$)

On entry, a user-supplied value of $ipivq$ lies outside the range $[1,n]$.

(errno $3$)

On entry, a user-supplied value of $ipivp$ is repeated.

(errno $3$)

On entry, a user-supplied value of $ipivp$ lies outside the range $[1,n]$.

(errno $4$)

The number of nonzero entries in the decomposition is too large. The decomposition has been terminated before completion. Either increase $\text{la}$, or reduce the fill by reducing $lfill$, or increasing $dtol$.

(errno $5$)

A serious error has occurred in an internal call to an auxiliary function. Check all function calls and array sizes. Seek expert help.

(errno $14$)

Either $n$ or the pair $ipivp$ and $ipivq$, and not all three, must be provided.

Notes

In the NAG Library the traditional C interface for this routine uses a different algorithmic base. Please contact NAG if you have any questions about compatibility.

real_gen_precon_ilu computes an incomplete $LU$ factorization (see Meijerink and Van der Vorst (1977) and Meijerink and Van der Vorst (1981)) of a real sparse nonsymmetric $n\times n$ matrix $A$. The factorization is intended primarily for use as a preconditioner with one of the iterative solvers real_gen_solve_ilu() or real_gen_basic_solver().

The decomposition is written in the form

$$A=M+R$$

where

$$M=PLDUQ$$

and $L$ is lower triangular with unit diagonal elements, $D$ is diagonal, $U$ is upper triangular with unit diagonals, $P$ and $Q$ are permutation matrices, and $R$ is a remainder matrix.

The amount of fill-in occurring in the factorization can vary from zero to complete fill, and can be controlled by specifying either the maximum level of fill $lfill$, or the drop tolerance $dtol$.

The argument $pstrat$ defines the pivoting strategy to be used. The options currently available are no pivoting, user-defined pivoting, partial pivoting by columns for stability, and complete pivoting by rows for sparsity and by columns for stability. The factorization may optionally be modified to preserve the row-sums of the original matrix.

The sparse matrix $A$ is represented in coordinate storage (CS) format (see the F11 Introduction). The array $a$ stores all the nonzero elements of the matrix $A$, while arrays $irow$ and $icol$ store the corresponding row and column indices respectively. Multiple nonzero elements may not be specified for the same row and column index.

The preconditioning matrix $M$ is returned in terms of the CS representation of the matrix

$$C=L+D^{-1}+U-2I\text{.}$$

Further algorithmic details are given in Algorithmic Details.

References

Meijerink, J and Van der Vorst, H, 1977, An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. Comput. (31), 148–162

Meijerink, J and Van der Vorst, H, 1981, Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems, J. Comput. Phys. (44), 134–155

Salvini, S A and Shaw, G J, 1996, An evaluation of new NAG Library solvers for large sparse unsymmetric linear systems, NAG Technical Report TR2/96

See also

naginterfaces.library.examples.sparse.real_gen_basic_solver_ex.main()