×

Iterative solution of linear systems in the 20th century. (English) Zbl 0965.65051

This paper gives an excellent survey of the development of iterative methods for solving linear algebraic equations. After a historic perspective relaxation-based methods are first discussed. Richardson and projection methods as well as second-order and polynomial accelerations are then described. After examining the Krylov subspace methods, preconditioning is examined including incomplete factorization, parallel and multilevel preconditioners. Multigrid methods are finally discussed.

MSC:

65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65Y05 Parallel numerical computation
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65-03 History of numerical analysis
01A60 History of mathematics in the 20th century
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, E. C.; Saad, Y., Solving sparse triangular systems on parallel computers, Internat. J. High Speed Comput., 1, 73-96 (1989) · Zbl 0726.65026
[2] Arnoldi, W. E., The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9, 17-29 (1951) · Zbl 0042.12801
[3] Axelsson, O., A generalized SSOR method, BIT, 12, 443-467 (1972) · Zbl 0256.65046
[5] Axelsson, O., Conjugate gradient type-methods for unsymmetric and inconsistent systems of linear equations, Linear Algebra Appl., 29, 1-16 (1980) · Zbl 0439.65020
[6] Axelsson, O., A general incomplete block-factorization method, Linear Algebra Appl., 74, 179-190 (1986) · Zbl 0622.65023
[7] Axelsson, O., Iterative Solution Methods (1994), Cambridge University Press: Cambridge University Press New York · Zbl 0795.65014
[8] Axelsson, O.; Lindskog, G., On the eigenvalue distribution of a class of preconditioning methods, Numer. Math., 48, 479-498 (1986) · Zbl 0564.65016
[9] Axelsson, O.; Vassilevski, P., Algebraic multilevel preconditioning methods, I, Numer. Math., 56, 157-177 (1989) · Zbl 0661.65110
[10] Axelsson, O.; Vassilevski, P., Algebraic multilevel preconditioning methods, II, SIAM J. Numer. Anal., 27, 6, 1569-1590 (1990) · Zbl 0715.65091
[11] Axelsson, O.; Vassilevski, P. S., A black box generalized conjugate gradient solver with inner iterations and variable-step preconditioning, SIAM J. Matrix Anal. Appl., 12, 4, 625-644 (1991) · Zbl 0748.65028
[12] Bank, R. E.; Chan, T. F., An analysis of the composite step biconjugate gradient method, Numer. Math., 66, 295-319 (1993) · Zbl 0802.65038
[13] 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: SIAM Philadelphia, PA
[16] Benson, M. W.; Frederickson, P. O., Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems, Utilitas Math., 22, 127-140 (1982) · Zbl 0502.65020
[18] Benzi, M.; Meyer, C. D.; Tůma, M., A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput., 17, 1135-1149 (1996) · Zbl 0856.65019
[19] Benzi, M.; Szyld, D. B.; van Duin, A., Orderings for incomplete factorization preconditioning of nonsymmetric problems, SIAM J. Sci. Comput., 20, 1652-1670 (1999) · Zbl 0940.65033
[20] Berryman, H.; Saltz, J.; Gropp, W.; Mirchandaney, R., Krylov methods preconditioned with incompletely factored matrices on the CM-2, J. Partial Distrib. Comput., 8, 186-190 (1990)
[21] Birkhoff, G., Solving elliptic problems: 1930-1980, (Schultz, M. H., Elliptic Problem Solver (1981), Academic Press: Academic Press New York), 17-38
[22] Björck, A.; Elfving, T., Accelerated projection methods for computing pseudo-inverse solutions of systems of linear equations, BIT, 19, 145-163 (1979) · Zbl 0409.65022
[23] Bodewig, E., Matrix Calculus (1956), North-Holland: North-Holland Amsterdam · Zbl 0086.32501
[24] Bodewig, E., Matrix Calculus (second revised and enlarged edition) (1959), North-Holland: North-Holland Amsterdam · Zbl 0086.32501
[25] Bramley, R.; Sameh, A., Row projection methods for large nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 13, 168-193 (1992) · Zbl 0752.65024
[27] Brandt, A., Multi-level adaptive solutions to boundary value problems, Math. Comp., 31, 333-390 (1977) · Zbl 0373.65054
[28] Brezinski, C., Padé-Type Approximation and General Orthogonal Polynomials (1980), Birkhäuser: Birkhäuser Basel · Zbl 0418.41012
[29] Brezinski, C., Projection Methods for Systems of Equations (1997), North-Holland: North-Holland Amsterdam · Zbl 0867.65009
[30] Brezinski, C.; Redivo-Zaglia, M., Look-ahead in bicgstab and other product methods for linear systems, BIT, 35, 169-201 (1995) · Zbl 0831.65032
[31] Brezinski, C.; Redivo-Zaglia, M.; Sadok, H., Avoiding breakdown and near-breakdown in Lanczos type algorithms, Numer. Algorithms, 1, 261-284 (1991) · Zbl 0748.65033
[32] Brezinski, C.; Redivo-Zaglia, M.; Sadok, H., A breakdown-free Lanczos’ type algorithm for solving linear systems, Numer. Math., 63, 29-38 (1992) · Zbl 0739.65027
[33] Briggs, W. L., A Multigrid Tutorial (1987), SIAM: SIAM Philadelphia, PA
[34] Brown, P. N., A theoretical comparison of the Arnoldi and GMRES algorithms, SIAM J. Sci. Statist. Comput., 12, 58-78 (1991) · Zbl 0719.65022
[35] Broyden, G. C., A new method of solving nonlinear simultaneous equations, Comput. J., 12, 94-99 (1969) · Zbl 0164.45101
[37] Cesari, L., Sulla risoluzione dei sistemi di equazioni lineari per approssimazioni successive, Atti Accad. Naz. Lincei. Rend. Cl. Sci. Fis. Mat. Nat. Ser. 6a, 25, 422-428 (1937) · JFM 63.0524.01
[38] Chan, T. F.; Gallopoulos, E.; Simoncini, V.; Szeto, T.; Tong, C. H., A quasi-minimal residual variant of the Bi-CGSTAB algorithm for nonsymmetric systems, SIAM J. Sci. Comput., 15, 338-347 (1994) · Zbl 0803.65038
[39] Chan, T. F.; Goovaerts, D., A note on the efficiency of domain decomposed incomplete factorizations, SIAM J. Sci. Statist. Comput., 11, 794-803 (1990) · Zbl 0707.65083
[41] Chazan, D.; Miranker, M., Chaotic relaxation, Linear Algebra Appl., 2, 199-222 (1969) · Zbl 0225.65043
[42] Chow, E.; Saad, Y., Approximate inverse techniques for block-partitioned matrices, SIAM J. Sci. Comput., 18, 1657-1675 (1997) · Zbl 0888.65035
[43] Chow, E.; Saad, Y., Approximate inverse preconditioners via sparse-sparse iterations, SIAM J. Sci. Comput., 19, 995-1023 (1998) · Zbl 0922.65034
[44] Cimmino, G., Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, Ric. Sci. Progr. Tecn. Econom. Naz., 9, 326-333 (1938) · JFM 64.1244.02
[45] Concus, P.; Golub, G. H., A generalized conjugate gradient method for nonsymmetric systems of linear equations, (Glowinski, R.; Lions, J. L., Computing Methods in Applied Sciences and Engineering (1976), Springer: Springer New York), 56-65
[46] Concus, P.; Golub, G. H.; Meurant, G., Block preconditioning for the conjugate gradient method, SIAM J. Sci. Statist. Comput., 6, 220-252 (1985) · Zbl 0556.65022
[47] Concus, P.; Golub, G. H.; O’Leary, D. P., A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, (Bunch, J. R.; Rose, D. J., Sparse Matrix Computations (1976), Academic Press: Academic Press New York), 309-332 · Zbl 0385.65048
[48] Cosgrove, J. D.F.; Dı́az, J. C.; Griewank, A., Approximate inverse preconditioning for sparse linear systems, Internat. J. Comput. Math., 44, 91-110 (1992) · Zbl 0762.65025
[49] Cullum, J.; Greenbaum, A., Relations between Galerkin and norm-minimizing iterative methods for solving linear systems, SIAM J. Matrix Anal. Appl., 17, 223-247 (1996) · Zbl 0855.65021
[50] Daniel, J. W., The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal., 4, 10-26 (1967) · Zbl 0154.40302
[51] Daniel, J. W., The Approximate Minimization of Functionals (1971), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0208.42901
[52] D’Azevedo, E. F.; Forsyth, F. A.; Tang, W. P., Ordering methods for preconditioned conjugate gradient methods applied to unstructured grid problems, SIAM J. Matrix Anal. Appl., 13, 944-961 (1992) · Zbl 0760.65028
[53] D’Azevedo, E. F.; Forsyth, F. A.; Tang, W. P., Towards a cost effective ILU preconditioner with high level fill, BIT, 31, 442-463 (1992) · Zbl 0761.65017
[54] de Boor, C.; Rice, J. R., Extremal polynomials with applications to Richardson iteration for indefinite systems, SIAM J. Sci. Statist. Comput., 3, 47-57 (1982) · Zbl 0476.65021
[55] Dedekind, R., Gauss in seiner Vorlesung über die Methode der kleisten Quadrate, Gesammelte Math. Werke, 2, 293-306 (1901)
[56] DeLong, M. A.; Ortega, J. M., SOR as a preconditioner, Appl. Numer. Math., 18, 431-440 (1995) · Zbl 0840.65018
[57] Dongarra, J. J.; Duff, I. S.; Sorensen, D. C.; van der Vorst, H. A., Numerical Linear Algebra for High-Performance Computers (1998), SIAM: SIAM Philadelphia, PA · Zbl 0914.65014
[58] Dubois, P. F.; Greenbaum, A.; Rodrigue, G. H., Approximating the inverse of a matrix for use on iterative algorithms on vectors processors, Computing, 22, 257-268 (1979) · Zbl 0438.65037
[59] Duff, I. S.; Meurant, G. A., The effect of ordering on preconditioned conjugate gradients, BIT, 29, 635-657 (1989) · Zbl 0687.65037
[60] Dupont, T.; Kendall, R.; Rachford, H., An approximate factorization procedure for solving self-adjoint elliptic difference equations, SIAM J. Numer. Anal., 5, 559-573 (1968) · Zbl 0174.47603
[61] Eirola, T.; Nevanlinna, O., Accelerating with rank-one updates, Linear Algebra Appl., 121, 511-520 (1989) · Zbl 0683.65018
[62] Eisenstat, S. C.; Elman, H. C.; Schultz, M. H., Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal., 20, 345-357 (1983) · Zbl 0524.65019
[63] Elman, H. C., A stability analysis of incomplete LU factorizations, Math. Comp., 47, 191-217 (1986) · Zbl 0621.65024
[64] Elman, H. C., Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems, BIT, 29, 890-915 (1989) · Zbl 0694.65011
[65] Elman, H. C.; Golub, G. H., Line iterative methods for cyclically reduced discrete convection-diffusion problems, SIAM J. Sci. Statist. Comput., 13, 339-363 (1992) · Zbl 0752.65067
[66] Elman, H. C.; Saad, Y.; Saylor, P., A hybrid Chebyshev Krylov subspace algorithm for solving nonsymmetric systems of linear equations, SIAM J. Sci. Statist. Comput., 7, 840-855 (1986) · Zbl 0613.65031
[70] Evans, D. J., The use of pre-conditioning in iterative methods for solving linear equations with symmetric positive definite matrices, J. Inst. Math. Appl., 4, 295-314 (1968) · Zbl 0232.65031
[71] Faber, V.; Manteuffel, T., Necessary and sufficient conditions for the existence of a conjugate gradient method, SIAM J. Numer. Anal., 21, 352-361 (1984) · Zbl 0546.65010
[73] Fedorenko, R. P., On the speed of convergence of an iteration process, USSR Comput. Math. Math. Phys., 4, 227-235 (1964) · Zbl 0148.39501
[74] Fischer, B.; Reichel, L., A stable Richardson iteration method for complex linear systems, Numer. Math., 54, 225-241 (1988) · Zbl 0641.65030
[75] Flanders, D. A.; Shortley, G., Numerical determination of fundamental modes, J. Appl. Phys., 21, 1322-1328 (1950)
[76] Fletcher, R., Conjugate gradient methods for indefinite systems, (Watson, G. A., Proceedings of the Dundee Biennal Conference on Numerical Analysis 1974 (1975), Springer: Springer New York), 73-89 · Zbl 0326.65033
[77] Fokkema, D. R.; Sleijpen, G. L.G.; van der Vorst, H. A., Generalized conjugate gradient squared, J. Comput. Appl. Math., 71, 125-146 (1994) · Zbl 0856.65021
[78] Frankel, S., Convergence rates of iterative treatments of partial differential equations, MTAC, 65-75 (1950)
[79] Freund, R. W., A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. Sci. Comput., 14, 2, 470-482 (1993) · Zbl 0781.65022
[81] Freund, R. W.; Nachtigal, N. M., QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60, 315-339 (1991) · Zbl 0754.65034
[82] Gallivan, K.; Sameh, A.; Zlatev, Z., A parallel hybrid sparse linear system solver, Comput. Systems Eng., 1, 2-4, 183-195 (1990)
[83] Gastinel, N., Analyse Numérique Linéaire (1966), Hermann: Hermann Paris · Zbl 0151.21202
[84] Gauss, C. F., Werke, Band IX (1903), Teubner: Teubner Leipzig
[86] Golub, G. H.; O’Leary, D. P., Some history of the conjugate gradient and Lanczos algorithms: 1948-1976, SIAM Rev., 31, 50-102 (1989) · Zbl 0673.65017
[87] Golub, G. H.; Varga, R. S., Chebyshev semi iterative methods successive overrelaxation iterative methods and second order Richardson iterative methods, Numer. Math., 3, 147-168 (1961) · Zbl 0099.10903
[88] Greenbaum, A., Iterative Methods for Solving Linear Systems (1997), SIAM: SIAM Philadelphia, PA · Zbl 0883.65022
[89] Greenbaum, A.; Strakos̆, Z., Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl., 13, 121-137 (1992) · Zbl 0755.65037
[90] Greenbaum, A.; Strakos̆, Z., Matrices that generate the same Krylov residual spaces, (Golub, G.; Luskin, M.; Greenbaum, A., Recent Advances in Iterative Methods. Recent Advances in Iterative Methods, IMA Volumes in Mathematics and Its Applications, Vol. 60 (1994), Springer: Springer New York), 95-119 · Zbl 0803.65029
[91] Greenbaum, A.; Ptak, V.; Strakoš, Z., Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17, 465-469 (1996) · Zbl 0857.65029
[92] Grote, M.; Huckle, T., Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18, 838-853 (1997) · Zbl 0872.65031
[93] Grote, M.; Simon, H. D., Parallel preconditioning and approximate inverses on the connection machine, (Sincovec, R. F.; Keyes, D. E.; Petzold, L. R.; Reed, D. A., Parallel Processing for Scientific Computing, Vol. 2 (1992), SIAM: SIAM Philadelphia, PA), 519-523
[94] Gustafsson, I., A class of first order factorization methods, BIT, 18, 142-156 (1978) · Zbl 0386.65006
[95] Gutknecht, M. H., A completed theory of the unsymmetric Lanczos process and related algorithms, Part I, SIAM J. Matrix Anal. Appl., 13, 594-639 (1992) · Zbl 0760.65039
[96] Hackbusch, W., Multi-Grid Methods and Applications (1985), Springer: Springer New York · Zbl 0585.65030
[97] Hackbusch, W., Iterative Solution of Large Linear Systems of Equations (1994), Springer: Springer New York
[98] Hageman, A. L.; Young, D. M., Applied Iterative Methods (1981), Academic Press: Academic Press New York · Zbl 0459.65014
[99] Hayes, R. M., Iterative methods of solving linear systems on Hilbert space, National Bureau of Standards, Appl. Math. Ser., 39, 71-103 (1954) · Zbl 0058.10703
[101] Hestenes, M. R.; Stiefel, E. L., Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards Section B, 49, 409-436 (1952) · Zbl 0048.09901
[102] Householder, A. S., Theory of Matrices in Numerical Analysis (1964), Blaisdell Publishing Company: Blaisdell Publishing Company Johnson, CO · Zbl 0161.12101
[103] Jea, K. C.; Young, D. M., Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods, Linear Algebra Appl., 34, 159-194 (1980) · Zbl 0463.65025
[104] Johnson, O. G.; Micchelli, C. A.; Paul, G., Polynomial preconditionings for conjugate gradient calculations, SIAM J. Numer. Anal., 20, 362-376 (1983) · Zbl 0563.65020
[106] Kaczmarz, S., Angenäherte Auflösung von Systemen linearer Gleichungen, Bull. Internat. Acad. Pol. Sci. Lett. A, 35, 355-357 (1937) · Zbl 0017.31703
[108] Kamath, C.; Sameh, A., A projection method for solving nonsymmetric linear systems on multiprocessors, Parallel Comput., 9, 291-312 (1988/89) · Zbl 0668.65028
[109] Kaniel, S., Estimates for some computational techniques in linear algebra, Math. Comp., 20, 369-378 (1966) · Zbl 0156.16202
[111] Karush, W., Convergence of a method of solving linear problems, Proc. Amer. Math. Soc., 3, 839-851 (1952) · Zbl 0048.09504
[112] Khabaza, I. M., An iterative least-square method suitable for solving large sparse matrices, Comput. J., 6, 202-206 (1963) · Zbl 0131.33901
[113] Kolotilina, L. Yu.; Yeremin, A. Yu., On a family of two-level preconditionings of the incomplete block factorization type, Soviet J. Numer. Anal. Math. Modelling, 1, 293-320 (1986) · Zbl 0825.65028
[114] Kolotilina, L. Yu.; Yeremin, A. Yu., Factorized sparse approximate inverse preconditionings I, Theory, SIAM J. Matrix Anal. Appl., 14, 45-58 (1993) · Zbl 0767.65037
[115] Lanczos, C., An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Standards, 45, 255-282 (1950)
[116] Lanczos, C., Chebyshev polynomials in the solution of large-scale linear systems, Toronto Symposium on Computing Techniques, 124-133 (1952)
[117] Lanczos, C., Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards, 49, 33-53 (1952)
[118] Liebmann, H., Die angenäherte harmonischer Funktionen und konformer Abbildungen (nach Ideen von Boltzmann und Jacobi), S. B. Math. Nat. Kl. Bayerischen Akad. Wiss. München, 385-416 (1918) · JFM 46.0559.01
[119] Luenberger, D. G., Hyperbolic pairs in the method of conjugate gradients, SIAM J. Appl. Math., 17, 1263-1267 (1979) · Zbl 0187.09704
[120] Magolu, M. M., Modified block-approximate factorization strategies, Numer. Math., 61, 91-110 (1992) · Zbl 0724.65029
[121] Magolu, M. M., Ordering strategies for modified block incomplete factorizations, SIAM J. Sci. Comput., 16, 378-399 (1995) · Zbl 0820.65014
[122] Manteuffel, T. A., The Tchebychev iteration for nonsymmetric linear systems, Numer. Math., 28, 307-327 (1977) · Zbl 0361.65024
[123] Manteuffel, T. A., Adaptive procedure for estimation of parameter for the nonsymmetric Tchebychev iteration, Numer. Math., 28, 187-208 (1978) · Zbl 0413.65032
[124] Mc Cormick (Ed.), S. F., Multigrid Methods (1987), SIAM: SIAM Philadelphia, PA
[125] 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. Comp., 31, 137, 148-162 (1977) · Zbl 0349.65020
[126] Meijerink, J. A.; van der Vorst, H. A., Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems, J. Comput. Phys., 44, 134-155 (1981) · Zbl 0472.65028
[127] Meurant, G., Computer Solution of Large Linear Systems (1999), North-Holland: North-Holland Amsterdam · Zbl 0934.65032
[128] Miellou, J. C., Algorithmes de relaxation chaotiques á retard, RAIRO, R-1, 55-82 (1975) · Zbl 0329.65038
[129] Nachtigal, N. M.; Reddy, S. C.; Trefethen, L. N., How fast are nonsymmetric matrix iterations?, SIAM J. Matrix Anal. Appl., 13, 778-795 (1992) · Zbl 0754.65036
[131] Notay, Y., DRIC: a dynamic version of the RIC method, Numer. Linear Algebra Appl., 1, 511-532 (1994) · Zbl 0839.65030
[132] Oliphant, T. A., An extrapolation process for solving linear systems, Quart. Appl. Math., 20, 257-267 (1962) · Zbl 0109.34601
[133] Oosterlee, C. W.; Washio, T., An evaluation of parallel multigrid as a solver and a preconditioner for singularly perturbed problems, SIAM J. Sci. Statist. Comput., 19, 87-110 (1991) · Zbl 0913.65109
[134] Osterby, O.; Zlatev, Z., Direct Methods for Sparse Matrices (1983), Springer: Springer New York · Zbl 0516.65011
[135] Ostrowski, A. M., Uber die Determinanten mit überwiegender Hauptdiagonale, Comment. Math. Helv., 10, 69-96 (1937) · Zbl 0017.29010
[136] Ostrowski, A. M., On the linear iteration procedures for symmetirc matrices, Rend. Mat. Appl., 14, 140-163 (1954) · Zbl 0057.10401
[137] Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629 (1975) · Zbl 0319.65025
[138] Paige, C. C.; Saunders, M. A., LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8, 43-71 (1982) · Zbl 0478.65016
[139] Parlett, B. N., Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix Anal. Appl., 13, 567-593 (1992) · Zbl 0754.65040
[140] Parlett, B. N.; Taylor, D. R.; Liu, Z. S., A look-ahead Lanczos algorithm for nonsymmetric matrices, Math. Comp., 44, 105-124 (1985) · Zbl 0564.65022
[141] Peaceman, D.; Rachford, H., The numerical solution of elliptic and parabolic differential equations, J. SIAM, 3, 28-41 (1955) · Zbl 0067.35801
[143] Radicati di Brozolo, G.; Robert, Y., Parallel conjugate gradient-like algorithms for solving sparse nonsymmetric systems on a vector multiprocessor, Parallel Comput., 11, 223-239 (1989) · Zbl 0678.65017
[144] Reich, E., On the convergence of the classical iterative method of solving linear simultaneous equations, Ann. Math. Statist., 20, 448-451 (1949) · Zbl 0041.24201
[145] Reid, J. K., On the method of conjugate gradients for the solution of large sparse systems of linear equations, (Reid, J. K., Large Sparse Sets of Linear Equations (1971), Academic Press: Academic Press New York), 231-254
[146] Richardson, L. F., The approximate arithmetical solution by finite differences of physical problems involving differential equations with an application to the stresses to a masonry dam, Philos. Trans. Roy. Soc. London Ser. A, 210, 307-357 (1910) · JFM 42.0873.02
[147] Robert, F., Contraction en norme vectorielle: convergence d’itérations chaotiques, Linear Algebra Appl., 13, 19-35 (1976) · Zbl 0332.65019
[148] Robert, F.; Charnay, M.; Musy, F., Iterations chaotiques série-parallèle pour les équations non linéaires de point fixe, Apl. Math., 20, 1-38 (1975)
[151] Saad, Y., Practical use of polynomial preconditionings for the conjugate gradient method, SIAM J. Sci. Statist. Comput., 6, 865-881 (1985) · Zbl 0601.65019
[152] Saad, Y., Least squares polynomials in the complex plane and their use for solving sparse nonsymmetric linear systems, SIAM J. Numer. Anal., 24, 155-169 (1987) · Zbl 0619.65022
[153] Saad, Y., Preconditioning techniques for indefinite and nonsymmetric linear systems, J. Comput. Appl. Math., 24, 89-105 (1988) · Zbl 0662.65028
[154] Saad, Y., Krylov subspace methods on supercomputers, SIAM J. Sci. Statist. Comput., 10, 1200-1232 (1989) · Zbl 0693.65028
[155] Saad, Y., A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Statist. Comput., 14, 461-469 (1993) · Zbl 0780.65022
[156] Saad, Y., Highly parallel preconditioners for general sparse matrices, (Golub, G.; Luskin, M.; Greenbaum, A., Recent Advances in Iterative Methods, IMA Volumes in Mathematics and Its Applications, Vol. 60 (1994), Springer: Springer New York), 165-199 · Zbl 0803.65059
[157] Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS Publishing: PWS Publishing New York · Zbl 1002.65042
[158] Saad, Y.; Schultz, M. H., GMRES: a generalized minimal residual algorithm for solving a nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7, 856-869 (1986) · Zbl 0599.65018
[159] Saltz, J.; Mirchandaney, R.; Crowley, K., Run-time paralellization and scheduling of loops, IEEE Trans. Comput., 40, 603-612 (1991)
[160] Saylor, P. E.; Smolarski, D. C., Computing the roots of complex orthogonal kernel polynomials, SIAM J. Sci. Statist. Comput., 9, 1-13 (1988) · Zbl 0637.65042
[161] Sheldon, J. W., On the numerical solution of elliptic difference equations, MTAC, 9, 101-112 (1955) · Zbl 0065.35801
[162] Shortley, G. H., Use of Tschebyscheff-polynomial operators in the solution of boundary value problems, J. Appl. Phys., 24, 392-396 (1953) · Zbl 0050.12404
[164] Simon, H. D., Direct sparse matrix methods, (Almond, J. C.; Young, D. M., Modern Numerical Algorithms for Supercomputers, Center for High Performance Computing (1989), The University of Texas: The University of Texas Austin), 325-344
[165] Sleijpen, G. L.G.; Fokkema, D. R., BICGSTAB(ℓ) for linear equations involving unsymmetric matrices with complex spectrum, ETNA, 1, 11-32 (1993) · Zbl 0820.65016
[166] Sonnoveld, P., CGS: a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 10, 36-52 (1989) · Zbl 0666.65029
[167] Southwell, R. V., Stress calculation in frameworks by the method of systematic relaxation of constraints, Proc. Roy. Soc. London Ser. A, 151, 56-95 (1935) · JFM 61.1498.02
[169] Stein, P.; Rosenberg, R. L., On the solution of linear simultaneous equations by iteration, J. London Math. Soc., 23, 111-118 (1948) · Zbl 0036.36501
[170] Stiefel, E. L., Kernel polynomials in linear algebra and their applications, U.S. Nat. Bur. Standards Appl. Math. Ser., 49, 1-24 (1958) · Zbl 0171.35703
[171] Stone, H. L., Iterative solution of implicit approximations of multidimensional partial differential equations, SIAM J. Numer. Anal., 5, 530-558 (1968) · Zbl 0197.13304
[172] Strakoš, Z., On the real convergence rate of the conjugate gradient method, Linear Algebra Appl., 154/156, 535-549 (1991) · Zbl 0732.65021
[174] Tanabe, K., Projection method for solving a singular system of linear equations and its applications, Numer. Math., 17, 203-214 (1971) · Zbl 0228.65032
[175] Tang, W. P., Generalized Schwarz splitting, SIAM J. Sci. Statist. Comput., 13, 573-595 (1992) · Zbl 0745.65027
[178] van der Ploeg, A.; Botta, E. F.F.; Wubs, F. W., Nested grids ILU-decomposition (NGILU), J. Comput. Appl. Math., 66, 515-526 (1996) · Zbl 0858.65028
[179] van der Sluis, A.; van der Vorst, H. A., The rate of convergence of conjugate gradients, Numer. Math., 48, 543-560 (1986) · Zbl 0596.65015
[180] Voevodin, V. V., The problem of a non-selfadjoint generalization of the conjugate gradient method has been closed, USSR Comput. Math. Math. Phys., 23, 143-144 (1983) · Zbl 0547.65032
[181] van der Vorst, H. A., Iterative solution methods for certain sparse linear systems with a non-symmetric matrix arising from PDE-problems, J. Comput. Phys., 44, 1-19 (1981) · Zbl 0472.65027
[182] van der Vorst, H. A., A vectorizable variant of some ICCG methods, SIAM J. Statist. Sci. Comput., 3, 350-356 (1982) · Zbl 0484.65018
[183] van der Vorst, H. A., Large tridiagonal and block tridiagonal linear systems on vector and parallel computers, Parallel Comput., 5, 45-54 (1987) · Zbl 0632.65034
[184] van der Vorst, H. A., High performance preconditioning, SIAM J. Sci. Statist. Comput., 10, 1174-1185 (1989) · Zbl 0693.65027
[186] van der Vorst, H. A., Bi-CDSTAB: a fast and smoothly converging variant of Bi-CG for the solution of non-symmetric linear systems, SIAM J. Sci. Statist. Comput., 13, 631-644 (1992) · Zbl 0761.65023
[187] van der Vorst, H. A.; Vuik, C., GMRESR: a family of nested GMRES methods, Numer. Linear Algebra Appl., 1, 369-386 (1994) · Zbl 0839.65040
[188] Varga, R. S., Matrix Iterative Analysis (1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0133.08602
[189] Varga, R. S., Factorization and normalized iterative methods, (Langer, R. E., Boundary Problems in Differential Equations (1960), University of Wisconsin Press: University of Wisconsin Press Madison), 121-142
[191] Vuik, C.; van der Vorst, H. A., A comparison of some GMRES-like methods, Linear Algebra Appl., 160, 131-162 (1992) · Zbl 0749.65027
[192] Wachspress, E. L., CURE, a generalized two-space-dimension multigroup coding for the IBM-704, Technical Report KAPL-1724, Knolls Atomic Power Laboratory (1957), Schenectady: Schenectady New York
[193] Wachspress, E. L., Iterative Solution of Elliptic Systems and Applications to the Neutron Equations of Reactor Physics (1966), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0161.12203
[194] Washio, T.; Hayami, K., Parallel block preconditioning based on SSOR and MILU, Numer. Linear Algebra Appl., 1, 533-553 (1994) · Zbl 0838.65027
[195] Watts III, 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)
[196] Weiss, R., Error-minimixing Krylov subspace methods, SIAM J. Sci. Comput., 15, 511-527 (1994) · Zbl 0798.65048
[198] Weiss, R., Parameter-Free Iterative Linear Solvers (1996), Akademie: Akademie Berlin · Zbl 0858.65031
[199] Wesseling, P., An Introduction to Multigrid Methods (1992), Wiley: Wiley Chichester · Zbl 0760.65092
[200] Widlund, O., A Lanczos method for a class of nonsymmetric systems of linear equations, SIAM J. Numer. Anal., 15, 801-812 (1978) · Zbl 0398.65030
[201] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Clarendon Press: Clarendon Press Oxford · Zbl 0258.65037
[202] Wilkinson, J. H.; Reinsch, C., Handbook of Automatic Computation, Linear Algebra, Vol. II (1971), Springer: Springer New York
[204] Young, D. M., On Richardson’s method for solving linear systems with positive definite matrices, J. Math. Phys., 32, 243-255 (1954) · Zbl 0055.11202
[205] Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic Press: Academic Press New York · Zbl 0204.48102
[206] Young, D. P.; Melvin, R. G.; Johnson, F. T.; Bussoletti, J. E.; Wigton, L. B.; Samant, S. S., Application of sparse matrix solvers as effective preconditioners, SIAM J. Sci. Statist. Comput., 10, 1186-1199 (1989) · Zbl 0684.65023
[207] Zhang, S.-L., GPBi-CG: generalized product-type methods based on Bi-CG for solving nonsymmetric linear systems, SIAM J. Sci. Comput., 18, 537-551 (1997) · Zbl 0872.65023
[208] 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.