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

naginterfaces.library.sparse.real_gen_precon_bdilu(n, nnz, a, irow, icol, istb, indb, lfill, dtol, milu, ipivp, ipivq, pstrat=None)

real_gen_precon_bdilu computes a block diagonal incomplete $LU$ factorization of a real sparse nonsymmetric matrix, represented in coordinate storage format. The diagonal blocks may be composed of arbitrary rows and the corresponding columns, and may overlap. This factorization can be used to provide a block Jacobi or additive Schwarz preconditioner, for use in combination with real_gen_solve_bdilu() or real_gen_basic_solver().

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

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

Parameters

nint

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

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

istbint, array-like, shape $(\text{nb}+1)$

$istb[\text{b}-1]$, for $\text{b}=1,2,\dots ,\text{nb}$, holds the indices in arrays $indb$, $ipivp$, $ipivq$ and $idiag$ that, on successful exit from this function, define block $\text{b}$. $istb[\text{nb}+1-1]$ holds the sum of the number of rows in all blocks plus $istb\left[0\right]$.

indbint, array-like, shape $\left(\text{lindb}\right)$

$indb$ must hold the row indices appearing in each diagonal block, stored consecutively. Thus the elements $indb\left[istb\right[b-1]-1]$ to $indb\left[istb\right[b]-2]$ are the row indices in the $\text{b}$th block, for $\text{b}=1,2,\dots ,\text{nb}$.

lfillint, array-like, shape $\left(\text{nb}\right)$

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

dtolfloat, array-like, shape $\left(\text{nb}\right)$

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

milustr, length 1, array-like, shape $\left(\text{nb}\right)$

$milu[\text{b}-1]$, for $\text{b}=1,2,\dots ,\text{nb}$, indicates whether or not the factorization in the block should be modified to preserve row-sums (see Further Comments for real_gen_precon_ilu).

$milu[b-1]=\text{'M'}$

The factorization is modified.

$milu[b-1]=\text{'N'}$

The factorization is not modified.

ipivpint, array-like, shape $\left(\text{lindb}\right)$

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

ipivqint, array-like, shape $\left(\text{lindb}\right)$

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

pstratNone or str, length 1, array-like, shape $\left(\text{nb}\right)$, optional

Note: if this argument is None then a default value will be used, determined as follows: $\text{'C'}$.

$pstrat[\text{b}-1]$, for $\text{b}=1,2,\dots ,\text{nb}$, specifies the pivoting strategy to be adopted in the block as follows:

$pstrat[b-1]=\text{'N'}$

No pivoting is carried out.

$pstrat[b-1]=\text{'U'}$

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

$pstrat[b-1]=\text{'P'}$

Partial pivoting by columns for stability is carried out.

$pstrat[b-1]=\text{'C'}$

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

Returns

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

The first $nnz$ entries of $a$ contain the nonzero elements of $A$ and the next $nnzc$ entries contain the elements of the matrices $C_{\text{b}}$, for $\text{b}=1,2,\dots ,\text{nb}$ stored consecutively. Within each block the matrix elements are ordered by increasing row index, and by increasing column index within each row.

irowint, ndarray, shape $\left(\text{la}\right)$

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

icolint, ndarray, shape $\left(\text{la}\right)$

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

ipivpint, ndarray, shape $\left(\text{lindb}\right)$

The row and column indices of the pivot elements, arranged consecutively for each block, as for $indb$. If $ipivp\left[istb\right[b-1]+k-2]=i$ and $ipivq\left[istb\right[b-1]+k-2]=j$, the element in row $i$ and column $j$ of $A_b$ was used as the pivot at elimination stage $k$.

ipivqint, ndarray, shape $\left(\text{lindb}\right)$

The row and column indices of the pivot elements, arranged consecutively for each block, as for $indb$. If $ipivp\left[istb\right[b-1]+k-2]=i$ and $ipivq\left[istb\right[b-1]+k-2]=j$, the element in row $i$ and column $j$ of $A_b$ was used as the pivot at elimination stage $k$.

istrint, ndarray, shape $(\text{lindb}+1)$

$istr\left[istb\right[\text{b}-1]+\text{k}-2]$, gives the index in the arrays $a$, $irow$ and $icol$ of row $\text{k}$ of the matrix $C_{\text{b}}$, for $\text{k}=1,2,\dots ,istb[\text{b}+1-1]-istb[\text{b}-1]$, for $\text{b}=1,2,\dots ,\text{nb}$.

$istr\left[istb\right[\text{nb}]-1]$ contains $nnz+nnzc+1$.

idiagint, ndarray, shape $\left(\text{lindb}\right)$

$idiag\left[istb\right[\text{b}-1]+\text{k}-2]$, gives the index in the arrays $a$, $irow$ and $icol$ of the diagonal element in row $\text{k}$ of the matrix $C_{\text{b}}$, for $\text{k}=1,2,\dots ,istb[\text{b}+1-1]-istb[\text{b}-1]$, for $\text{b}=1,2,\dots ,\text{nb}$.

nnzcint

The sum total number of nonzero elements in the matrices $C_{\text{b}}$, for $\text{b}=1,2,\dots ,\text{nb}$.

npivmint, ndarray, shape $\left(\text{nb}\right)$

If $npivm[b-1]>0$ it gives the number of pivots which were modified during the factorization to ensure that $M_b$ exists.

If $npivm[\text{b}-1]=-1$ no pivot modifications were required, but a local restart occurred (see Further Comments for real_gen_precon_ilu). The quality of the preconditioner will generally depend on the returned values of $npivm[\text{b}-1]$, for $\text{b}=1,2,\dots ,\text{nb}$.

If $npivm[b-1]$ is large, for some block, the preconditioner may not be satisfactory.

In this case it may be advantageous to call real_gen_precon_bdilu again with an increased value of $lfill[b-1]$, a reduced value of $dtol[b-1]$, or $pstrat[b-1]=\text{'C'}$.

Raises

NagValueError

(errno $1$)

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

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

(errno $1$)

On entry, $\text{nb}=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $1\le \text{nb}\le n$.

(errno $1$)

On entry, $istb\left[0\right]=⟨value⟩$.

Constraint: $istb\left[0\right]\ge 1$.

(errno $1$)

On entry, for $b=⟨value⟩$, $istb\left[b\right]=⟨value⟩$ and $istb[b-1]=⟨value⟩$.

Constraint: $istb\left[\text{b}\right]>istb[\text{b}-1]$, for $\text{b}=1,2,\dots ,\text{nb}$.

(errno $1$)

On entry, $indb[⟨value⟩]=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $1\le indb[\text{m}-1]\le n$, for $\text{m}=1,2,\dots ,istb\left[\text{nb}\right]-1$

(errno $1$)

On entry, $\text{lindb}=⟨value⟩$, $istb\left[\text{nb}\right]-1=⟨value⟩$ and $\text{nb}=⟨value⟩$.

Constraint: $\text{lindb}\ge istb\left[\text{nb}\right]-1$.

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 1$.

(errno $1$)

On entry, $nnz=⟨value⟩$.

Constraint: $nnz\ge 1$.

(errno $1$)

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

Constraint: $nnz\le n^2$.

(errno $1$)

On entry, $dtol[⟨value⟩]=⟨value⟩$.

Constraint: $dtol[\text{b}-1]\ge 0.0$, for $\text{b}=1,2,\dots ,\text{nb}$.

(errno $1$)

On entry, $pstrat[⟨value⟩]=⟨value⟩$.

Constraint: $pstrat[b-1]=\text{'N'}$, $\text{'U'}$, $\text{'P'}$ or $\text{'C'}$ for all $b$.

(errno $1$)

On entry, $milu[⟨value⟩]=⟨value⟩$.

Constraint: $milu[b-1]=\text{'M'}$ or $\text{'N'}$ for all $b$.

(errno $2$)

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

Constraint: $1\le irow[\text{i}-1]\le n$, for $\text{i}=1,2,\dots ,nnz$.

(errno $2$)

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

Constraint: $1\le icol[\text{j}-1]\le n$, for $\text{j}=1,2,\dots ,nnz$.

(errno $2$)

On entry, element $⟨value⟩$ of $a$ was out of order.

(errno $2$)

On entry, location $⟨value⟩$ of $(irow,icol)$ was a duplicate.

(errno $3$)

On entry, the user-supplied value of $ipivp$ for block $⟨value⟩$ lies outside its range.

(errno $3$)

On entry, the user-supplied value of $ipivp$ for block $⟨value⟩$ was repeated.

(errno $3$)

On entry, the user-supplied value of $ipivq$ for block $⟨value⟩$ lies outside its range.

(errno $3$)

On entry, the user-supplied value of $ipivq$ for block $⟨value⟩$ was repeated.

(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$.

Notes

real_gen_precon_bdilu computes an incomplete $LU$ factorization (see Meijerink and Van der Vorst (1977) and Meijerink and Van der Vorst (1981)) of the (possibly overlapping) diagonal blocks $A_{\text{b}}$, for $\text{b}=1,2,\dots ,\text{nb}$, of a real sparse nonsymmetric $n\times n$ matrix $A$. The factorization is intended primarily for use as a block Jacobi or additive Schwarz preconditioner (see Saad (1996)), with one of the iterative solvers real_gen_solve_bdilu() and real_gen_basic_solver().

The $\text{nb}$ diagonal blocks need not consist of consecutive rows and columns of $A$, but may be composed of arbitrarily indexed rows, and the corresponding columns, as defined in the arguments $indb$ and $istb$. Any given row or column index may appear in more than one diagonal block, resulting in overlap. Each diagonal block $A_{\text{b}}$, for $\text{b}=1,2,\dots ,\text{nb}$, is factorized as:

$$A_b=M_b+R_b$$

where

$$M_b=P_b{L}_b{D}_b{U}_b{Q}_b$$

and $L_b$ is lower triangular with unit diagonal elements, $D_b$ is diagonal, $U_b$ is upper triangular with unit diagonals, $P_b$ and $Q_b$ are permutation matrices, and $R_b$ is a remainder matrix.

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

The parameter $pstrat[b-1]$ defines the pivoting strategy to be used in block $b$. 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 block 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 matrices $M_{\text{b}}$, for $\text{b}=1,2,\dots ,\text{nb}$, are returned in terms of the CS representations of the matrices

$$C_b=L_b+D_b^{-1}+U_b-2I\text{.}$$

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

Saad, Y, 1996, Iterative Methods for Sparse Linear Systems, PWS Publishing Company, Boston, MA