Preconditioning techniques for nonsymmetric and indefinite linear systems.

*(English)*Zbl 0662.65028This paper examines different techniques for solving large sparse linear systems which are nonsymmetric or indefinite by preconditioning techniques. Solving those systems by iterative schemes can be very hard and none of the examined techniques can be viewed as a general purpose solver. Alternatives considered for these cases are either to use direct methods or techniques based on the normal equations.

Examples show that the incomplete LQ factorization combined with the normal equation approach is one of the most promising methods. The author uses a Gram-Schmidt-process which is numerically stable because the rows remain very sparse in the incomplete LQ factorization. For the incompleteness of the factorization a dropping strategy is proposed which keeps only a fixes amount of largest elements in L and Q. The resulting algorithm is fairly economical and does not require allocating more space than necessary but it is not amenable to parallel or vector processing. As alternative methods the author describes the incomplete LU factorization with pivoting, SSOR and incomplete Cholesky on the normal equations.

Examples show that the incomplete LQ factorization combined with the normal equation approach is one of the most promising methods. The author uses a Gram-Schmidt-process which is numerically stable because the rows remain very sparse in the incomplete LQ factorization. For the incompleteness of the factorization a dropping strategy is proposed which keeps only a fixes amount of largest elements in L and Q. The resulting algorithm is fairly economical and does not require allocating more space than necessary but it is not amenable to parallel or vector processing. As alternative methods the author describes the incomplete LU factorization with pivoting, SSOR and incomplete Cholesky on the normal equations.

Reviewer: N.Köckler

##### MSC:

65F10 | Iterative numerical methods for linear systems |

65F50 | Computational methods for sparse matrices |

##### Keywords:

least squares problems; comparison of methods; large sparse linear systems; nonsymmetric; indefinite; preconditioning; normal equations; incomplete LQ factorization; Gram-Schmidt-process; incomplete LU factorization with pivoting; SSOR; incomplete Cholesky##### Software:

LSQR
PDF
BibTeX
XML
Cite

\textit{Y. Saad}, J. Comput. Appl. Math. 24, No. 1--2, 89--105 (1988; Zbl 0662.65028)

Full Text:
DOI

##### References:

[1] | Anderson, E.; Saad, Y., Solving sparse triangular systems on parallel processors, Tech. rep., (1988), University of Illinois, CSRD Urbana, Il, in preparation |

[2] | A. Bjork, Least squares methods, in: P.G. Giarlet and J.L. Lions, Eds., Handbook of Numerical Analysis (North-Holland, Amsterdam, to appear). |

[3] | Bjork, A.; Elfving, T., Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations, Bit, 19, 145-163, (1979) · Zbl 0409.65022 |

[4] | Duff, I.S.; Erisman, A.M.; Reid, J.K., Direct methods for sparse matrices, (1986), Clarendon Press Oxford · Zbl 0604.65011 |

[5] | Elman, H., Iterative methods for large sparse nonsymmetric systems of linear equations, Ph.D. dissertation, (1982), Yale University, Computer Science Dept New Haven, CT |

[6] | Elman, H., A stability analysis of incomplete LU factorizations, Math. comp., 47, 191-217, (1986) · Zbl 0621.65024 |

[7] | George, J.; Heath, M., Solution of sparse linear least squares problems using givens rotations, Lin. algebra appl., 34, 69-83, (1980) · Zbl 0459.65025 |

[8] | Goldstein, C.; Turkel, E., An iterative method for the Helmholtz equation, J. comput. phys., 49, 443-457, (1983) · Zbl 0524.65068 |

[9] | Kamath, C.; Sameh, A., A projection method for solving nonsymmetric linear systems on multiprocessors, Tech. rep. 611, (1986), CSRD, University of Illinois Urbana, IL |

[10] | Paige, C.; Saunders, M., An algorithm for sparse linear equations and sparse least squares, ACM trans. math. software, 8, 43-71, (1982) · Zbl 0478.65016 |

[11] | Saad, Y.; Schultz, M., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. sci. stat. comput., 7, 856-869, (1986) · Zbl 0599.65018 |

[12] | Varga, R., Matrix iterative analysis, (1962), Prentice-Hall Englewood Cliffs, NJ · Zbl 0133.08602 |

[13] | Watts, J.W., A conjugate gradient truncated direct method for the iterative solution of the reservoir simulation pressure equation, Soc. petroleum eng. J., 21, 345-353, (1981) |

[14] | Zlatev, Z., Use of iterative refinement in the solution of sparse linear systems, SIAM J. numer. anal., 19, 381-399, (1982) · Zbl 0485.65022 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.