×
Young, David M.

A historical overview of iterative methods. (English) Zbl 0798.65035

Comput. Phys. Commun. 53, No. 1-3, 1-17 (1989).
Summary: The object of this paper is to present a historical overview of the development of iterative methods for the solution of large sparse systems of linear equations. The emphasis is on methods which are applicable to linear systems arising in the numerical solution of partial differential equations. Aspects to be covered include: early work, including the methods of L. F. Richardson and of Liebmann as well as relaxation methods used by Southwell and others; the SOR method and extensions such as block SOR methods, and \(p\)-cyclic matrices; Chebyshev polynomial methods; alternating direction implicit methods; the SSOR method, approximate matrix factorization methods including the strongly implicit method (SIP) and the incomplete Cholesky method (ICC); fast direct methods; conjugate gradient methods; adaptive methods for the automatic determination of iteration parameters; multigrid methods; methods for nonsymmetric systems; and iterative software. Future developments will be discussed with emphasis on the use of vector and parallel processors.

Cited in 11 Documents

MSC:

65F10 Iterative numerical methods for linear systems
65-03 History of numerical analysis
65Y05 Parallel numerical computation
01A60 History of mathematics in the 20th century
15A18 Eigenvalues, singular values, and eigenvectors

Keywords:

bibliography; \(p\)-cyclic matrices; historical overview; iterative methods; large sparse systems; relaxation methods; SOR method; Chebyshev polynomial methods; alternating direction implicit methods; matrix factorization methods; strongly implicit method; incomplete Cholesky method; fast direct methods; conjugate gradient methods; adaptive methods; multigrid methods; iterative software; vector and parallel processors

Software:

ELLPACK
Cite Review PDF
Full Text: DOI

References:

[1] Anderson, R. S.; Golub, G. H., (Report CS-72-304 (1972), Computer Science Dept., Stanford University: Computer Science Dept., Stanford University Stanford, California)
[2] Arms, R. J.; Gates, L. D.; Zondek, B., J. Soc. Ind. Appl. Math., 4, 220 (1956)
[3] Axelsson, O., BIT, 13, 443 (1972)
[4] Axelsson, O., (CERN 74-10, European Organization for Nuclear Research (CERN) (1974), Data Handling Division: Data Handling Division Geneva)
[5] Axelsson, O., Lin. Alg. Appl., 29, 1 (1980) · Zbl 0439.65020
[6] Axelsson, O.; Barker, V. A., Finite Element Solution of Boundary Value Problems, (Theory and Computation (1984), Academic Press: Academic Press New York) · Zbl 0981.65130
[7] Benokraitis, V. J., (Doctoral thesis (1974), Univ. of Texas: Univ. of Texas Austin, Texas)
[8] Birkhoff, G., The Numerical Solution of Elliptic Equations, (CBMS-NSF Regional Conf. Series in Applied Mathematics, vol. 1 (1971), SIAM: SIAM Philadelphia, Pennsylvania) · Zbl 0208.19202
[9] Birkhoff, G., A History of Computing in the Twentieth Century (1980), Academic Press: Academic Press New York · Zbl 0456.68001
[10] Birkhoff, G.; Lynch, R. E., SIAM Studies in Applied Mathematics (1984), SIAM: SIAM Philadelphia, Pennsylvania · Zbl 0556.65078
[11] Birkhoff, G.; Varga, R. S., Trans. Am. Math. Soc., 92, 13 (1959) · Zbl 0093.31201
[12] Birkhoff, G.; Varga, R. S.; Young, D., Advan. Comput., 3, 189 (1962) · Zbl 0111.31402
[13] Blair, A.; Metropolis, N.; von Neumann, J.; Taub, A. H.; Tsingori, M., Math. Tables Aids Comput., 13, 145 (1959) · Zbl 0102.33603
[14] Brandt, A., Math. Comput., 31, 333 (1977) · Zbl 0373.65054
[15] Briggs, W. L., A Multigrid Tutorial (1987), SIAM: SIAM Philadelphia, Pennsylvania · Zbl 0659.65095
[16] Broyden, C. G., Num. Math., 6, 269 (1964) · Zbl 0244.65021
[17] Broyden, C. G., Num. Math., 12, 47 (1968) · Zbl 0181.17204
[18] Buneman, O., (Report 294 (1969), Stanford University Institute for Plasma Research: Stanford University Institute for Plasma Research Stanford, California)
[19] Buzbee, B. L.; Golub, G. H.; Nielson, C. W., SIAM J. Num. Anal., 7, 617 (1970)
[20] Concus, P.; Golub, G. H.; O’Leary, D. P., (Bunch, J. R.; Rose, D. J., Sparse Matrix Computation (1976), Academic Press: Academic Press New York), 309
[21] Concus, P.; Golub, G. H., Computing Methods in Applied Sciences and Engineering, (Glowinski, R.; Lions, J. L., Lecture Notes in Economics and Mathematical Systems, vol. 134 (1976), Springer-Verlag: Springer-Verlag Berlin), 56 · Zbl 0332.00006
[22] Cuthill, E. H.; Varga, R. S., J. Assoc. Comput. Mach., 6, 236 (1959) · Zbl 0088.09403
[23] Daniel, J. W., (Ph.D. Thesis (1965), Stanford University: Stanford University Palo Alto, California)
[24] Daniel, J. W., SIAM J. Num. Anal., 4, 10 (1967)
[25] Dongarra, J. J.; Leaf, G. K.; Minkoff, M., (Report ANL-81-71 (1981), Argonne Nat. Lab: Argonne Nat. Lab Argonne, Illinois)
[26] Douglas, J., J. Soc. Ind. Appl. Math., 3, 42 (1955) · Zbl 0067.35802
[27] Douglas, J.; Rachford, H., Trans. Am. Math. Soc., 82, 421 (1956) · Zbl 0070.35401
[28] Dupont, T.; Kendall, R.; Rachford, H. H., SIAM J. Num. Anal., 5, 559 (1968) · Zbl 0174.47603
[29] Ehrlich, L. W., (Doctoral thesis (1963), The University of Texas: The University of Texas Austin, Texas)
[30] Ehrlich, L. W., J. Soc. Ind. Appl. Math., 12, 807 (1964) · Zbl 0133.38004
[31] Ehrlich, L. W., J. Comput. Phys., 43, 31 (1981)
[32] Eisenstat, S. C.; Elman, H. C.; Schultz, M. H., SIAM J. Num. Anal., 20, 345 (1983) · Zbl 0524.65019
[33] Eisenstat, S. C.; Elman, H. C.; Schultz, M. H.; Sherman, A. A., (Birkhoff, G.; Schoenstadt, A., Elliptic Problem Solvers, II (1984), Academic Press: Academic Press New York)
[34] Elman, H. C., (Ph.D. Dissertation, (1982), Dept. of Comput. Sci., Yale University: Dept. of Comput. Sci., Yale University New Haven, Connecticut), also Research Rep. 229
[35] Evans, D. J., J. Inst. Math. Appl., 4, 295 (1967)
[36] Evans, D. J.; Forrington, C. V.D., Comput. J., 6, 271 (1963) · Zbl 0127.08202
[37] Flanders, D.; Shortley, G., J. Appl. Phys., 21, 1326 (1950) · Zbl 0039.34101
[38] Fletcher, R., (Lecture Notes in Mathematics, 506 (1976), Springer-Verlag: Springer-Verlag Berlin and New York)
[39] Forsythe, G. E., Bull. Am. Math. Soc., 59, 299 (1953) · Zbl 0050.34603
[40] Forsythe, G. E.; Wasow, W. R., Finite Difference Methods for Partial Differential Equations (1960), John Wiley: John Wiley New York · Zbl 0099.11103
[41] Frankel, S. P., Math. Tables Aids Comput, 4, 65 (1950)
[42] Math. Tables Aids Comput., 5, 255 (1954), translated by G.E. Forsythe under the title Gauss to Gerling on Relaxation
[43] Geiringer, H., Reissner Anniversary Volume, (Contributions to Applied Mechanics (1949), Edwards: Edwards Ann Arbor, Michigan), 365
[44] Golub, G. H., (Doctoral Thesis (1959), University of Illinois: University of Illinois Urbana, Illinois)
[45] Golub, G. H.; Varga, R. S., Num. Math. (parts I and II), 3, 147 (1961)
[46] Gustafsson, I. A., BIT, 18, 142 (1978) · Zbl 0386.65006
[47] Habetler, G. J.; Wachspress, E. L., Math. Comput., 15, 356 (1961) · Zbl 0102.11403
[48] Hageman, L. A.; Young, D. M., Applied Iterative Methods (1981), Academic Press: Academic Press New York · Zbl 0459.65014
[49] Hayes, L. J.; Young, D. M., (Report CNA-123 (1977), Center for Numerical Analysis, The University of Texas: Center for Numerical Analysis, The University of Texas Austin, Texas)
[50] Hestenes, M. R., (Curtiss, J., Numerical Analysis, vol. VI (1956), McGraw-Hill: McGraw-Hill New York)
[51] Hestenes, M. R.; Stiefel, E., J. Res. Nat. Bur. Stand., 49, 498 (1952)
[52] Hockney, R. W., (UCID-16558 (1965), Lawrence Livermore Laboratory: Lawrence Livermore Laboratory Livermore, California)
[53] Huang, R., (Report CNA-187 (1983), Center for Numerical Analysis, The University of Texas: Center for Numerical Analysis, The University of Texas Austin, Texas)
[54] Jacobi, C. G.J., Astr. Nachr., 22, 297 (1845)
[55] Jea, K. C., (Report CNA-176 (1982), Center for Numerical Analysis, The University of Texas: Center for Numerical Analysis, The University of Texas Austin, Texas)
[56] Jea, K. C.; Young, D. M., Lin. Alg. Appl., 52, 399 (1983)
[57] Kahan, W., (Doctoral Thesis (1958), University of Toronto: University of Toronto Toronto, Canada)
[58] Kincaid, D. R.; Young, D. M., (Report CNA-217 (1988), Center for Numerical Analysis, The University of Texas: Center for Numerical Analysis, The University of Texas Austin, Texas)
[59] Kincaid, D. R.; Respess, J.; Young, D. M.; Grimes, R., ACM Trans. Math. Software, 8, 302 (1982) · Zbl 0485.65025
[60] Lanczos, C., J. Res. Nat. Bur. Stand., 49, 33 (1952)
[61] Liebmann, H., Sitzungsberichte der Bayer. Akad. Wiss. Math.-Phys. K1., 47, 385 (1918)
[62] Manteuffel, T. A., Num. Math., 28, 307 (1977) · Zbl 0361.65024
[63] Manteuffel, T. A., Num. Math., 31, 183 (1978) · Zbl 0413.65032
[64] Manteuffel, T. A., Math. Comput., 34, 473 (1980) · Zbl 0422.65018
[65] Markoff, W., Math. Ann., 77, 218 (1916), (translation and condensation by J. Grossman of Russian article published in 1892)
[66] (McCormick, S. F., Multigrid Methods (1987), Soc. for Industrial and Applied Mathematics: Soc. for Industrial and Applied Mathematics Philadelphia, Pennsylvania) · Zbl 0659.65094
[67] Meijerink, J. A.; van der Vorst, H. A., Math. Comput., 31, 148 (1977) · Zbl 0349.65020
[68] D.O’Leary and G.H. Golub, SIAM Rev. (in press).; D.O’Leary and G.H. Golub, SIAM Rev. (in press).
[69] Ortega, J. M., Introduction to Parallel and Vector Solution of Linear Systems (1988), Plenum Press: Plenum Press New York · Zbl 0669.65017
[70] Ortega, J. M.; Voigt, R. G., SIAM Rev., 27, 149 (1985) · Zbl 0644.65075
[71] Peaceman, D. W.; Rachford, H. H., J. Soc. Ind. Appl. Math., 3, 28 (1955) · Zbl 0067.35801
[72] Price, H.; Varga, R. S., (Report No. 91 (1962), Gulf Research and Development Co: Gulf Research and Development Co Pittsburgh, Pennsylvania)
[73] Proskurowski, W.; Widlund, O., Math. Comput., 30, 433 (1976) · Zbl 0332.65057
[74] Reid, J. K., (Proc. Conf. Large Sparse Sets of Linear Equations (1971), Academic Press: Academic Press New York), 231
[75] Reid, J. K., SIAM J. Num. Anal., 9, 325 (1972) · Zbl 0259.65037
[76] (Rose, D. J.; Willoughby, R. A., Sparse Matrices and Their Applications (1972), Plenum Press: Plenum Press New York)
[77] (Rice, J. R.; Boisvert, R. F., Solving Elliptic Problems Using ELLPACK (1985), Springer-Verlag: Springer-Verlag New York) · Zbl 0562.65064
[78] Richardson, L. F., Phil. Trans. Roy. Soc. London Ser., A210, 307 (1910)
[79] Saad, Y.; Schultz, M. H., (Report RR-254 (1983), Dept. of Comp. Sci., Yale University: Dept. of Comp. Sci., Yale University New Haven, Connecticut)
[80] Seidel, L., Abh. Math.-Phys. K1. Bayerische Akad. Wiss. München, 11, III, 81 (1874)
[81] Sheldon, J., Math. Tables Aids Comput., 9, 101 (1955) · Zbl 0065.35801
[82] Shortley, G. H., J. Appl. Phys., 24, 392 (1953) · Zbl 0050.12404
[83] Shortley, G. H.; Weller, R., J. Appl. Phys., 9, 334 (1938) · Zbl 0019.03801
[84] Shortley, G. H.; Weller, R.; Fried, B., (Bull. No. 107 (1940), Ohio State University, Engineering Experiment Station), 55, (revised ed., January 1942) · Zbl 0063.06974
[85] Stone, H. L., SIAM J. Num. Anal., 5, 530 (1968) · Zbl 0197.13304
[86] Southwell, R. V., Relaxation Methods in Theoretical Physics (1946), Oxford Univ. Press: Oxford Univ. Press New York · Zbl 0061.27706
[87] Swartztrauber, P. M., SIAM J. Num. Anal., 11, 1136 (1974) · Zbl 0292.65054
[88] Sweet, R. A., SIAM J. Num. Anal., 11, 506 (1974) · Zbl 0253.65061
[89] Temple, G., Proc. Roy. Soc., A169, 476 (1938)
[90] Varga, R. S., J. SIAM, 5, 39 (1957) · Zbl 0080.10701
[91] Varga, R. S., Pacific. J. Math., 9, 617 (1957)
[92] Varga, R. S., Pacific J. Math., 9, 925 (1959)
[93] Varga, R. S., Matrix Iterative Analysis (1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, New Jersey · Zbl 0133.08602
[94] Verner, J. H.; Bernal, M. J.M., Num. Math., 12, 215 (1968) · Zbl 0172.18802
[95] Vinsome, P. K.W., (Paper SPE 5739, Symp. Num. Simulation of Reservoir Performance of SPE of AIME. Paper SPE 5739, Symp. Num. Simulation of Reservoir Performance of SPE of AIME, 4th Los Angeles, California (19-20 February 1976))
[96] Wachspress, E. L., Iterative Solution of Elliptic Systems and Applications to the Neutron Diffusion Equations of Reactor Physics (1966), Prentice-Hall: Prentice-Hall Englewood Cliffs, New Jersey · Zbl 0161.12203
[97] Wachspress, E. L.; Habetler, G. J., J. Soc. Ind. Appl. Math., 8, 403 (1960) · Zbl 0158.33901
[98] Widlund, O., Math. Comput., 20, 500 (1966) · Zbl 0173.44503
[99] Widlund, O., SIAM J. Num. Anal., 15, 801 (1978) · Zbl 0398.65030
[100] Wrigley, E. E., Comput. J., 6, 169 (1963) · Zbl 0131.14201
[101] Young, D. M., (Doctoral Thesis (1950), Harvard University: Harvard University Cambridge, Massachusetts)
[102] Young, D. M., Trans. Am. Math. Soc., 76, 92 (1954) · Zbl 0055.35704
[103] Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic Press: Academic Press New York · Zbl 0204.48102
[104] Young, D. M., J. Approx. Theory, 5, 137 (1972) · Zbl 0236.65027
[105] Young, D. M., Adv. Math., 23, 215 (1977) · Zbl 0356.65027
[106] Young, D. M., A History of Scientific Computation, (Nash, Stephen G., Report CNA-206 (1989), Center for Numerical Analysis, The University of Texas: Center for Numerical Analysis, The University of Texas Austin, Texas), to appear in:
[107] Young, D. M.; Eidson, H. E., (Report CNA-1 (1970), Center for Numerical Analysis, The University of Texas: Center for Numerical Analysis, The University of Texas Austin, Texas)
[108] Young, D. M.; Huang, R., (Report CNA-185 (1983), Center for Numerical Analysis, The University of Texas: Center for Numerical Analysis, The University of Texas Austin, Texas)
[109] Young, D. M.; Jea, K. C., J. Linear Algebra and Its Appl., 34, 159 (1980) · Zbl 0463.65025
[110] Young, D. M.; Mai, T. Z., (Report CNA-197 (1984), Center for Numerical Analysis, The University of Texas: Center for Numerical Analysis, The University of Texas Austin, Texas)
[111] Young, D. M.; Mai, T., (Proc. Conf. on Iterative Methods for Large Linear Systems which was held at The University of Texas. Proc. Conf. on Iterative Methods for Large Linear Systems which was held at The University of Texas, Austin, Texas (October 1988)), to appear in:
[112] Axelsson, O., Iterative Methods in Sparse Matrix Techniques, (Barker, V. A., LNH #572 (1976), Springer Verlag: Springer Verlag Berlin), 1
[113] (Verwer, J. G., Colloquium Topics in Applied Numerical Analysis, vol. 1 (1984)), 21, Amsterdam 1983/1984
[114] Bakhvalov, N. S., USSR Comput. Math. Math. Phys., 6, 101 (1966), Amsterdam
[115] Birkhoff, G., (Nash, S. G., A History of Scientific Computation (1989), Addison Wesley: Addison Wesley Mass)
[116] Concus, P.; Golub, G. H., SIAM J. Num. Anal., 10, 1103 (1973) · Zbl 0245.65043
[117] Fedorenko, R. P., USSR Comput. Math. Math. Phys., 1, 1092 (1962)
[118] (Glowinski, R.; Golub, G. H.; Meurant, G. A.; Periaux, J., Proc. First Intern. Symp. on Domain Decomposition Methods for Partial Differential Equations (1988), SIAM: SIAM Philadelphia)
[119] Lanczos, C., Nat. Bur. Stand. J. Res., 45, 255 (1950)
[120] Lebedev, V. I.; Finogenov, Zh. Vychislit. Mat. i Mat Fiz., 13, 18 (1973) · Zbl 0271.65026
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.