A survey of preconditioned iterative methods for linear systems of algebraic equations

O. Axelsson and V. A. Barker,Finite Element Solutions of Boundary Value Problems. Theory and Computation. Academic Press, New York, 1984. R. S. Varga,Matrix Iterative Analysis. Prentice Hall, New Jersey, 1962. V. I. Lebedev and S. A. Finogenov,On the order of choice of the iteration parameters in the Chebyshev cyclic iteration method. Zh. Vychislit. Mat. i Mat. Fiz. 11 (1971, p. 425, and 13 (1973), p. 18. O. Axelsson,Solution of linear systems of equations: Iterative methods inSparse Matrix Techniques (editor V. A. Barker), LNM #572, pp. 1–51, Springer-Verlag, 1977. D. M. Young,Second degree iterative methods for the solution of large linear systems, J. Approx. Theory 5 (1972), pp. 137–148. T. A. Manteuffel,The Tchebychev iteration for nonsymmetric linear systems, Numer. Math. 28 (1977), pp. 307–327. Y. Saad and M. H. Schultz,Conjugate gradient-like algorithms for solving nonsymmetric linear systems. Research Report RR-283, Department of Computer Science, Yale University, 1983. D. G. Luenberger,Introduction to Linear and Nonlinear Programming, Addison-Wesley, Reading, Mass., 1973. I. Gustafsson,Modified incomplete Cholesky (MIC) methods, inPreconditioning Methods: Analysis and Applications (editor D. J. Evans), pp. 265–293, Gordon and Breach, New York, 1983. D. M. Young,Iterative Solution of Large Linear Systems, Academic Press, New York, 1971. O. Axelsson, S. Brinkkemper and V. P. Il'in,On some versions of incomplete block-matrix factorization iterative methods, Lin. Alg. Appl. 58 (1984), pp. 3–15. O. Axelsson,On preconditioning and convergence acceleration in sparse matrix problems, CERN 74-10, Geneva, 1974. L. A. Hageman and D. M. Young,Applied Iterative Methods. Academic Press, New York, 1981. R. S. Varga,Factorizations and normalized iterative methods, inBoundary Problems in Differential Equations (editor R. E. Langer), pp. 121–142, The University of Wisconsin Press, Madison, Wisconsin, 1960. J. A. Meijerink and H. A. van der Vorst,An iterative method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. Comp. 31 (1977), pp. 148–162. O. Axelsson and N. Munksgaard,A class of preconditioned conjugate gradient methods for the solution of a mixed finite-element discretization of the biharmonic operator, Int. J. Numer. Math. Eng. 14 (1978), pp. 1001–1019. D. S. Kershaw,The incomplete Choleski-conjugate gradient method for the iterative solution of systems of linear equations, J. Comput. Phys. 26 (1978), 43–65. O. Axelsson and N. Munksgaard,Analysis of incomplete factorizations with fixed storage allocation, inPreconditioning Methods: Analysis and Applications (editor D. J. Evans), pp. 219–241, Gordon and Breach, New York, 1983. O. Axelsson,A general incomplete block-matrix factorization method, Lin. Alg. Appl., to appear. H. A. van der Vorst,Preconditioning by incomplete decompositions, Ph.D. Thesis, University of Utrecht, 1982. E. G. D'Yakonov,On the iterative method for the solution of finite difference equations, Dokl. Akad. Nauk SSSR, 138 (1961), 522–525. J. E. Gunn,The solution of elliptic difference equations by semi-explicit iterative techniques, SIAM J. Numer. Anal. Ser B2 (1964), 24–45. O. Axelsson,A generalized SSOR method, BIT 12 (1972), 443–467. T. Dupont, R. P. Kendall and H. H. Rachford, Jr.,An approximate factorization procedure for solving self-adjoint elliptic difference equations, SIAM J. Numer. Anal. 5 (1968), 559–573. H. L. Stone,Iterative solution of implicit approximations of multidimensional partial differential equations, SIAM J. Numer. Anal. 5 (1968), 530–558. R. Beauwens,On Axelsson's perturbations, Linear Algebra Appl., to appear. S. C. Eisenstat,Efficient implementation of a class of preconditioned conjugate gradient methods, SIAM J. Sci. Stat. Comput. 2 (1981), 1–4. P. Concus, G. H. Golub and D. P. O'Leary,A generalized conjugate gradient iteration for the numerical solution of elliptic partial differential equations, pp. 304–322 inSparse Matrix Computations (J. R. Bunch and D. J. Rose, eds), Academic Press, New York, 1976. J. Douglas, Jr. and T. Dupont,Preconditioned conjugate gradient iteration applied to Galerkin methods for a mildly-nonlinear Dirichlet problem, pp. 323–333 in same volume as ref. [26]. R. Bank,An automatic scaling procedure for a D'Yakonov-Gunn iteration scheme, Linear Algebra Appl. 28 (1979), 17–33. R. R. Underwood,An approximate factorization procedure based on the block Cholesky decomposition and its use with the conjugate gradient method, Report NEDO-11386, General Electric Co., Nuclear Energy Div., San Jose, California (1976). P. Concus, G. H. Golub and G. Meurant,Block preconditioning for the conjugate gradient method, Report LBL-14856, Lawrence Berkeley Lab., University of California (1982), to appear (abridged) in SISSC. R. Kettler,Analysis and comparison of relaxed schemes in robust multigrid and preconditioned conjugate gradient methods, inMultigrid Methods (eds W. Hackbusch and U. Trottenberg), LNM 960, pp. 502–534, Springer Verlag, 1982. O. Axelsson,A vectorizable variant of a block incomplete factorization method, Proceedings of the VIth International Conference on the Numerical Solution of Fuid Flow Problems, Jan. 1984, The University of Texas at Austin, John Wiley and Sons, to appear. O. Axelsson,Incomplete block matrix factorization preconditioning methods. The ultimate answer? to appear in J. Comp. Appl. Math. S. Demko, W. F. Moss and P. W. Smith,Decay rates for inverses of band matrices, to appear in Math. Comp. R. Beauwens and M. BenBouzid,On block-OBV methods, Part I, Commissariat aux energies nouvelles, Physique Théorique et Méthodes Numériques, Alger, 1983. G. Meurant,The block preconditoned conjugate gradient method on vector computers, BIT 24 (1984), 623–633. O. Axelsson,A survey of vectorizable preconditioning methods for large scale finite element matrix problems, CNA-190, February 1984, Center for Numerical Analysis, The University of Texas at Austin, Texas. O. Axelsson and I. Gustafsson,Preconditioning and two-level multigrid methods of arbitrary degree of approximation, Math. Comp. 40 (1983), 214–242. H. Yserentant,On the multilevel splitting of finite element spaces. Bericht Nr. 21, 1983, Institut für Geometrie und Praktische Mathematik, R.W.T.H., Aachen, Germany. J. H. Bramble, J. E. Pasciak and A. H. Schatz,Preconditioners for interface problems on mesh domains, preprint, Cornell University, 1963. G. H. Golub and D. Mayers,The use of pre-conditioning over irregular regions, NA-83-27, Computer Science Department, Stanford University, California, December 1983. Q. V. Dinh, R. Glowinski, B. Mantel, J. Periaux and P. Perrier,Subdomain solutions of non-linear problems in fluid dynamics on parallel processors, inComputing Methods in Applied Sciences and Engineering, V, R. Glowinski and J. L. Lions (editors), North-Holland Publ. Comp., 1982. N. K. Madson, G. H. Rodrigue and J. I. Karush,Matrix multiplication by diagonals on a vector/parallel processor, Information Processing Lett. 5 (1976), 41–45. H. van der Vorst,A vectorizable variant of some ICCG methods, SIAM J. Stat. Comput. 3 (1982), 86–96. H. S. Stone,An efficient parallel algorithm for the solution of a tridiagonal linear system of equations, J.A.C.M. 20 (1973), 27–38. D. Heller,A survey of parallel algorithms in numerical linear algebra, SIAM Review 20 (1978), 740–776. P. Dubois and G. Rodrigue,An analysis of the recursive doubling algorithm, in D. J. Kuck et al. (eds),High Speed Computer and Algorithm Organization, Academic Press, New York, 1977. O. G. Johnson, C. A. Micchelli and G. Paul,Polynomial preconditioners for conjugate gradient calculations, RC 9208, IBM Th. J. Watson Research Center, Yorktown Heights, New York, 1982. Y. Saad,Practical use of polynomial preconditionings for the conjugate gradient method. Research Report RR 283, Yale University, Department of Computer Science, 1983. P. F. Dubois, A. Greenbaum and G. H. Rodrigue,Approximating the inverse of a matrix for use in iterative algorithms on vector processors, Computing 22 (1979), 257–268. I. Gustafsson,Stability and rate of convergence of modified incomplete Cholesky factorization methods, Ph.D. Thesis, Department of Computer Science, Göteborg, Sweden, 1979. G. Rodrigue and D. Wolitzer,Incomplete block cyclic reduction, 2nd IMACS International Symposium on Parallel Computation, Newark, Delaware, 1981. O. Axelsson,Error estimates over infinite intervals of some discretizations of evolution equations, BIT 24 (1984), 413–424. A. F. Cornock,The numerical solution of Poisson's and the bi-harmonic equations by matrices, Proc. Cambridge Phil. Soc. 50 (1954), 524–535. S. Schechter,Quasi-tridiagonal matrices and type-insensitive difference equations, Quart. Appl. Math. 18 (1960), 285–295. G. I. Marchuk, and V. P. Il'in,Parallel computations in grid methods for solving mathematical physics problems, Information Processing 80, S. H. Lavington (ed.), North-Holland Publ. Comp. IFIP, 1980. D. J. Evans,New parallel algorithms in linear algebra, EDF., Bulletin de la Direction des Etudes et des Recherches, Serie C, No. 1, Paris, 1983. M. H. Schultz,Solving elliptic problems on an array processor system, Research Report YALEU/DCS/RR-272, June 1983. T. J. Jordan,A guide to parallel computation and some CRAY-1 experiences, LANL Report, Los Alamos, 1981. C. Kamath and A. Sameh,The preconditioned conjugate gradient algorithm on a multiprocessor, inAdvances in Computer Methods for Partial Differential Equations, V. R. Vichnevetsky and R. S. Stepleman (eds), Publ. IMACS, Newark, Delaware, 1984. D. R. Kincaid, T. C. Oppe and D. M. Young,Vector computations for sparse linear systems, Center for Numerical Analysis, CNA-189, The University of Texas at Austin, February 1984.