Not all matrices [A] can be factored into the form [L][D][L]T (symmetric) or [L][U] (nonsymmetric). If two rows are identical except for a scale factor, the equations are linearly dependent and a zero pivot results. In actual practice, equations that are close to being linearly dependent generate pivots that are close to zero. The result is errors in the solution vector when the matrix factors are used.
To detect these ill-conditioned matrices, FMS monitors the accuracy of the diagonal pivots. Each term in the diagonal factor is computed from an equation of the following form:
D = A - S
where D is the matrix factor diagonal being computed, A is the diagonal of the original matrix, and S is the sum of an inner product.
The following figure shows how precision is lost during subtraction from a hardware point of view.
In this example, a 64-bit floating point representation is used with 11 exponent bits and 53 mantissa bits (IEEE format).
The first step in the subtraction process is to right shift the mantissa of the smaller term so that both the exponents of A and S are identical. Next, an integer subtraction is performed to compute the result D = A - S.
If A and S are close, their exponents and leading mantissa bits will be the same, as shown in the figure above. The result D will then contain leading 0's, representing lost bits of accuracy.
FMS contains two precision flags which are based on the number of lost mantissa bits. If the calculation of D results in NBITSP lost mantissa bits, FMS prints a warning message and continues with the factoring process. The default value of 26 corresponds to a ratio of
If the calculation of D results in NBITSZ lost mantissa bits, FMS handles the pivot as though it were zero. The default value of 39 corresponds to a ratio of
FMS will also generate a zero pivot condition if the absolute value of D is less than or equal to the FMS Parameter PIVMIN (for complex data, D squared is compared to PIVMIN). The default value of 0 for PIVMIN prevents this test from being used unless you call FMSRST to reset PIVMIN.
The action taken by FMS when a zero (or close to zero) pivot is found depends on the parameter MZERO. If MZERO is 0 (default), a fatal error is generated. If MZERO is 1, FMS sets the pivot reciprocal to RPIVOT, prints a warning message and continues. If MZERO is set to 2, FMS calls your subroutine RSUPIV or CSUPIV according to the appropriate data type.
When a zero pivot is encountered, it does not necessarily mean that the equation is bad. It just means that it could not be eliminated at that particular point in the matrix. The objective of pivoting is to relocate zero pivot equations to a lower point in the matrix where they may be processed.
For nonsymmetric full matrices, FMS includes an option for full column partial pivoting. This option selects the largest absolute value pivot as each diagonal is processed by examining the remaining equations in the column containing the diagonal. If a term larger than the diagonal is found, the rows are swapped to move the larger term to the diagonal position. This option may be selected by setting the matrix format type MFMAT to a SLAB matrix.
You can always process any matrix as full and nonsymmetric. However if the matrix is symmetric or contains a lot of zeros, this would be inefficient.
It is possible to accomplish pivoting for sparse or symmetric matrices by making two passes on the matrix. On the first pass, the FMS Parameter MZERO is set to 1. If a zero pivot is found, FMS sets its reciprocal to RPIVOT (default 0) and continues. This has the effect of eliminating the row and column corresponding to that equation from the matrix. At the end of factoring, FMS has printed a list of all zero pivot equations, if any.
For the second step, you renumber the equations placing the zero pivot equations at the bottom of the matrix. This has the effect of full row and column pivoting, which leaves diagonal matrix terms on the diagonal.
Once the matrix has been rebuilt in the new order, it may be refactored as in step 1. In the unlikely event that more zero pivots were found, these steps may be repeated.
If you want to automate the above procedure or provide zero pivot handling not included in FMS, you may supply your own subroutine. Setting MZERO = 2 will direct FMS to call RSUPIV or CSUPIV according to the appropriate data type. You may flag the zero pivot equations in an array or provide other special effects particular to your own program.