NAG Library Function Document
nag_sparse_nsym_precon_bdilu (f11dfc)
1
Purpose
nag_sparse_nsym_precon_bdilu (f11dfc) computes a block diagonal incomplete
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
nag_sparse_nsym_basic_solver (f11bec) or
nag_sparse_nsym_precon_bdilu_solve (f11dgc).
2
Specification
#include <nag.h> |
#include <nagf11.h> |
void |
nag_sparse_nsym_precon_bdilu (Integer n,
Integer nnz,
double a[],
Integer la,
Integer irow[],
Integer icol[],
Integer nb,
const Integer istb[],
const Integer indb[],
Integer lindb,
const Integer lfill[],
const double dtol[],
const Nag_SparseNsym_Piv pstrat[],
const Nag_SparseNsym_Fact milu[],
Integer ipivp[],
Integer ipivq[],
Integer istr[],
Integer idiag[],
Integer *nnzc,
Integer npivm[],
NagError *fail) |
|
3
Description
nag_sparse_nsym_precon_bdilu (f11dfc) computes an incomplete
factorization (see
Meijerink and Van der Vorst (1977) and
Meijerink and Van der Vorst (1981)) of the (possibly overlapping)
diagonal blocks
, for
, of a real sparse nonsymmetric
by
matrix
. The factorization is intended primarily for use as a block Jacobi or additive Schwarz preconditioner (see
Saad (1996)), with one of the iterative solvers
nag_sparse_nsym_basic_solver (f11bec) and
nag_sparse_nsym_precon_bdilu_solve (f11dgc).
The
nb diagonal blocks need not consist of consecutive rows and columns of
, 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
, for
, is factorized as:
where
and
is lower triangular with unit diagonal elements,
is diagonal,
is upper triangular with unit diagonals,
and
are permutation matrices, and
is a remainder matrix.
The amount of fill-in occurring in the factorization of block can vary from zero to complete fill, and can be controlled by specifying either the maximum level of fill , or the drop tolerance .
The parameter defines the pivoting strategy to be used in block . 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
is represented in coordinate storage (CS) format (see
Section 2.1.1 in the f11 Chapter Introduction). The array
a stores all the nonzero elements of the matrix
, 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
, for
, are returned in terms of the CS representations of the matrices
4
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
5
Arguments
- 1:
– IntegerInput
-
On entry: , the order of the matrix .
Constraint:
.
- 2:
– IntegerInput
-
On entry: the number of nonzero elements in the matrix .
Constraint:
.
- 3:
– doubleInput/Output
-
On entry: the nonzero elements in the matrix
, 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
nag_sparse_nsym_sort (f11zac) may be used to order the elements in this way.
On exit: the first
nnz entries of
a contain the nonzero elements of
and the next
nnzc entries contain the elements of the matrices
, for
stored consecutively. Within each block the matrix elements are ordered by increasing row index, and by increasing column index within each row.
- 4:
– IntegerInput
-
On entry: the dimension of the arrays
a,
irow and
icol. These arrays must be of sufficient size to store both
(
nnz elements) and
(
nnzc elements).
Note: the minimum value for
la is only appropriate if
lfill and
dtol are set such that minimal fill-in occurs. If this is not the case then we recommend that
la is set much larger than the minimum value indicated in the constraint.
Constraint:
.
- 5:
– IntegerInput/Output
- 6:
– IntegerInput/Output
-
On entry: the row and column indices of the nonzero elements supplied in
a.
Constraints:
irow and
icol must satisfy these constraints (which may be imposed by a call to
nag_sparse_nsym_sort (f11zac)):
- and , for ;
- either or both and , for .
On exit: the row and column indices of the nonzero elements returned in
a.
- 7:
– IntegerInput
-
On entry: the number of diagonal blocks to factorize.
Constraint:
.
- 8:
– const IntegerInput
-
On entry:
, for
, holds the indices in arrays
indb,
ipivp,
ipivq and
idiag that, on successful exit from this function, define block
. Let
denote the number of rows in block
; then
, for
. Thus,
holds the sum of the number of rows in all blocks plus
.
Constraint:
, for .
- 9:
– const IntegerInput
-
On entry:
indb must hold the row indices appearing in each diagonal block, stored consecutively. Thus the elements
, for
,
are the row indices in the
th block, for
.
Constraint:
, for .
- 10:
– IntegerInput
-
On entry: the dimension of the arrays
indb,
ipivp,
ipivq and
idiag.
Constraint:
.
- 11:
– const IntegerInput
-
On entry: if
its value is the maximum level of fill allowed in the decomposition of the block (see
Section 9.2 in
nag_sparse_nsym_fac (f11dac)). A negative value of
indicates that
will be used to control the fill in the block instead.
- 12:
– const doubleInput
-
On entry: if
then
is used as a drop tolerance in the block to control the fill-in (see
Section 9.2 in
nag_sparse_nsym_fac (f11dac)); otherwise
is not referenced.
Constraint:
if , , for .
- 13:
– const Nag_SparseNsym_PivInput
-
On entry:
, for
, specifies the pivoting strategy to be adopted in the block as follows:
- No pivoting is carried out.
- Pivoting is carried out according to the user-defined input values of ipivp and ipivq.
- Partial pivoting by columns for stability is carried out.
- Complete pivoting by rows for sparsity, and by columns for stability, is carried out.
Suggested value:
, for .
Constraint:
, , or , for .
- 14:
– const Nag_SparseNsym_FactInput
-
On entry:
, for
, indicates whether or not the factorization in the block should be modified to preserve row-sums (see
Section 9.4 in
nag_sparse_nsym_fac (f11dac)).
- The factorization is modified.
- The factorization is not modified.
Constraint:
or , for .
- 15:
– IntegerInput/Output
- 16:
– IntegerInput/Output
-
On entry: if
,
and
must specify the row and column indices of the element used as a pivot at elimination stage
of the factorization of the block. Otherwise
ipivp and
ipivq need not be initialized.
Constraint:
if
, the elements
to
of
ipivp and
ipivq must both hold valid permutations of the integers on
.
On exit: the row and column indices of the pivot elements, arranged consecutively for each block, as for
indb. If
and
, the element in row
and column
of
was used as the pivot at elimination stage
.
- 17:
– IntegerOutput
-
On exit:
, gives the index in the arrays
a,
irow and
icol of row
of the matrix
, for
and
.
contains .
- 18:
– IntegerOutput
-
On exit:
, gives the index in the arrays
a,
irow and
icol of the diagonal element in row
of the matrix
, for
and
.
- 19:
– Integer *Output
-
On exit: the sum total number of nonzero elements in the matrices
, for .
- 20:
– IntegerOutput
-
On exit: if
it gives the number of pivots which were modified during the factorization to ensure that
exists.
If
no pivot modifications were required, but a local restart occurred (see
Section 9.3 in
nag_sparse_nsym_fac (f11dac)). The quality of the preconditioner will generally depend on the returned values of
, for
.
If is large, for some block, the preconditioner may not be satisfactory. In this case it may be advantageous to call nag_sparse_nsym_precon_bdilu (f11dfc) again with an increased value of , a reduced value of , or .
- 21:
– NagError *Input/Output
-
The NAG error argument (see
Section 3.7 in How to Use the NAG Library and its Documentation).
6
Error Indicators and Warnings
- NE_ALLOC_FAIL
-
Dynamic memory allocation failed.
See
Section 2.3.1.2 in How to Use the NAG Library and its Documentation for further information.
- NE_BAD_PARAM
-
On entry, argument had an illegal value.
- NE_INT
-
On entry, .
Constraint: .
On entry, .
Constraint: .
On entry, .
Constraint: .
- NE_INT_2
-
On entry, and .
Constraint: .
On entry, and .
Constraint: .
On entry, and .
Constraint: .
- NE_INT_3
-
On entry, , and .
Constraint: .
- NE_INT_ARRAY
-
On entry, and .
Constraint: , for .
- NE_INTERNAL_ERROR
-
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact
NAG for assistance.
See
Section 2.7.6 in How to Use the NAG Library and its Documentation for further information.
- NE_INVALID_CS
-
On entry, and .
Constraint: , for .
On entry, and .
Constraint: , for .
- NE_INVALID_ROWCOL_PIVOT
-
On entry, the user-supplied value of
ipivp for block
lies outside its range.
On entry, the user-supplied value of
ipivp for block
was repeated.
On entry, the user-supplied value of
ipivq for block
lies outside its range.
On entry, the user-supplied value of
ipivq for block
was repeated.
- NE_NO_LICENCE
-
Your licence key may have expired or may not have been installed correctly.
See
Section 2.7.5 in How to Use the NAG Library and its Documentation for further information.
- NE_NOT_STRICTLY_INCREASING
-
On entry, element
of
a was out of order.
On entry, for , and .
Constraint: , for .
On entry, location of was a duplicate.
- NE_REAL_ARRAY
-
On entry, .
Constraint: , for .
- NE_TOO_SMALL
-
The number of nonzero entries in the decomposition is too large.
The decomposition has been terminated before completion.
Either increase
la, or reduce the fill by reducing
lfill, or increasing
dtol.
7
Accuracy
The accuracy of the factorization of each block will be determined by the size of the elements that are dropped and the size of any modifications made to the pivot elements. If these sizes are small then the computed factors will correspond to a matrix close to . The factorization can generally be made more accurate by increasing the level of fill , or by reducing the drop tolerance with .
If
nag_sparse_nsym_precon_bdilu (f11dfc) is used in combination with
nag_sparse_nsym_basic_solver (f11bec) or
nag_sparse_nsym_precon_bdilu_solve (f11dgc), the more accurate the factorization the fewer iterations will be required. However, the cost of the decomposition will also generally increase.
8
Parallelism and Performance
nag_sparse_nsym_precon_bdilu (f11dfc) is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
Please consult the
x06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the
Users' Note for your implementation for any additional implementation-specific information.
nag_sparse_nsym_precon_bdilu (f11dfc) calls
nag_sparse_nsym_fac (f11dac)
internally for each block
. The comments and advice provided in
Section 9 in
nag_sparse_nsym_fac (f11dac) on timing, control of
fill, algorithmic details, and choice of parameters, are all
therefore relevant to
nag_sparse_nsym_precon_bdilu (f11dfc), if interpreted blockwise.
10
Example
This example program reads in a sparse matrix
and then defines a block partitioning of the row indices with a user-supplied overlap and computes an overlapping incomplete
factorization suitable for use as an additive Schwarz preconditioner. Such a factorization is used for this purpose in the example program of
nag_sparse_nsym_precon_bdilu_solve (f11dgc).
10.1
Program Text
Program Text (f11dfce.c)
10.2
Program Data
Program Data (f11dfce.d)
10.3
Program Results
Program Results (f11dfce.r)