If  the amount of fill-in occurring in the incomplete factorization is controlled by limiting the maximum level of fill-in to lfill. The original non-zero elements of  are defined to be of level 0. The fill level of a new non-zero location occurring during the factorization is defined as:

where  is the level of fill of the element being eliminated, and  is the level of fill of the element causing the fill-in.

If  the fill-in is controlled by means of the drop tolerance dtol. A potential fill-in element  occurring in row  and column  will not be included if:

where  is the maximum absolute value element in the matrix .

For either method of control, any elements which are not included are discarded unless , in which case their contributions are subtracted from the pivot element in the relevant elimination row, to preserve the row-sums of the original matrix.

Should the factorization process break down a local restart process is implemented as described in Section [Algorithmic Details]. This will affect the amount of fill present in the final factorization.

The factorization is constructed row by row. At each elimination stage a row index is chosen. In the case of complete pivoting this index is chosen in order to reduce fill-in. Otherwise the rows are treated in the order given, or some user-defined order.

The chosen row is copied from the original matrix  and modified according to those previous elimination stages which affect it. During this process any fill-in elements are either dropped or kept according to the values of lfill or dtol. In the case of a modified factorization () the sum of the dropped terms for the given row is stored.

Finally the pivot element for the row is chosen and the multipliers are computed for this elimination stage. For partial or complete pivoting the pivot element is chosen in the interests of stability as the element of largest absolute value in the row. Otherwise the pivot element is chosen in the order given, or some user-defined order.

If the factorization breaks down because the chosen pivot element is zero, or there is no non-zero pivot available, a local restart recovery process is implemented. The modification of the given pivot row according to previous elimination stages is repeated, but this time keeping all fill. Note that in this case the final factorization will include more fill than originally specified by the user-supplied value of lfill or dtol. The local restart usually results in a suitable non-zero pivot arising. The original criteria for dropping fill-in elements is then resumed for the next elimination stage (hence the local nature of the restart process). Should this restart process also fail to produce a non-zero pivot element an arbitrary unit pivot is introduced in an arbitrarily chosen column. nag_sparse_nsym_fac (f11dac) returns an integer argument npivm which gives the number of these arbitrary unit pivots introduced. If no pivots were modified but local restarts occurred  is returned.

There is unfortunately no choice of the various algorithmic arguments which is optimal for all types of matrix, and some experimentation will generally be required for each new type of matrix encountered.

If the matrix  is not known to have any particular special properties the following strategy is recommended. Start with  and . If the value returned for npivm is significantly larger than zero, i.e., a large number of pivot modifications were required to ensure that  existed, the preconditioner is not likely to be satisfactory. In this case increase lfill until npivm falls to a value close to zero.

If  has non-positive off-diagonal elements, is non-singular, and has only non-negative elements in its inverse, it is called an "M-matrix". It can be shown that no pivot modifications are required in the incomplete  factorization of an M-matrix (Meijerink and Van der Vorst (1977)). In this case a good preconditioner can generally be expected by setting ,  and .

Some illustrations of the application of nag_sparse_nsym_fac (f11dac) to linear systems arising from the discretization of two-dimensional elliptic partial differential equations, and to random-valued randomly structured linear systems, can be found in Salvini and Shaw (1996).