naginterfaces.library.sparse.real_​symm_​precon_​ichol

naginterfaces.library.sparse.real_symm_precon_ichol(nnz, a, irow, icol, lfill, dtol, mic, dscale, ipiv, pstrat='M')

real_symm_precon_ichol computes an incomplete Cholesky factorization of a real sparse symmetric matrix, represented in symmetric coordinate storage format. This factorization may be used as a preconditioner in combination with real_symm_solve_ichol() or real_symm_basic_solver().

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

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

Parameters

nnzint

The number of nonzero elements in the lower triangular part of the matrix $A$.

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

The nonzero elements in the lower triangular part of 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_symm_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$.

lfillint

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

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

micstr, length 1

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

$mic=\text{'M'}$

The factorization is modified.

$mic=\text{'N'}$

The factorization is not modified.

dscalefloat

The diagonal scaling parameter. All diagonal elements are multiplied by the factor ($1+dscale$) at the start of the factorization. This can be used to ensure that the preconditioner is positive definite. See Choice of Arguments.

ipivint, array-like, shape $\left(n\right)$

If $pstrat=\text{'U'}$, $ipiv[i-1]$ must specify the row index of the diagonal element used as a pivot at elimination stage $i$. Otherwise $ipiv$ need not be initialized.

pstratstr, length 1, optional

Specifies the pivoting strategy to be adopted.

$pstrat=\text{'N'}$

No pivoting is carried out.

$pstrat=\text{'M'}$

Diagonal pivoting aimed at minimizing fill-in is carried out, using the Markowitz strategy.

$pstrat=\text{'U'}$

Diagonal pivoting is carried out according to the user-defined input value of $ipiv$.

Returns

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

The first $nnz$ elements of $a$ contain the nonzero elements of $A$ and the next $nnzc$ elements contain the elements of the lower triangular matrix $C$. 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$.

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

The pivot indices. If $ipiv[i-1]=j$ then the diagonal element in row $j$ was used as the pivot at elimination stage $i$.

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.

nnzcint

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

npivmint

The number of pivots which were modified during the factorization to ensure that $M$ was positive definite. 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_symm_precon_ichol again with an increased value of either $lfill$ or $dscale$. See also Further Comments.

Raises

NagValueError

(errno $1$)

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

Constraint: $nnz\le n\times (n+1)/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, $pstrat\ne \text{'N'}$, $\text{'U'}$ or $\text{'M'}$: $pstrat=⟨value⟩$.

(errno $1$)

On entry, $mic\ne \text{'M'}$ or $\text{'N'}$: $mic=⟨value⟩$.

(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 ($irow[\text{I}-1],icol[\text{I}-1]$) is a duplicate: $\text{I}=⟨value⟩$.

(errno $2$)

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

(errno $2$)

On entry, $\text{I}=⟨value⟩$, $icol[\text{I}-1]=⟨value⟩$ and $irow[\text{I}-1]=⟨value⟩$.

Constraint: $icol[\text{I}-1]\ge 1$ and $icol[\text{I}-1]\le irow[\text{I}-1]$.

(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 $ipiv$ is repeated.

(errno $3$)

On entry, a user-supplied value of $ipiv$ 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 setting $pstrat=\text{'M'}$, reducing $lfill$, or increasing $dtol$.

(errno $5$)

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

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_symm_precon_ichol computes an incomplete Cholesky factorization (see Meijerink and Van der Vorst (1977)) of a real sparse symmetric $n\times n$ matrix $A$. It is designed specifically for positive definite matrices, but may also work for some mildly indefinite cases. The factorization is intended primarily for use as a preconditioner with one of the symmetric iterative solvers real_symm_solve_ichol() or real_symm_basic_solver().

The decomposition is written in the form

$$A=M+R$$

where

$$M=PLD{L}^T{P}^T$$

and $P$ is a permutation matrix, $L$ is lower triangular with unit diagonal elements, $D$ is diagonal 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 factorization may be modified in order to preserve row sums, and the diagonal elements may be perturbed to ensure that the preconditioner is positive definite. Diagonal pivoting may optionally be employed, either with a user-defined ordering, or using the Markowitz strategy (see Markowitz (1957)), which aims to minimize fill-in. For further details see Further Comments.

The sparse matrix $A$ is represented in symmetric coordinate storage (SCS) format (see the F11 Introduction). The array $a$ stores all the nonzero elements of the lower triangular part of $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 SCS representation of the lower triangular matrix

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

References

Chan, T F, 1991, Fourier analysis of relaxed incomplete factorization preconditioners, SIAM J. Sci. Statist. Comput. (12(2)), 668–680

Markowitz, H M, 1957, The elimination form of the inverse and its application to linear programming, Management Sci. (3), 255–269

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

Salvini, S A and Shaw, G J, 1995, An evaluation of new NAG Library solvers for large sparse symmetric linear systems, NAG Technical Report TR1/95

Van der Vorst, H A, 1990, The convergence behaviour of preconditioned CG and CG-S in the presence of rounding errors, Lecture Notes in Mathematics, (eds O Axelsson and L Y Kolotilina) (1457), Springer–Verlag