Approximate factorizations with S/P consistently ordered M-factors

The behaviour of PCG methods for solving a finite difference or finite element positive definite linear system Ax=b with a (pre)conditioning matrix B=UTP-1U (where U is upper triangular and P=diag(U)) obtained from a modified incomplete factorization, is unpredictable in the present status of knowledge whenever the upper triangular factor is not strictly diagonally dominant and 2 P -D, where D=diag(A), is not symmetric positive definite. The origin of this rather surprising shortcoming of the theory is that all upper bounds on the associated spectral condition number κ(B-1A) obtained so far require either the strict diagonal dominance of the upper triangular factor or the strict positive definiteness of 2 P -D. It is our purpose here to improve the theory in this respect by showing that, when the triangular factors are "S/P consistently ordered"M-matrices, nonstrict diagonal dominance is generally a sufficient requirement, without additional condition on 2 P -D. As a consequence, the new analysis does not require diagonal perturbations (otherwise needed to keep control of the diagonal dominance of U or of the positive definiteness of 2 P -D). Further, the bounds obtained here on κ(B-1A) are independent of the lower spectral bound of D-1A meaning that quasi-singular problems can be solved at the same speed as regular ones, an unexpected result. © 1989 BIT Foundations.SCOPUS: ar.j