Preconditioning techniques for large linear systems: A survey. (English) Zbl 1015.65018

Benzi, Michele

J. Comput. Phys. 182, No. 2, 418-477 (2002).

Summary: This article surveys preconditioning techniques for the iterative solution of large linear systems, with a focus on algebraic methods suitable for general sparse matrices. Covered topics include progress in incomplete factorization methods, sparse approximate inverses, reorderings, parallelization issues, and block and multilevel extensions. Some of the challenges ahead are also discussed. An extensive bibliography completes the paper.

MSC:

65F35	Numerical computation of matrix norms, conditioning, scaling
65-02	Research exposition (monographs, survey articles) pertaining to numerical analysis
65N55	Multigrid methods; domain decomposition for boundary value problems involving PDEs
65-00	General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to numerical analysis
65F10	Iterative numerical methods for linear systems
65F50	Computational methods for sparse matrices
65Y05	Parallel numerical computation

Keywords:

linear systems; sparse matrices; iterative methods; algebraic preconditioners; incomplete factorizations; sparse approximate inverses; unstructured grids; multilevel methods; parallel computing; orderings; block algorithms; survey paper; bibliography

Software:

symrcm; pARMS; ILUS; MUMPS; ILUM; PETSc; BPKit; ARMS; BoomerAMG; BILUTM; TAUCS; SparseMatrix; ILUT; Algorithm 740

References:

[1]	Ahn, C.H.; Chew, W.C.; Zhao, J.S.; Michielssen, E., Numerical study of approximate inverse preconditioner for two-dimensional engine inlet problems, Electromagnetics, 19, 131, (1999)
[2]	Ajiz, M.A.; Jennings, A., A robust incomplete choleski-conjugate gradient algorithm, Int. J. numer. methods eng., 20, 949, (1984) · Zbl 0541.65019
[3]	Alléon, G.; Benzi, M.; Giraud, L., Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics, Numer. algorithms, 16, 1, (1997) · Zbl 0895.65017
[4]	Amestoy, P.; Davis, T.A.; Duff, I.S., An approximate minimum degree ordering algorithm, SIAM J. matrix anal. appl., 17, 886, (1996) · Zbl 0861.65021
[5]	Amestoy, P.; Duff, I.S.; L’Excellent, J.-Y.; Koster, J., A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. matrix anal. appl., 23, 15, (2001) · Zbl 0992.65018
[6]	Ashby, S.F.; Brown, P.N.; Dorr, M.R.; Hindmarsh, A.C., A linear algebraic analysis of diffusion synthetic acceleration for the Boltzmann transport equation, SIAM J. numer. anal., 32, 179, (1995) · Zbl 0821.65088
[7]	Ashby, S.F.; Manteuffel, T.A.; Saylor, P.E., Adaptive polynomial preconditioning for Hermitian indefinite linear systems, Bit, 29, 583, (1989) · Zbl 0688.65024
[8]	Ashcraft, C., Compressed graphs and the minimum degree algorithm, SIAM J. sci. comput., 16, 1404, (1995) · Zbl 0837.65015
[9]	Axelsson, O., A generalized SSOR method, Bit, 13, 443, (1972) · Zbl 0256.65046
[10]	Axelsson, O., A survey of preconditioned iterative methods for linear systems of algebraic equations, Bit, 25, 166, (1985) · Zbl 0566.65017
[11]	Axelsson, O., A general incomplete block matrix factorization method, Linear algebra its appl., 74, 179, (1986) · Zbl 0622.65023
[12]	Axelsson, O., iterative solution methods, (1994), Cambridge Univ. Press Cambridge · Zbl 0795.65014
[13]	Axelsson, O.; Brinkkemper, S.; Il’in, V.P., On some versions of incomplete block matrix factorization iterative methods, Linear algebra its appl., 58, 3, (1984) · Zbl 0548.65016
[14]	Axelsson, O.; Eijkhout, V., Vectorizable preconditioners for elliptic difference equations in three space dimensions, J. comput. appl. math., 27, 299, (1991) · Zbl 0678.65030
[15]	Axelsson, O.; Kolotilina, L.Yu., Diagonally compensated reduction and related preconditioning methods, Numer. linear algebra appl., 1, 155, (1994) · Zbl 0837.65023
[16]	Axelsson, O.; Vassilevski, P.S., Algebraic multilevel preconditioning methods, I, Numer. math., 56, 157, (1989) · Zbl 0661.65110
[17]	Axelsson, O.; Vassilevski, P.S., Algebraic multilevel preconditioning methods, II, SIAM J. numer. anal., 27, 1569, (1990) · Zbl 0715.65091
[18]	S. Balay, K. Buschelman, W. Gropp, D. Kaushik, M. Knepley, L. C. McInnes, B. Smith, and, H. Zhang, PETSc User’s Manual, Report ANL 95/11, Revision 2.2.3, Argonne National Laboratory, Argonne, IL, 2002.
[19]	Banerjee, R.N.; Benson, M.W., An approximate inverse based multigrid approach to the biharmonic problem, Int. J. comput. math., 40, 201, (1991) · Zbl 0746.65083
[20]	Bank, R.E.; Smith, R.K., The incomplete factorization multigraph algorithm, SIAM J. sci. comput., 20, 1349, (1999) · Zbl 0931.65021
[21]	Bank, R.E.; Smith, R.K., An algebraic multilevel multigraph algorithm, SIAM J. sci. comput., 23, 1572, (2002) · Zbl 1006.65027
[22]	Bank, R.E.; Wagner, C., Multilevel ILU decomposition, Numer. math., 82, 543, (1999) · Zbl 0938.65063
[23]	Barnard, S.T.; Bernardo, L.M.; Simon, H.D., An MPI implementation of the SPAI preconditioner on the T3E, Int. J. high perform. comput. appl., 13, 107, (1999)
[24]	S. T. Barnard, and, R. L. Clay, A portable MPI implementation of the SPAI preconditioner in ISIS++, in, Proceedings of the Eight SIAM Conference on Parallel Processing for Scientific Computing, edited by, M. Heath, et al., SIAM, Philadelphia, PA, 1997, [CD-ROM]).
[25]	S. T. Barnard, and, M. J. Grote, A block version of the SPAI preconditioner, in, Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, edited by, B. A. Hendrickson, et al., SIAM, Philadelphia, PA, 1999, [CD-ROM]).
[26]	Barrett, R.; Berry, M.; Chan, T.F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; van der Vorst, H., templates for the solution of linear systems: building blocks for iterative methods, (1994), SIAM Philadelphia
[27]	Behie, G.A.; Forsyth, P.A., Comparison of fast iterative methods for symmetric systems, IMA J. numer. anal., 3, 41, (1983) · Zbl 0514.65076
[28]	Benson, M.W., iterative solution of large scale linear systems, (1973), Lakehead University Thunder Bay
[29]	Benson, M.W., Frequency domain behavior of a set of parallel multigrid smoothing operators, Int. J. comput. math., 36, 77, (1990) · Zbl 0706.65116
[30]	Benson, M.W., An approximate inverse based multigrid approach to thin domain problems, Util. math., 45, 39, (1994) · Zbl 0814.65117
[31]	Benson, M.W.; Frederickson, P.O., Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems, Util. math., 22, 127, (1982) · Zbl 0502.65020
[32]	Benzi, M.; Cullum, J.K.; Tůma, M., Robust approximate inverse preconditioning for the conjugate gradient method, SIAM J. sci. comput., 22, 1318, (2000) · Zbl 0985.65035
[33]	Benzi, M.; Haws, J.C.; Tůma, M., Preconditioning highly indefinite and nonsymmetric matrices, SIAM J. sci. comput., 22, 1333, (2000) · Zbl 0985.65036
[34]	Benzi, M.; Joubert, W.D.; Mateescu, G., Numerical experiments with parallel orderings for ILU preconditioners, Electron. trans. numer. anal., 8, 88, (1999) · Zbl 0923.65012
[35]	Benzi, M.; Kouhia, R.; Tůma, M., An assessment of some preconditioning techniques in shell problems, Commun. numer. methods eng., 14, 897, (1998) · Zbl 0920.73348
[36]	Benzi, M.; Kouhia, R.; Tůma, M., Stabilized and block approximate inverse preconditioners for problems in solid and structural mechanics, Comput. methods appl. mech. eng., 190, 6533, (2001) · Zbl 1021.74041
[37]	Benzi, M.; Marı́n, J.; Tůma, M., A two-level parallel preconditioner based on sparse approximate inverses, (), 167
[38]	Benzi, M.; Meyer, C.D.; Tůma, M., A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. sci. comput., 17, 1135, (1996) · Zbl 0856.65019
[39]	Benzi, M.; Szyld, D.B.; van Duin, A., Orderings for incomplete factorization preconditioning of nonsymmetric problems, SIAM J. sci. comput., 20, 1652, (1999) · Zbl 0940.65033
[40]	Benzi, M.; Tůma, M., A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. sci. comput., 19, 968, (1998) · Zbl 0930.65027
[41]	Benzi, M.; Tůma, M., Numerical experiments with two approximate inverse preconditioners, Bit, 38, 234, (1998) · Zbl 0909.65027
[42]	Benzi, M.; Tůma, M., A comparative study of sparse approximate inverse preconditioners, Appl. numer. math., 30, 305, (1999) · Zbl 0949.65043
[43]	Benzi, M.; Tůma, M., Orderings for factorized approximate inverse preconditioners, SIAM J. sci. comput., 21, 1851, (2000) · Zbl 0959.65047
[44]	M. Benzi, and, M. Tůma, A robust incomplete factorization preconditioner for positive definite matrices, Numer. Linear Algebra Appl, in press. · Zbl 1042.65030
[45]	Benzi, M.; Tůma, M., A parallel solver for large-scale Markov chains, Appl. numer. math., 41, 135, (2002) · Zbl 0997.65006
[46]	Bergamaschi, L.; Pini, G.; Sartoretto, F., Approximate inverse preconditioning in the parallel solution of sparse eigenproblems, Numer. linear algebra appl., 7, 99, (2000) · Zbl 0982.65038
[47]	Bergamaschi, L.; Pini, G.; Sartoretto, F., Parallel preconditioning of a sparse eigensolver, Parallel comput., 27, 963, (2001) · Zbl 0971.68213
[48]	Berman, A.; Plemmons, R.J., nonnegative matrices in the mathematical sciences, (1979), Academic Press New York · Zbl 0484.15016
[49]	A. Berman, and, R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 3rd ed. reprinted by, SIAM, Philadelphia, PA, 1994. · Zbl 0815.15016
[50]	M. Bern, J. R. Gilbert, B. Hendrickson, N. Nguyen, and, S. Toledo, Support graph preconditioners, submitted for publication.
[51]	Bodewig, E., matrix calculus, (1959), Interscience New York/North-Holland
[52]	Bollhöfer, M., A robust ILU with pivoting based on monitoring the growth of the inverse factors, Linear algebra its appl., 338, 201, (2001) · Zbl 0991.65028
[53]	M. Bollhöfer, A robust and efficient ILU that incorporates the growth of the inverse triangular factors, submitted for publication.
[54]	Bollhöfer, M.; Mehrmann, V., Algebraic multilevel methods and sparse approximate inverses, SIAM J. matrix anal. appl., 24, 191, (2002) · Zbl 1035.65030
[55]	Bollhöfer, M.; Saad, Y., A factored approximate inverse preconditioner with pivoting, SIAM J. matrix anal. appl., 23, 692, (2002) · Zbl 0999.65027
[56]	Bollhöfer, M.; Saad, Y., On the relations between ILUs and factored approximate inverses, SIAM J. matrix anal. appl., 24, 219, (2002) · Zbl 1017.65019
[57]	E. G. Boman, D. Chen, B. Hendrickson, and, S. Toledo, Maximum-weight-basis preconditioners, submitted for publication. · Zbl 1164.65393
[58]	Botros, Y.Y.; Volakis, J.L., Preconditioned generalized minimal residual iterative scheme for perfectly matched layer terminated applications, IEEE microwave guided wave lett., 9, 45, (1999)
[59]	Botta, E.F.F.; Wubs, F.W., Matrix renumbering ILU: an effective algebraic multilevel ILU preconditioner for sparse matrices, SIAM J. matrix anal. appl., 20, 1007, (1999) · Zbl 0937.65057
[60]	Bramble, J.H., multigrid methods, (1993), Longman Scientific & Technical Harlow
[61]	Brand, C.W., An incomplete factorization preconditioning using repeated red/black ordering, Numer. math., 61, 433, (1992) · Zbl 0772.65018
[62]	Brandt, A., Multi-level adaptive solutions to boundary-value problems, Math. comput., 31, 333, (1977) · Zbl 0373.65054
[63]	A. Brandt, S. McCormick, and, J. Ruge, Algebraic multigrid (AMG) for sparse matrix equations, in, Sparsity and Its Applications, edited by, D. J. Evans, p, 257, Cambridge Univ. Press, Cambridge, UK, 1985. · Zbl 0548.65014
[64]	Brezinski, C., projection methods for systems of equations, studies in computational mathematics, (1997), North-Holland Amsterdam · Zbl 0867.65009
[65]	Bridson, R.; Tang, W.-P., Ordering, anisotropy and factored sparse approximate inverses, SIAM J. sci. comput., 21, 867, (1999) · Zbl 0955.65018
[66]	Bridson, R.; Tang, W.-P., A structural diagnosis of some IC orderings, SIAM J. sci. comput., 22, 1527, (2000) · Zbl 0988.65035
[67]	Bridson, R.; Tang, W.-P., Refining an approximate inverse, J. comput. appl. math., 22, 1527, (2000)
[68]	Bridson, R.; Tang, W.-P., Multiresolution approximate inverse preconditioners, SIAM J. sci. comput., 23, 463, (2001) · Zbl 0992.65027
[69]	Briggs, W.L.; Henson, V.E.; McCormick, S.F., A multigrid tutorial, (2000), SIAM Philadelphia
[70]	Bröker, O.; Grote, M.J., Sparse approximate inverse smoothers for geometric and algebraic multigrid, Appl. numer. math., 41, 61, (2002) · Zbl 0995.65129
[71]	Bröker, O.; Grote, M.J.; Mayer, C.; Reusken, A., Robust parallel smoothing for multigrid via sparse approximate inverses, SIAM J. sci. comput., 23, 1395, (2001) · Zbl 1004.65043
[72]	Bruaset, A.M., A survey of preconditioned iterative methods, (1995), Longman Scientific & Technical Harlow · Zbl 0834.65014
[73]	Buleev, N.I., A numerical method for solving two dimensional diffusion equations, At. energ., 6, 338, (1959)
[74]	Buleev, N.I., A numerical method for solving two- and three-dimensional diffusion equations, Mat. sb., 51, 227, (1960) · Zbl 0105.10401
[75]	Carpentieri, B.; Duff, I.S.; Giraud, L., Sparse pattern selection strategies for robust Frobenius-norm minimization preconditioners in electromagnetics, Numer. linear algebra appl., 7, 667, (2000) · Zbl 1051.65050
[76]	B. Carpentieri, I. S. Duff, L. Giraud, and, M. Magolu monga Made, Sparse Symmetric Preconditioners for Dense Linear Systems in Electromagnetics, CERFACS Technical Report TR/PA/01/35, Toulouse, France, 2001.
[77]	Carpentieri, B.; Duff, I.S.; Giraud, L.; Sylvand, G., Combining fast multipole techniques and approximate inverse preconditioners for large calculations in electromagnetism, Activity report of the parallel algorithms project at CERFACS, January 2001-december 2001, (2001) · Zbl 1089.78023
[78]	Cesari, L., Sulla risoluzione dei sistemi di equazioni lineari per approssimazioni successive, Atti accad. nazionale lincei R. classe sci. fis. mat. nat., 25, 422, (1937) · JFM 63.0524.01
[79]	Challacombe, M., A simplified density matrix minimization for linear scaling self-consistent field theory, J. chem. phys., 110, 2332, (1999)
[80]	Challacombe, M., A general parallel sparse-blocked matrix multiply for linear scaling SCF theory, Comput. phys. commun., 128, 93, (2000) · Zbl 1003.81582
[81]	Chan, T.F.; Tang, W.-P.; Wan, W.-L., Wavelet sparse approximate inverse preconditioners, Bit, 37, 644, (1997) · Zbl 0891.65048
[82]	T. F. Chan, and, H. A. van der Vorst, Approximate and incomplete factorizations, in, Parallel Numerical Algorithms, edited by, D. E. Keyes, A. Sameh, and V. Venkatakrishnan, ICASE/LaRC Interdisciplinary Series in Science and Engineering, Vol, 4, p, 167, Kluwer Academic, Dordrecht, 1997. · Zbl 0865.65015
[83]	Chapman, A.; Saad, Y.; Wigton, L., High-order ILU preconditioners for CFD problems, Int. J. numer. methods fluids, 33, 767, (2000) · Zbl 0959.76077
[84]	D. Chen, and, S. Toledo, Vaidya’s preconditioners: implementation and experimental study, submitted for publication. · Zbl 1031.65064
[85]	Chen, K., On a class of preconditioning methods for dense linear systems from boundary elements, SIAM J. sci. comput., 20, 684, (1998)
[86]	Chen, K., Discrete wavelet transforms accelerated sparse preconditioners for dense boundary element systems, Electron. trans. numer. anal., 8, 138, (1999) · Zbl 0974.65043
[87]	Chen, K., An analysis of sparse approximate inverse preconditioners for boundary integral equations, SIAM J. matrix anal. appls., 22, 1058, (2001) · Zbl 0985.65038
[88]	Chernesky, M.P., On preconditioned Krylov subspace methods for discrete convection-diffusion problems, Numer. methods partial differential equations, 13, 321, (1997) · Zbl 0881.65095
[89]	Choi, H.; Szyld, D.B., Application of threshold partitioning of sparse matrices to Markov chains, Proceedings of the IEEE international computer performance and dependability symposium, IPDS’96, 158, (1996)
[90]	Choquet, R.; Perrier, V., Fast wavelet iterative solvers applied to the Neumann problem, Aerospace sci. technol., 4, 135, (2000) · Zbl 0964.65116
[91]	Chow, E., A priori sparsity patterns for parallel sparse approximate inverse preconditioners, SIAM J. sci. comput., 21, 1804, (2000) · Zbl 0957.65023
[92]	Chow, E., Parallel implementation and performance characteristics of sparse approximate inverse preconditioners with a priori sparsity patterns, Int. J. high-perform. comput. appl., 15, 56, (2001)
[93]	Chow, E.; Heroux, M.A., An object-oriented framework for block preconditioning, ACM trans. math. software, 24, 159, (1998) · Zbl 0930.65052
[94]	Chow, E.; Saad, Y., Approximate inverse techniques for block-partitioned matrices, SIAM J. sci. comput., 18, 1657, (1997) · Zbl 0888.65035
[95]	Chow, E.; Saad, Y., Experimental study of ILU preconditioners for indefinite matrices, J. comput. appl. math., 86, 387, (1997) · Zbl 0891.65028
[96]	Chow, E.; Saad, Y., ILUS: an incomplete ILU preconditioner in sparse skyline format, Int. J. numer. methods fluids, 25, 739, (1997) · Zbl 0896.76037
[97]	Chow, E.; Saad, Y., Approximate inverse preconditioners via sparse-sparse iterations, SIAM J. sci. comput., 19, 995, (1998) · Zbl 0922.65034
[98]	Cleary, A.J.; Falgout, R.D.; Henson, V.E.; Jones, J.J.; Manteuffel, T.A.; McCormick, S.F.; Miranda, G.N.; Ruge, J.W., Robustness and scalability of algebraic multigrid, SIAM J. sci. comput., 21, 1886, (2000) · Zbl 0959.65049
[99]	Clift, S.S.; Tang, W.-P., Weighted graph based ordering techniques for preconditioned conjugate gradient methods, Bit, 35, 30, (1995) · Zbl 0839.65110
[100]	Cohen, A.; Masson, R., Wavelet methods for second-order elliptic problems, preconditioning, and adaptivity, SIAM J. sci. comput., 21, 1006, (1999) · Zbl 0981.65132
[101]	Concus, P.; Golub, G.H.; Meurant, G., Block preconditioning for the conjugate gradient method, SIAM J. sci. stat. comput., 6, 220, (1985) · Zbl 0556.65022
[102]	P. Concus, G. H. Golub, and, D. P. O’Leary, A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, in, Sparse Matrix Computations, edited by, J. R. Bunch and D. J. Rose, p, 309, Academic Press, New York, 1976.
[103]	Cosgrove, J.D.F.; Dı́az, J.C.; Griewank, A., Approximate inverse preconditioning for sparse linear systems, Int. J. comput. math., 44, 91, (1992) · Zbl 0762.65025
[104]	E. Cuthill, Several strategies for reducing the bandwidth of matrices, in, Sparse Matrices and Their Applications, p, 157, edited by, D. J. Rose and R. A. Willoughby, Plenum, New York, 1972.
[105]	Dahmen, W.; Elsner, L., Algebraic multigrid methods and the Schur complement, Robust multigrid methods (Kiel 1988), 58, (1989) · Zbl 0689.65011
[106]	Darve, E., The fast multipole method. I. error analysis and asymptotic complexity, SIAM J. numer. anal., 38, 98, (2000) · Zbl 0974.65033
[107]	Darve, E., The fast multipole method: numerical implementation, J. comput. phys., 160, 195, (2000) · Zbl 0974.78012
[108]	T. A. Davis, University of Florida Sparse Matrix Collection, NA Digest, Vol, 92, No, October 16, 1994;
[109]	T. A. Davis, University of Florida Sparse Matrix Collection, NA Digest, Vol, 96, No, July 23, 1996;
[110]	T. A. Davis, University of Florida Sparse Matrix Collection, and NA Digest, Vol, 97, No, June 7, 1997, available at, http://www.cise.ufl.edu/research/sparse/matrices, ftp://ftp.cise.ufl.edu/pub/faculty/davis/matrices.
[111]	D’Azevedo, E.F.; Forsyth, P.A.; Tang, W.-P., Ordering methods for preconditioned conjugate gradient methods applied to unstructured grid problems, SIAM J. matrix anal. appl., 13, 944, (1992) · Zbl 0760.65028
[112]	E. F. D’Azevedo, P. A. Forsyth, and, W.-P. Tang, Two variants of minimum discarded fill ordering, in, Iterative Methods in Linear Algebra, edited by, R. Beauwens and P. de Groen, p, 603, Elsevier Science, North-Holland, 1992.
[113]	Dendy, J.E., Black box multigrid, J. comput. phys., 48, 366, (1980) · Zbl 0495.65047
[114]	E. de Doncker, and, A. K. Gupta, Coarse grain preconditioned conjugate gradient solver for large sparse systems, in, Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, edited by, J. Lewis, p, 472, SIAM, Philadelphia, PA, 1995. · Zbl 0836.65048
[115]	Demko, S.; Moss, W.F.; Smith, P.W., Decay rates for inverses of band matrices, Math. comput., 43, 491, (1984) · Zbl 0568.15003
[116]	Dı́az, J.C.; Komara, K., Incomplete multilevel Cholesky factorizations, SIAM J. matrix anal. appl., 22, 895, (2000) · Zbl 1006.86008
[117]	Doi, S., On parallelism and convergence of incomplete LU factorizations, Appl. numer. math., 7, 417, (1991) · Zbl 0729.65019
[118]	Doi, S.; Washio, T., Ordering strategies and related techniques to overcome the trade-off between parallelism and convergence in incomplete factorizations, Parallel comput., 25, 1995, (1999)
[119]	Dongarra, J.J.; Duff, I.S.; Sorensen, D.C.; van der Vorst, H.A., numerical linear algebra for high-performance computers, (1998), SIAM Philadelphia · Zbl 0914.65014
[120]	Douglas, J.; Rachford, H.H., On the numerical solution of heat conduction problems in two or three space variables, Trans. am. math. soc., 82, 421, (1956) · Zbl 0070.35401
[121]	Drkošsová, J.; Greenbaum, A.; Rozložnik, M.; Strakoš, Z., Numerical stabilty of GMRES, Bit, 35, 309, (1995) · Zbl 0837.65040
[122]	Dubois, P.F.; Greenbaum, A.; Rodrigue, G.H., Approximating the inverse of a matrix for use in iterative algorithms on vector processors, Computing, 22, 257, (1979) · Zbl 0438.65037
[123]	Duff, I.S.; Erisman, A.M.; Gear, C.W.; Reid, J.K., Sparsity structure and Gaussian elimination, SIGNUM newsl., 23, 2, (1988)
[124]	Duff, I.S.; Erisman, A.M.; Reid, J.K., direct methods for sparse matrices, (1986), Clarendon Oxford · Zbl 0604.65011
[125]	I. S. Duff, R. G. Grimes, and, J. G. Lewis, The Rutherford-Boeing Sparse Matrix Collection, Technical Report RAL-TR-97-031, Rutherford Appleton Laboratory, Chilton, UK, 1997.
[126]	Duff, I.S.; Koster, J., The design and use of algorithms for permuting large entries to the diagonal of sparse matrices, SIAM J. matrix anal. appl., 20, 889, (1999) · Zbl 0947.65048
[127]	Duff, I.S.; Koster, J., On algorithms for permuting large entries to the diagonal of a sparse matrix, SIAM J. matrix anal. appl., 22, 973, (2001) · Zbl 0979.05087
[128]	Duff, I.S.; Meurant, G., The effect of ordering on preconditioned conjugate gradients, Bit, 29, 635, (1989) · Zbl 0687.65037
[129]	Dupont, T.; Kendall, R.P.; Rachford, H.H., An approximate factorization procedure for solving self-adjoint elliptic difference equations, SIAM J. numer. anal., 5, 559, (1968) · Zbl 0174.47603
[130]	Dutto, L.C., The effect of ordering on preconditioned GMRES algorithm, for solving the compressible Navier-Stokes equations, Int. J. numer. methods eng., 36, 457, (1993) · Zbl 0767.76026
[131]	Eijkhout, V., Analysis of parallel incomplete point factorizations, Linear algebra its appl., 154, 723, (1991) · Zbl 0737.65025
[132]	V. Eijkhout, Beware of unperturbed modified incomplete factorizations, in, Iterative Methods in Linear Algebra, edited by, R. Beauwens and P. de Groen, p, 583, Elsevier Science, North-Holland, 1992. · Zbl 0785.65022
[133]	Eisenstat, S., Efficient implementation of a class of conjugate gradient methods, SIAM J. sci. stat. comput., 2, 1, (1981) · Zbl 0474.65020
[134]	Elman, H.C., A stability analysis of incomplete LU factorizations, Math. comput., 47, 191, (1986) · Zbl 0621.65024
[135]	Elman, H.C.; Chernesky, M.P., Ordering effects on relaxation methods applied to the discrete one-dimensional convection-diffusion equation, SIAM J. numer. anal., 30, 1268, (1993) · Zbl 0790.65027
[136]	Engeli, M.; Ginsburg, Th.; Rutishauser, H.; Stiefel, E., refined iterative methods for computation of the solution and the eigenvalues of self-adjoint boundary value problems, (1959), Birkhäuser Basel/Stuttgart · Zbl 0089.12103
[137]	Evans, D.J., The use of pre-conditioning in iterative methods for solving linear systems with symmetric positive definite matrices, J. inst. math. its appl., 4, 295, (1968) · Zbl 0232.65031
[138]	Farhat, C.; Roux, F.-X., A method of finite-element tearing and interconnecting and its parallel solution algorithm, Int. J. numer. methods eng., 32, 1205, (1991) · Zbl 0758.65075
[139]	Farhat, C.; Mandel, J.; Roux, F.-X., Optimal convergence properties of the FETI domain decomposition method, Comput. methods appl. mech. eng., 115, 365, (1994)
[140]	Farhat, C.; Mandel, J., The two-level FETI method for static and dynamic plate problems. part I: an optimal iterative solver for biharmonic systems, Comput. methods appl. mech. eng., 155, 129, (1998) · Zbl 0964.74062
[141]	Fedorenko, R.P., A relaxation method for solving elliptic difference equations, USSR comput. math. math. phys., 1, 1092, (1961) · Zbl 0163.39303
[142]	Fedorenko, R.P., The speed of convergence of one iterative process, USSR comput. math. math. phys., 4, 227, (1964) · Zbl 0148.39501
[143]	M. R. Field, An Efficient Parallel Preconditioner for the Conjugate Gradient Algorithm, Hitachi Dublin Laboratory Technical Report HDL-TR-97-175, Dublin, Ireland, 1997.
[144]	M. R. Field, Improving the Performance of Factorised Sparse Approximate Inverse Preconditioner, Hitachi Dublin Laboratory Technical Report HDL-TR-98-199, Dublin, Ireland, 1998.
[145]	Fischer, B., polynomial based iteration methods for symmetric linear systems, (1996), Wiley-Teubner Chichester · Zbl 0852.65031
[146]	R. Fletcher, Conjugate gradient methods for indefinite systems, in, Numerical Analysis Dundee 1975, edited by, G. A. Watson, p, 73, Lecture Notes in Mathematics No. 506, Springer, Berlin, 1976.
[147]	Fox L, L.; Huskey, H.D.; Wilkinson, J.H., Notes on the solution of algebraic linear simultaneous equations, Q. J. mech. appl. math., 1, 149, (1948) · Zbl 0033.28503
[148]	P. O. Frederickson, Fast Approximate Inversion of Large Sparse Linear Systems, Math. Report 7, Lakehead University, Thunder Bay, Ontario, 1975.
[149]	Freund, R., A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. sci. comput., 14, 470, (1993) · Zbl 0781.65022
[150]	Freund, R.; Golub, G.H.; Nachtigal, N.M., Iterative solution of linear systems, Acta numer., 1, 57, (1991)
[151]	Freund, R.; Nachtigal, N.M., QMR: A quasi-minimal residual method for non-Hermitian linear systems, Numer. math., 60, 315, (1991) · Zbl 0754.65034
[152]	George, A., Nested dissection of a regular finite element mesh, SIAM J. numer. anal., 10, 345, (1973) · Zbl 0259.65087
[153]	George, A.; Liu, J.W., computer solution of large sparse positive definite systems, (1981), Prentice-Hall Englewood Cliffs · Zbl 0516.65010
[154]	George, A.; Liu, J.W., The evolution of the minimum degree algorithm, SIAM rev., 31, 1, (1989) · Zbl 0671.65024
[155]	Gibbs, N.E.; Poole, W.G.; Stockmeyer, P.K., An algorithm for reducing the bandwidth and profile of a sparse matrix, SIAM J. numer. anal., 13, 236, (1976) · Zbl 0329.65024
[156]	Gilbert, J.R., Predicting structure in sparse matrix computations, SIAM J. matrix anal. appl., 15, 62, (1994) · Zbl 0796.65061
[157]	Gill, P.E.; Murray, W.; Wright, M.H., practical optimization, (1981), Academic Press London
[158]	Golub, G.H.; O’Leary, D.P., Some history of the conjugate gradient and Lanczos methods: 1948-1976, SIAM rev., 31, 50, (1989) · Zbl 0673.65017
[159]	Golub, G.H.; van Loan, C.F., matrix computations, (1996), Johns Hopkins Press Baltimore
[160]	Golub, G.H.; Ye, Q., Inexact preconditioned conjugate-gradient method with inner-outer iteration, SIAM J. sci. comput., 21, 1305, (1999) · Zbl 0955.65022
[161]	Gould, N.I.M.; Scott, J.A., Sparse approximate-inverse preconditioners using norm-minimization techniques, SIAM J. sci. comput., 19, 605, (1998) · Zbl 0911.65037
[162]	Greenbaum, A., Analysis of a multigrid method as an iterative method for solving linear systems, SIAM J. numer. anal., 21, 473, (1984) · Zbl 0539.65011
[163]	Greenbaum, A., iterative methods for solving linear systems, (1997), SIAM Philadelphia · Zbl 0883.65022
[164]	Greenbaum, A.; Pták, V.; Strakoš, Z., Any nonincreasing convergence curve is possible for GMRES, SIAM J. matrix anal. appl., 17, 465, (1996) · Zbl 0857.65029
[165]	Greenbaum, A.; Strakoš, Z., Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. matrix anal. appl., 13, 121, (1992) · Zbl 0755.65037
[166]	Grote, M.; Huckle, T., Parallel preconditioning with sparse approximate inverses, SIAM J. sci. comput., 18, 838, (1997) · Zbl 0872.65031
[167]	Gustafsson, I., A class of first order factorization methods, Bit, 18, 142, (1978) · Zbl 0386.65006
[168]	Haase, G., Parallel incomplete Cholesky preconditioners based on the nonoverlapping data distribution, Parallel comput., 24, 1685, (1998)
[169]	Hackbusch, W., multi-grid methods and applications, (1985), Springer-Verlag Berlin · Zbl 0585.65030
[170]	Hackbusch, W., iterative solution of large sparse systems of equations, (1994), Springer-Verlag New York
[171]	Hageman, A.L.; Young, D.M., applied iterative methods, (1981), Academic Press New York
[172]	Heniche, M.; Secretan, Y.; Leclerc, M., Efficient ILU preconditioning and inexact-Newton-GMRES to solve the 2D steady shallow water equations, Commun. numer. methods eng., 17, 69, (2001) · Zbl 0986.76040
[173]	Henson, V.E.; Yang, U.M., Boomeramg: A parallel algebraic multigrid solver and preconditioner, Appl. numer. math., 41, 155, (2002) · Zbl 0995.65128
[174]	Hestenes, M.R.; Stiefel, E.L., Methods of conjugate gradients for solving linear systems, J. res. natl. bur. stand., 49, 409, (1952) · Zbl 0048.09901
[175]	Hladı́k, I.; Reed, M.B.; Swoboda, G., Robust preconditioners for linear elasticity FEM analyses, Int. J. numer. methods eng., 40, 2109, (1997) · Zbl 0896.73059
[176]	Householder, A.S., the theory of matrices in numerical analysis, (1964), Blaisdell New York · Zbl 0161.12101
[177]	Huckle, T., Approximate sparsity patterns for the inverse of a matrix and preconditioning, Appl. numer. math., 30, 291, (1999) · Zbl 0927.65045
[178]	Huckle, T., Factorized sparse approximate inverses for preconditioning and smoothing, Selčuk J. appl. math., 1, 63, (2000) · Zbl 1011.65018
[179]	Huckle, T., Factorized sparse approximate inverses for preconditioning, Proceedings of the international conference on parallel and distributed processing techniques and applications (PDPTA 2001), (2001) · Zbl 1027.65056
[180]	Hysom, D., new sequential and scalable parallel algorithms for incomplete factor preconditioning, (2001), Old Dominion Univ.Dep. Computer Science Norfolk
[181]	Hysom, D.; Pothen, A., A scalable parallel algorithm for incomplete factor preconditioning, SIAM J. sci. comput., 22, 2194, (2001) · Zbl 0986.65048
[182]	Il’in, V.P., iterative incomplete factorization methods, (1992), World Scientific · Zbl 0788.65036
[183]	Jacobi, C.G.J., Über eine neue aufiösungsart der bei der methode der kleinsten quadrate vorkommenden linearen gleichungen, Astron. nachrichten, 22, 297, (1845)
[184]	Johnson, O.G.; Micchelli, C.A.; Paul, G., Polynomial preconditioning for conjugate gradient calculations, SIAM J. numer. anal., 20, 362, (1983) · Zbl 0563.65020
[185]	Jones, M.T.; Plassmann, P.E., Scalable iterative solution of sparse linear systems, Parallel comput., 20, 753, (1994) · Zbl 0802.65034
[186]	Jones, M.T.; Plassmann, P.E., An improved incomplete Cholesky factorization, ACM trans. math. software., 21, 5, (1995) · Zbl 0886.65024
[187]	Jones, M.T.; Plassmann, P.E., Algorithm 740: Fortran subroutines to compute improved incomplete Cholesky factorizations, ACM trans. math. software, 21, 18, (1995) · Zbl 0886.65023
[188]	Kaporin, I.E., New convergence results and preconditioning strategies for the conjugate gradient method, Numer. linear algebra appl., 1, 179, (1994) · Zbl 0837.65027
[189]	Kaporin, I.E., High quality preconditioning of a general symmetric positive definite matrix based on its UTU+UTR+RTU decomposition, Numer. linear algebra appl., 5, 483, (1998) · Zbl 0969.65037
[190]	Kaporin, I.E.; Konshin, I.N., A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems, Numer. linear algebra appl., 9, 141, (2002) · Zbl 1071.65513
[191]	Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. sci. comput., 20, 359, (1998) · Zbl 0915.68129
[192]	G. Karypis, and, V. Kumar, Parallel Threshold-Based ILU Factorization, Technical Report 061, Dep. Computer Science/Army HPC Research Center, Univ. Minnesota, Minneapolis, 1998.
[193]	Kershaw, D.S., The incomplete Cholesky conjugate gradient method for the iterative solution of systems of linear equations, J. comput. phys., 26, 43, (1978) · Zbl 0367.65018
[194]	Kharchenko, S.A.; Kolotilina, L.Yu.; Nikishin, A.A.; Yeremin, A.Yu., A robust AINV-type method for constructing sparse approximate inverse preconditioners in factored form, Numer. linear algebra appl., 8, 165, (2001) · Zbl 1051.65057
[195]	Knyazev, A.W., Preconditioned eigensolvers—an oxymoron?, Electron. trans. numer. anal., 7, 104, (1998) · Zbl 1053.65513
[196]	Kolotilina, L.Yu., Explicit preconditioning of systems of linear algebraic equations with dense matrices, J. sov. math., 43, 2566, (1988) · Zbl 0664.65042
[197]	Kolotilina, L.Yu.; Nikishin, A.A.; Yeremin, A.Yu., Factorized sparse approximate inverse preconditionings. IV: simple approaches to rising efficiency, Numer. linear algebra appl., 6, 515, (1999) · Zbl 0983.65062
[198]	Kolotilina, L.Yu.; Yeremin, A.Yu., On a family of two-level preconditionings of the incomplete block factorization type, Sov. J. numer. anal. math. model., 1, 293, (1986) · Zbl 0825.65028
[199]	Kolotilina, L.Yu.; Yeremin, A.Yu., Factorized sparse approximate inverse preconditioning. I. theory, SIAM J. matrix anal. appl., 14, 45, (1993) · Zbl 0767.65037
[200]	Kolotilina, L.Yu.; Yeremin, A.Yu., Factorized sparse approximate inverse preconditioning. II: solution of 3D FE systems on massively parallel computers, Int. J. high speed comput., 7, 191, (1995)
[201]	Krechen, A.; Stüben, K., Parallel algebraic multigrid based on subdomain blocking, Parallel comput., 27, 1009, (2001) · Zbl 0971.68215
[202]	Lanczos, C., Solutions of systems of linear equations by minimized iterations, J. res. natl. bur. stand., 49, 33, (1952)
[203]	Larsen, E.W., Unconditionally stable diffusion-synthetic acceleration methods for the slab geometry discrete ordinates equations. part I: theory, Nucl. sci. eng., 82, 47, (1982)
[204]	Le Borne, S., Ordering techniques for two- and three-dimensional convection-dominated elliptic boundary value problems, Computing, 64, 123, (2000) · Zbl 0969.76072
[205]	Lee, S.L., Krylov methods for the numerical solution of initial-value problems in differential-algebraic equations, (1993), Univ. Illinois at Urbana-ChampaignDep. Computer Science
[206]	N. Li, Y. Saad, and, M. Sosonkina, pARMS: A Parallel Version of the Algebraic Recursive Multilevel Solver, Technical Report UMSI-2001-100, Minnesota Supercomputer Institute, Univ. Minnesota, Minneapolis, 2001. · Zbl 1071.65532
[207]	Lin, C.-J.; Moré, J.J., Incomplete Cholesky factorizations with limited memory, SIAM J. sci. comput., 21, 24, (1999) · Zbl 0941.65033
[208]	Lin, C.-J.; Saigal, R., An incomplete Cholesky factorization for dense symmetric positive definite matrices, Bit, 40, 536, (2000) · Zbl 0960.65033
[209]	Lipton, R.J.; Rose, D.J.; Tarjan, R.E., Generalized nested dissection, SIAM J. numer. anal., 16, 346, (1979) · Zbl 0435.65021
[210]	Liu, J.W.H., Modification of the minimum degree algorithm by multiple elimination, ACM trans. math. software, 11, 141, (1985) · Zbl 0568.65015
[211]	Liu, J.W.H.; Ng, E.G.; Peyton, B.W., On finding supernodes for sparse matrix computations, SIAM J. matrix anal. appl., 14, 242, (1993) · Zbl 0765.65034
[212]	Magolu monga Made, M., Incomplete factorization based preconditionings for solving the Helmholtz equation, Int. J. numer. methods eng., 50, 1077, (2001) · Zbl 0977.65102
[213]	Magolu monga Made, M.; Beauwens, R.; Warzée, G., Preconditioning of discrete Helmholtz operators perturbed by a diagonal complex matrix, Commun. numer. methods eng., 16, 801, (2000) · Zbl 0972.65031
[214]	Magolu monga Made, M.; Polman, B., Experimental comparison of three-dimensional point and line modified incomplete factorization, Numer. algorithms, 23, 51, (2000) · Zbl 0948.65029
[215]	Magolu monga Made, M.; van der Vorst, H.A., Parallel incomplete factorizations with pseudooverlapping subdomains, Parallel comput., 27, 989, (2001) · Zbl 0971.68060
[216]	Manteuffel, T.A., An incomplete factorization technique for positive definite linear systems, Math. comput., 34, 473, (1980) · Zbl 0422.65018
[217]	McCoy, D.R.; Larsen, E.W., Unconditionally stable diffusion-synthetic acceleration methods for the slab geometry discrete ordinates equations. part II: numerical results, Nucl. sci. eng., 82, 64, (1982)
[218]	Meijerink, J.A.; van der Vorst, H.A., An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. comput., 31, 148, (1977) · Zbl 0349.65020
[219]	Meurant, G.A., A review of the inverse of symmetric tridiagonal and block tridiagonal matrices, SIAM J. matrix anal. appl., 13, 707, (1992) · Zbl 0754.65029
[220]	G. A. Meurant, Computer Solution of Large Linear Systems, Studies in Mathematics and Its Applications, Vol, 28, North-Holland, Amsterdam, 1999. · Zbl 0934.65032
[221]	Meurant, G.A., A multilevel AINV preconditioner, Numer. algorithms, 29, 107, (2002) · Zbl 1044.65036
[222]	Meurant, G.A., Numerical experiments with algebraic multilevel preconditioners, Electron. trans. numer. anal., 12, 1, (2001) · Zbl 0974.65040
[223]	Milyukova, O.Yu., Parallel approximate factorization method for solving discrete elliptic equations, Parallel comput., 27, 1365, (2001) · Zbl 0969.68193
[224]	Morgan, R.B., Preconditioning eigenvalues and some comparison of solvers, J. comput. appl. math., 123, 101, (2000) · Zbl 0979.65028
[225]	Mousseau, V.A.; Knoll, D.A.; Rider, W.J., Physics-based preconditioning and the newton – krylov method for non-equilibrium radiation diffusion, J. comput. phys., 160, 743, (2000) · Zbl 0949.65092
[226]	Murphy, M.F.; Golub, G.H.; Wathen, A.J., A note on preconditioning for indefinite linear systems, SIAM J. sci. comput., 21, 1969, (2000) · Zbl 0959.65063
[227]	Nash, S.G., A history of scientific computing, (1990), Addison-Wesley Reading
[228]	National Institute of Standards, Matrix Market, available online at, http://math.nist.gov/MatrixMarket.
[229]	Ng, E.; Peyton, B.W.; Raghavan, P., A blocked incomplete Cholesky preconditioner for hierarchical-memory computers, (), 211
[230]	Notay, Y., Using approximate inverses in algebraic multilevel methods, Numer. math., 80, 397, (1998) · Zbl 0911.65027
[231]	Notay, Y., A multilevel block incomplete factorization preconditioning, Appl. numer. math., 31, 209, (1999) · Zbl 0960.65053
[232]	Notay, Y., Optimal order preconditioning of finite difference matrices, SIAM J. sci. comput., 21, 1991, (2000) · Zbl 0959.65064
[233]	Notay, Y., Flexible conjugate gradient, SIAM J. sci. comput., 22, 1444, (2000) · Zbl 0980.65030
[234]	Oliphant, T.A., An extrapolation process for solving linear systems, Q. appl. math., 20, 257, (1962) · Zbl 0109.34601
[235]	Olschowka, M.; Neumaier, A., A new pivoting strategy for Gaussian elimination, Linear algebra its appl., 240, 131, (1996) · Zbl 0852.65021
[236]	O’Neil, J.; Szyld, D.B., A block ordering method for sparse matrices, SIAM J. sci. stat. comput., 11, 811, (1990) · Zbl 0706.65021
[237]	Ong, H.L., Fast approximate solution of large scale sparse linear systems, J. comput. appl. math., 10, 45, (1984) · Zbl 0529.65064
[238]	Padiy, A.; Axelsson, O.; Polman, B., Generalized augmented matrix preconditioning approach and its application to iterative solution of ill-conditioned algebraic systems, SIAM J. matrix anal. appl., 22, 793, (2001) · Zbl 0982.65053
[239]	Paige, C.C.; Saunders, M.A., Solution of sparse indefinite systems of linear equations, SIAM J. numer. anal., 12, 617, (1975) · Zbl 0319.65025
[240]	Peaceman, D.W.; Rachford, H.H., The numerical solution of parabolic and elliptic differential equations, J. soc. ind. appl. math., 3, 28, (1955) · Zbl 0067.35801
[241]	Poole, E.L.; Ortega, J.M., Multicolor ICCG methods for vector computers, SIAM J. numer. anal., 24, 1394, (1987) · Zbl 0646.65032
[242]	Qu, Y.; Fish, J., Global-basis two-level method for indefinite systems. part 2: computational issues, Int. J. numer. methods eng., 49, 461, (2000)
[243]	Quarteroni, A.; Valli, A., domain decomposition methods for partial differential equations, (1999), Clarendon Oxford · Zbl 0931.65118
[244]	J. K. Reid, On the method of conjugate gradients for the solution of large sparse systems of linear equations, in, Large Sparse Sets of Linear Equations, edited by, J. K. Reid, p, 231, Academic Press, New York, 1971.
[245]	Reusken, A., A multigrid method based on incomplete Gaussian elimination, Numer. linear algebra appl., 3, 369, (1996) · Zbl 0906.65118
[246]	Robert, Y., Regular incomplete factorizations of real positive definite matrices, Linear algebra its appl., 48, 105, (1982) · Zbl 0502.65018
[247]	J. W. Ruge, and, K. Stüben, Algebraic multigrid, in, Multigrid Methods, edited by, S. F. McCormick, p, 73, SIAM, Philadelphia, PA, 1987.
[248]	Saad, Y., Preconditioning techniques for nonsymmetric and indefinite linear systems, J. comput. appl. math., 24, 89, (1988) · Zbl 0662.65028
[249]	Saad, Y., Krylov subspace methods on supercomputers, SIAM J. sci. stat. comput., 10, 1200, (1989) · Zbl 0693.65028
[250]	Saad, Y., A flexible inner-outer preconditioned GMRES algorithm, SIAM J. sci. comput., 14, 461, (1993) · Zbl 0780.65022
[251]	Saad, Y., ILUT: A dual threshold incomplete LU factorization, Numer. linear algebra appl., 1, 387, (1994) · Zbl 0838.65026
[252]	Y. Saad, Highly parallel preconditioners for general sparse matrices, in, Recent Advances in Iterative Methods, edited by, G. H. Golub, R. M. Luskin, and A. Greenbaum, p, 165, IMA Volumes in Mathematics and Its Applications, Vol, 60, Springer-Verlag, New York, 1994.
[253]	Saad, Y., ILUM: A multi-elimination ILU preconditioner for general sparse matrices, SIAM J. sci. comput., 17, 830, (1996) · Zbl 0858.65029
[254]	Saad, Y., iterative methods for sparse linear systems, (1996), PWS Publishing Boston · Zbl 1002.65042
[255]	Y. Saad, Finding Exact and Approximate Block Structures for ILU Preconditioning, Technical Report UMSI-2001-93, Minnesota Supercomputer Institute, Univ. Minnesota, Minneapolis, 2001. · Zbl 1034.65020
[256]	Saad, Y.; Schultz, M.H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. sci. stat. comput., 7, 856, (1986) · Zbl 0599.65018
[257]	Saad, Y.; Suchomel, B., ARMS: an algebraic recursive multilevel solver for general sparse linear systems, Numer. linear algebra appl., 9, 359, (2002) · Zbl 1071.65001
[258]	Saad, Y.; van der Vorst, H.A., Iterative solution of linear systems in the 20th century, J. comput. appl. math., 123, 1, (2000) · Zbl 0965.65051
[259]	Saad, Y.; Zhang, J., BILUM: block versions of multielimination and multilevel preconditioner for general sparse linear systems, SIAM J. sci. comput., 20, 2103, (1999) · Zbl 0956.65026
[260]	Saad, Y.; Zhang, J., BILUTM: A domain-based multilevel block ILUT preconditioner for general sparse matrices, SIAM J. matrix anal. appl., 21, 279, (1999) · Zbl 0942.65045
[261]	Saint-Georges, P.; Warzee, G.; Notay, Y.; Beauwens, R., High-performance PCG solvers for FEM structural analyses, Int. J. numer. methods eng., 39, 1133, (1996) · Zbl 0886.73071
[262]	Saint-Georges, P.; Warzee, G.; Notay, Y.; Beauwens, R., Problem-dependent preconditioners for iterative solvers in FE elastostatics, Comput. struct., 73, 33, (1999) · Zbl 1048.74591
[263]	Schnabel, R.B.; Eskow, E., A new modified Cholesky factorization, SIAM J. sci. stat. comput., 11, 1136, (1990) · Zbl 0716.65023
[264]	Sheldon, J.W., On the numerical solution of elliptic difference equations, Math. tables other aids comput., 9, 101, (1955) · Zbl 0065.35801
[265]	G. L. G. Sleijpen, and, F. W. Wubs, Exploiting Multilevel Preconditioning Techniques in Eigenvalue Computations, Preprint nr. 1117, Dep. Mathematics, Univ. Utrecht, Utrecht, The Netherlands, 1999; revised version, 2001. · Zbl 1061.65030
[266]	Sloan, S.W., An algorithm for profile and wavefront reduction of sparse matrices, Int. J. numer. methods eng., 23, 239, (1986) · Zbl 0601.65027
[267]	Smith, B.F.; Bjørstad, P.E.; Gropp, W.D., domain decomposition: parallel multilevel methods for elliptic partial differential equations, (1996), Cambridge Univ. Press Cambridge/New York/Melbourne · Zbl 0857.65126
[268]	Smith, R.D.; Dukowicz, J.K.; Malone, R.C., Parallel Ocean general circulation modeling, Phys. D, 60, 38, (1992) · Zbl 0779.76064
[269]	Stüben, K., Algebraic multigrid (AMG): experiences and comparisons, Appl. math. comput., 13, 419, (1983) · Zbl 0533.65064
[270]	Stüben, K., A review of algebraic multigrid, J. comput. appl. math., 128, 281, (2001) · Zbl 0979.65111
[271]	Suarjana, M.; Law, K.H., A robust incomplete factorization based on value and space constraints, Int. J. numer. methods eng., 38, 1703, (1995) · Zbl 0822.73073
[272]	Szyld, D.B.; Vogel, J., FQMR: A flexible quasi-minimal residual method with inexact preconditioning, SIAM J. sci. comput., 23, 363, (2001) · Zbl 0997.65062
[273]	Tang, W.-P.; Wan, W.-L., Sparse approximate inverse smoother for multigrid, SIAM J. matrix anal. appl., 21, 1236, (2000) · Zbl 1049.65146
[274]	Tismenetsky, M., A new preconditioning technique for solving large sparse linear systems, Linear algebra its appl., 154-156, 331, (1991) · Zbl 0732.65030
[275]	Trefethen, L.N.; Bau, D., numerical linear algebra, (1997), SIAM Philadelphia
[276]	Trottenberg, U.; Oosterlee, C.W.; Schüller, A., multigrid, (2000), Academic Press London
[277]	Turing, A.M., Rounding-off errors in matrix processes, Q. J. mech. appl. math., 1, 287, (1948) · Zbl 0033.28501
[278]	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 José, CA, 1976.
[279]	van der Ploeg, A.; Botta, E.F.F.; Wubs, F.W., Nested grids ILU-decomposition (NGILU), J. comput. appl. math., 66, 515, (1996) · Zbl 0858.65028
[280]	van der Vorst, H.A., Iterative solution methods for certain sparse linear systems with a nonsymmetric matrix arising from PDE-problems, J. comput. phys., 44, 1, (1981) · Zbl 0472.65027
[281]	van der Vorst, H.A., Large tridiagonal and block tridiagonal linear systems on vector and parallel computers, Parallel comput., 5, 45, (1987) · Zbl 0632.65034
[282]	H. A. van der Vorst, The convergence behaviour of preconditioned CG and CGS in the presence of rounding errors, in, Preconditioned Conjugate Gradient Methods, edited by, O. Axelsson and L. Yu. Kolotilina, p, 126, Lecture Notes in Mathematics, Vol, 1457, Springer-Verlag, Berlin, 1990. · Zbl 0714.65034
[283]	van der Vorst, H.A., Bi-CGSTAB: A fast and smoothly converging variant of bi-CG for the solution of non-symmetric linear systems, SIAM J. sci. stat. comput., 12, 631, (1992) · Zbl 0761.65023
[284]	R. S. Varga, Factorizations and normalized iterative methods, in, Boundary Problems in Differential Equations, edited by, R. E. Langer, p, 121, Univ. Wisconsin Press, Madison, 1960.
[285]	Varga, R.S., matrix iterative analysis, (1962), Prentice-Hall Englewood Cliffs · Zbl 0133.08602
[286]	Varga, R.S.; Saff, E.B.; Mehrmann, V., Incomplete factorizations of matrices and connections with H-matrices, SIAM J. numer anal., 17, 787, (1980) · Zbl 0477.65020
[287]	Vassilevski, P.S., A block-factorization (algebraic) formulation of multigrid and Schwarz methods, East-west J. numer. math., 6, 65, (1998) · Zbl 0915.65120
[288]	Vuik, C.; van Nooyen, R.P.; Wesseling, P., Parallelism in ILU-preconditioned GMRES, Parallel comput., 24, 1927, (1998)
[289]	Wachspress, E., iterative solution of elliptic systems and applications to the neutron diffusion equations of reactor physics, (1966), Prentice-Hall Englewood Cliffs · Zbl 0161.12203
[290]	J. S. Warsa, T. A. Wareing, and, J. E. Morel, Solution of the discontinuous P1 equations in two-dimensional Cartesian geometry with two-level preconditioning, SIAM J. Sci. Comput, in press. · Zbl 1035.65133
[291]	Watts, J.W., A conjugate gradient truncated direct method for the iterative solution of the reservoir simulation pressure equation, Soc. petrol. eng. J., 21, 345, (1981)
[292]	Weiss, R., parameter-free iterative linear solvers, (1996), Akademie Berlin · Zbl 0858.65031
[293]	Wittum, G., On the robustness of ILU-smoothing, SIAM J. sci. stat. comput., 10, 699, (1989) · Zbl 0677.65096
[294]	Worley, P.H., Limits on parallelism in the numerical solution of linear pdes, SIAM J. sci. stat. comput., 12, 1, (1991) · Zbl 0719.65086
[295]	Wu, K.; Saad, Y.; Stathopoulos, A., Inexact Newton preconditioning techniques for large symmetric eigenvalue problems, Electron. trans. numer. anal., 7, 202, (1998) · Zbl 0916.65035
[296]	Young, D.M., iterative methods for solving partial difference equations of elliptic type, (1950), Harvard University Cambridge
[297]	Young, D.M., iterative solution of large linear systems, (1971), Academic Press New York · Zbl 0204.48102
[298]	Zhang, J., Sparse approximate inverse and multilevel block ILU preconditioning techniques for general sparse matrices, Appl. numer. math., 35, 67, (2000) · Zbl 0966.65043
[299]	Zhang, J., A multilevel dual reordering strategy for robust incomplete LU factorization of indefinite matrices, SIAM J. matrix anal. appl., 22, 925, (2001) · Zbl 0993.65037