×

zbMATH — the first resource for mathematics

Iterative methods for linear systems of equations: a brief historical journey. (English) Zbl 07370296
Brenner, Susanne C. (ed.) et al., 75 years of mathematics of computation. Symposium celebrating 75 years of mathematics of computation, Institute for Computational and Experimental Research in Mathematics, ICERM, Providence, RI, USA, November 1–3, 2018. Providence, RI: American Mathematical Society (AMS). Contemp. Math. 754, 197-215 (2020).
Summary: This paper presents a brief historical survey of iterative methods for solving linear systems of equations. The journey begins with Gauss who developed the first known method that can be termed iterative. The early 20th century saw good progress of these methods which were initially used to solve least-squares systems, and then linear systems arising from the discretization of partial differential equations. Then iterative methods received a big impetus in the 1950s – partly because of the development of computers. The survey does not attempt to be exhaustive. Rather, the aim is to bring out the way of thinking at specific periods of time and to highlight the major ideas that steered the field.
For the entire collection see [Zbl 1461.11002].

MSC:
65F10 Iterative numerical methods for linear systems
65-03 History of numerical analysis
01A55 History of mathematics in the 19th century
Software:
SPARSPAK; CGS; symrcm
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, D. N. de G.; Southwell, Richard, Relaxation methods applied to engineering problems. XIV. Plastic straining in two-dimensional stress-systems, Philos. Trans. Roy. Soc. London. Ser. A., 242, 379-414 (1950) · Zbl 0039.20603
[2] Hartwig Anzt, Stanimire Tomov, Jack Dongarra, and Vincent Heuveline, A block-asynchronous relaxation method for graphics processing units, Journal of Parallel and Distributed Computing 73 (2013), no. 12, 1613 - 1626, Heterogeneity in Parallel and Distributed Computing.
[3] Axelsson, O., A survey of preconditioned iterative methods for linear systems of algebraic equations, BIT, 25, 1, 166-187 (1985) · Zbl 0566.65017
[4] Axelsson, O., A generalized conjugate gradient, least square method, Numer. Math., 51, 2, 209-227 (1987) · Zbl 0596.65014
[5] Axelsson, Owe, Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations, Linear Algebra Appl., 29, 1-16 (1980) · Zbl 0439.65020
[6] Bahi, M.; Miellou, J.-C., Contractive mappings with maximum norms: comparison of constants of contraction and application to asynchronous iterations, Parallel Comput., 19, 5, 511-523 (1993) · Zbl 0776.65040
[7] Baudet, G\'{e}rard M., Asynchronous iterative methods for multiprocessors, J. Assoc. Comput. Mach., 25, 2, 226-244 (1978) · Zbl 0372.68015
[8] M. Benzi, Gianfranco Cimmino”s contributions to numerical mathematics, Atti del Seminario di Analisi Matematica, Dipartimento di Matematica dell’Universita‘ di Bologna, pages 87-109, Tecnoprint, Bologna, 2005.
[9] Bertsekas, Dimitri P.; El Baz, Didier, Distributed asynchronous relaxation methods for convex network flow problems, SIAM J. Control Optim., 25, 1, 74-85 (1987) · Zbl 0624.90028
[10] Blair, A.; Metropolis, N.; von Neumann, J.; Taub, A. H.; Tsingou, M., A study of a numerical solution to a two-dimensional hydrodynamical problem, Math. Tables Aids Comput., 13, 145-184 (1959) · Zbl 0102.33603
[11] Bodewig, E., Matrix calculus, 2nd revised and enlarged edition, xi+452 pp. (1959), North-Holland Publishing Co., Amsterdam; Interscience Publishers, Inc., New York · Zbl 0086.32501
[12] 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, 2, 338-347 (1994) · Zbl 0803.65038
[13] Chazan, D.; Miranker, W., Chaotic relaxation, Linear Algebra and Appl., 2, 199-222 (1969) · Zbl 0225.65043
[14] E. Chow, H. Anzt, and J. Dongarra, Asynchronous iterative algorithm for computing incomplete factorizations on GPUs, High Performance Computing. ISC High Performance (Ludwig T. Kunkel J., ed.), Lecture Notes in Computer Science, vol 9137, Springer, 2015.
[15] E. Chu, A. George, J. W.-H. Liu, and E. G.-Y. Ng, Users guide for SPARSPAK-A: Waterloo sparse linear equations package, Tech. Report CS-84-36, University of Waterloo, Waterloo, Ontario, Canada, 1984.
[16] G. Cimmino, Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, Ricerca Scientifica, II 9 (1938), 326-333. · Zbl 0018.41802
[17] Allen, D. N. de G.; Southwell, R. V., Relaxation methods applied to determine the motion, in two dimensions, of a viscous fluid past a fixed cylinder, Quart. J. Mech. Appl. Math., 8, 129-145 (1955) · Zbl 0064.19802
[18] I. S. Duff, A survey of sparse matrix research, Proceedings of the IEEE, 65 (New York), Prentice Hall, 1977, pp. 500-535.
[19] Eisenstat, Stanley C.; Elman, Howard C.; Schultz, Martin H., Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal., 20, 2, 345-357 (1983) · Zbl 0524.65019
[20] El Baz, Didier, \(M\)-functions and parallel asynchronous algorithms, SIAM J. Numer. Anal., 27, 1, 136-140 (1990) · Zbl 0701.65040
[21] El Tarazi, Mouhamed Nabih, Some convergence results for asynchronous algorithms, Numer. Math., 39, 3, 325-340 (1982) · Zbl 0479.65030
[22] Nahid Emad, S.-A. Shahzadeh-Fazeli, and Jack Dongarra, An asynchronous algorithm on the netsolve global computing system, Future Generation Computer Systems 22 (2006), no. 3, 279 - 290. · Zbl 1142.65332
[23] 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, Mitt. Inst. Angew. Math. Z\"{u}rich. No., 8, 107 pp. (1959) · Zbl 0089.12103
[24] Fletcher, R., Conjugate gradient methods for indefinite systems. Numerical analysis, Proc 6th Biennial Dundee Conf., Univ. Dundee, Dundee, 1975, 73-89. Lecture Notes in Math., Vol. 506 (1976), Springer, Berlin
[25] G. E. Forsythe, Gauss to Gerling on relaxation, Mathematical Tables and Other Aids to Computation 5 (1951), 255-258.
[26] Forsythe, George E., Solving linear algebraic equations can be interesting, Bull. Amer. Math. Soc., 59, 299-329 (1953) · Zbl 0050.34603
[27] Fox, L., A short account of relaxation methods, Quart. J. Mech. Appl. Math., 1, 253-280 (1948) · Zbl 0033.37901
[28] Fox, L.; Southwell, R. V., Relaxation methods applied to engineering problems. VII A. Biharmonic analysis as applied to the flexure and extension of flat elastic plates, Philos. Trans. Roy. Soc. London. Ser. A., 239, 419-460 (1945) · Zbl 0063.01421
[29] Frankel, Stanley P., Convergence rates of iterative treatments of partial differential equations, Math. Tables Aids Comput., 4, 65-75 (1950)
[30] Freund, Roland 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
[31] Freund, Roland W.; Nachtigal, No\"{e}l M., QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60, 3, 315-339 (1991) · Zbl 0754.65034
[32] Frommer, Andreas; Szyld, Daniel B., On asynchronous iterations, J. Comput. Appl. Math., 123, 1-2, 201-216 (2000) · Zbl 0967.65066
[33] George, Alan; Liu, Joseph W. H., The evolution of the minimum degree ordering algorithm, SIAM Rev., 31, 1, 1-19 (1989) · Zbl 0671.65024
[34] George, Alan; Liu, Joseph W. H., Computer solution of large sparse positive definite systems, xii+324 pp. (1981), Prentice-Hall, Inc., Englewood Cliffs, N.J. · Zbl 0516.65010
[35] Giraud, L.; Spiteri, P., R\'{e}solution parall\`ele de probl\`emes aux limites non lin\'{e}aires, RAIRO Mod\'{e}l. Math. Anal. Num\'{e}r., 25, 5, 579-606 (1991) · Zbl 0733.65060
[36] Golub, Gene H.; O’Leary, Dianne P., Some history of the conjugate gradient and Lanczos algorithms: 1948-1976, SIAM Rev., 31, 1, 50-102 (1989) · Zbl 0673.65017
[37] Golub, Gene H.; Varga, Richard S., Chebyshev semi-iterative methods, successive over-relaxation iterative methods, and second order Richardson iterative methods. II, Numer. Math., 3, 157-168 (1961) · Zbl 0099.10903
[38] Green, J. R.; Southwell, R. V., Relaxation methods applied to engineering problems. IX. High-speed flow of compressible fluid through a two-dimensional nozzle, Philos. Trans. Roy. Soc. London. Ser. A., 239, 367-386 (1944) · Zbl 0063.01734
[39] Householder, Alston S., The theory of matrices in numerical analysis, xi+257 pp. (1964), Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London
[40] C. G. J. Jacobi, Ueber eine neue Auflosungsart der bei der Methode der kleinsten Quadrate vorkommende linearen Gleichungen, Astronomische Nachrichten (1845), 297-306.
[41] Jacobi, C. G. J., \"{U}ber ein leichtes Verfahren die in der Theorie der S\"{a}cularst\"{o}rungen vorkommenden Gleichungen numerisch aufzul\"{o}sen, J. Reine Angew. Math., 30, 51-94 (1846) · ERAM 030.0852cj
[42] Kaczmarz, S., Approximate solution of systems of linear equations, Internat. J. Control, 57, 6, 1269-1271 (1993) · Zbl 0817.65025
[43] Knuth, Donald E., George Forsythe and the development of computer science, Comm. ACM, 15, 8, 721-726 (1972)
[44] Lanczos, Cornelius, Solution of systems of linear equations by minimized-iterations, J. Research Nat. Bur. Standards, 49, 33-53 (1952)
[45] H. Liebmann, Die angenaherte harmonischer Funktionen und konformer Abbildungen (nach Ideen von Boltzmann und Jacobi), S. B. Math. Nat. Kl. Bayerischen Akad. Wiss. Munchen (1918), 385-416. · JFM 46.0559.01
[46] Magoul\`es, Fr\'{e}d\'{e}ric; Szyld, Daniel B.; Venet, C\'{e}dric, Asynchronous optimized Schwarz methods with and without overlap, Numer. Math., 137, 1, 199-227 (2017) · Zbl 1382.65449
[47] R. Mehmke and P.A. Nekrasov, Solutions of linear systems of equations by means of successive approximations, Matematicheskii Sbornik 16 (1892), 437-459, German translation available in Math-Net.Ru.
[48] 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
[49] Miellou, J. C., Algorithmes de r\'{e}laxation chaotique \`a retards, Rev. Fran\c{c}aise Automat. Informat. Recherche Operationnelle S\'{e}r., 9, R-1, 55-82 (1975) · Zbl 0329.65038
[50] Miellou, J. C.; El Baz, D.; Spiteri, P., A new class of asynchronous iterative algorithms with order intervals, Math. Comp., 67, 221, 237-255 (1998) · Zbl 0899.65031
[51] Miellou, Jean-Claude, It\'{e}rations chaotiques \`a retards, C. R. Acad. Sci. Paris S\'{e}r. A, 278, 957-960 (1974) · Zbl 0314.65028
[52] Comte, Pierre, It\'{e}rations chaotiques \`a retards, \'{e}tude de la convergence dans le cas d’un espace produit d’espaces vectoriellement norm\'{e}s, C. R. Acad. Sci. Paris S\'{e}r. A-B, 281, 20, Aii, A863-A866 (1975) · Zbl 0316.65007
[53] P. Nekrassov, Determination des inconnues par la methode de moindres carres dans le cas ou le nombre d’inconnues est considerable, Mat. Sb. 12 (1885), 189-204, In Russian. Available along a French version from http://mi.mathnet.ru/msb7148.
[54] Ostrowski, Alexander, Determinanten mit \"{u}berwiegender Hauptdiagonale und die absolute Konvergenz von linearen Iterationsprozessen, Comment. Math. Helv., 30, 175-210 (1956) · Zbl 0072.13803
[55] Parter, S., The use of linear graphs in Gauss elimination, SIAM Rev., 3, 119-130 (1961) · Zbl 0102.11302
[56] Petrova, Svetlana S.; Solov\cprime ev, Alexander D., The origin of the method of steepest descent, Historia Math., 24, 4, 361-375 (1997) · Zbl 0894.01006
[57] Reid, J. K., On the method of conjugate gradients for the solution of large sparse systems of linear equations. Large sparse sets of linear equations, Proc. Conf., St. Catherine’s Coll., Oxford, 1970, 231-254 (1971), Academic Press, London
[58] L. F. Richardson, The approximate arithmetical solution by finite differences of physical problems involving differential equations with an application to the stresses to a masonry dam, Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences 210 (1910), 307-357. · JFM 42.0873.02
[59] Robert, F.; Charnay, M.; Musy, F., It\'{e}rations chaotiques s\'{e}rie-parall\`ele pour des \'{e}quations non-lin\'{e}aires de point fixe, Apl. Mat., 20, 1-38 (1975)
[60] Rose, Donald J.; Tarjan, R. Endre; Lueker, George S., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 2, 266-283 (1976) · Zbl 0353.65019
[61] Rose, Donald J.; Tarjan, Robert Endre, Algorithmic aspects of vertex elimination on directed graphs, SIAM J. Appl. Math., 34, 1, 176-197 (1978) · Zbl 0377.65013
[62] J. Rosenfeld, A case study on programming for parallel processors, Research Report RC 64, IBM, Watson Research Center, Yorktown Heights, New-York, 1967.
[63] Saad, Y., Krylov subspace methods for solving large unsymmetric linear systems, Math. Comp., 37, 155, 105-126 (1981) · Zbl 0474.65019
[64] Saad, Yousef, Iterative methods for sparse linear systems, xviii+528 pp. (2003), Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 1031.65046
[65] Saad, Youcef; Schultz, Martin H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7, 3, 856-869 (1986) · Zbl 0599.65018
[66] Saad, Yousef; van der Vorst, Henk A., Iterative solution of linear systems in the 20th century, J. Comput. Appl. Math., 123, 1-2, 1-33 (2000) · Zbl 0965.65051
[67] Smith, David Eugene, Book Review: Briefwechsel zwischen Carl Friedrich Gauss und Christian Ludwig Gerling, Bull. Amer. Math. Soc., 34, 5, 665-666 (1928)
[68] Schechter, Samuel, Relaxation methods for linear equations, Comm. Pure Appl. Math., 12, 313-335 (1959) · Zbl 0096.09801
[69] Ludwig Seidel, uber ein Verfahren, die Gleichungen, auf welche die Methode der kleinsten Quadrate fuhrt, sowie lineare Gleichungen uiberhaupt, durch successive Annaherung aufzulosen, Akad. Wiss., Munich, mat.-nat. Abt. Abhandlungen 11 (1874), 81-108.
[70] Sheldon, John W., On the numerical solution of elliptic difference equations, Math. Tables Aids Comput., 9, 101-112 (1955) · Zbl 0065.35801
[71] Shortley, George, Use of Tschebyscheff-polynomial operators in the numerical solution of boundary-value problems, J. Appl. Phys., 24, 392-396 (1953) · Zbl 0050.12404
[72] Sleijpen, G\`erard L. G.; Fokkema, Diederik R., BiCGstab \((l)\) for linear equations involving unsymmetric matrices with complex spectrum, Electron. Trans. Numer. Anal., 1, Sept., 11-32 (electronic only) (1993) · Zbl 0820.65016
[73] Smith, David Eugene, Book Review: Briefwechsel zwischen Carl Friedrich Gauss und Christian Ludwig Gerling, Bull. Amer. Math. Soc., 34, 5, 665-666 (1928)
[74] Sonneveld, Peter, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 10, 1, 36-52 (1989) · Zbl 0666.65029
[75] R. V. Southwell, Stress calculation in frameworks by the method of systematic relaxation of constraints, Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences 151 (1935), 56-95. · JFM 61.1498.02
[76] R. V. Southwell, Relaxation methods in engineering science, a treatise on approximate computation, Oxford University Press, 1940, 1943. · JFM 66.1295.01
[77] R. V. Southwell, Relaxation methods in theoretical physics, vol. 2, Oxford Univ. Press, Oxford, 1946. · Zbl 0061.27706
[78] P. L. Tchebycheff, Theorie des mecanismes connus sous le nom de parallelogrammes (memoires presentes a l’academie imperiale des sciences de St-Petersbourg par divers savants vii, 1854, pp. 539-568), Oeuvres de P. L. Tchebycheff (A. Markoff and N. Sonin, eds.), Academie imperiale des sciences, St-Petersbourg, 1899, pp. 125-143.
[79] van der Vorst, H. A., Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 13, 2, 631-644 (1992) · Zbl 0761.65023
[80] Varga, Richard S., A comparison of the successive overrelaxation method and semi-iterative methods using Chebyshev polynomials, J. Soc. Indust. Appl. Math., 5, 39-46 (1957) · Zbl 0080.10701
[81] Varga, Richard S., Matrix iterative analysis, xiii+322 pp. (1962), Prentice-Hall, Inc., Englewood Cliffs, N.J.
[82] P. K. W. Vinsome, ORTHOMIN: an iterative method for solving sparse sets of simultaneous linear equations, Proceedings of the Fourth Symposium on Resevoir Simulation, Society of Petroleum Engineers of AIME, 1976, pp. 149-159.
[83] R. von Mises and H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflosung, Zeitschrift fur Angewandte Mathematik und Mechanik 9 (1929), 58-77. · JFM 55.0305.01
[84] Young, David M., ITERATIVE METHODS FOR SOLVING PARTIAL DIFFERENCE EQUATION OF ELLIPTIC TYPE, (no paging) pp. (1950), ProQuest LLC, Ann Arbor, MI
[85] Young, David M., Iterative solution of large linear systems, xxiv+570 pp. (1971), Academic Press, New York-London · Zbl 1049.65022
[86] Young, David M., A historical overview of iterative methods, Comput. Phys. Comm., 53, 1-3, 1-17 (1989) · Zbl 0798.65035
[87] Young, David M.; Jea, Kang C., Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods, Linear Algebra Appl., 34, 159-194 (1980) · Zbl 0463.65025
[88] R. Zurmuhl, Matrizen, Springer, Berlin, 1950.
[89] R. Zurmuhl, Matrizen, Springer, Berlin, 1950.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.