Alan Turing and the origins of modern Gaussian elimination
DOI:
https://doi.org/10.3989/arbor.2013.764n6007Keywords:
backward errors, condition number of a matrix, Gaussian elimination, Goldstine, LU factorization of matrices, numerical analysis, numerical linear algebra, rounding error analysis, Turing, von Neumann, WilkinsonAbstract
The solution of a system of linear equations is by far the most important problem in Applied Mathematics. It is important both in itself and because it is an intermediate step in many other important problems. Gaussian elimination is nowadays the standard method for solving this problem numerically on a computer and it was the first numerical algorithm to be subjected to rounding error analysis. In 1948, Alan Turing published a remarkable paper on this topic: “Rounding-off errors in matrix processes” (Quart. J. Mech. Appl. Math. 1, pp. 287-308). In this paper, Turing formulated Gaussian elimination as the matrix LU factorization and introduced the “condition number of a matrix”, both of them fundamental notions of modern Numerical Analysis. In addition, Turing presented an error analysis of Gaussian elimination for general matrices that deeply influenced the spirit of the definitive analysis developed by James Wilkinson in 1961. Alan Turing’s work on Gaussian elimination appears in a fascinating period for modern Numerical Analysis. Other giants of Mathematics, as John von Neumann, Herman Goldstine, and Harold Hotelling were also working in the mid-1940s on Gaussian elimination. The goal of these researchers was to find an efficient and reliable method for solving systems of linear equations in modern “automatic computers”. At that time, it was not clear at all whether Gaussian elimination was a right choice or not. The purpose of this paper is to revise, at an introductory level, the contributions of Alan Turing and other authors to the error analysis of Gaussian elimination, the historical context of these contributions, and their influence on modern Numerical Analysis.
Downloads
References
Aspray, W. and Burks, A. (eds.) (1987). Papers of John von Neumann on Computing and Computer Theory. Cambridge, MA: MIT Press.
Carpenter, B. E. and Doran, R. W. (eds.) (1986). A. M. Turing's ACE report of 1946 and other papers. Cambridge, MA: MIT Press.
Demmel, J. W. (1997). Applied Numerical Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). http://dx.doi.org/10.1137/1.9781611971446
Dieudonné, J. (1981). "Von Neumann, Johan (or John)". In: Dictionary of Scientific Biographies, Vol. 14, C. C. Gillispie, ed., New York: Charles Scribner's Sons, pp. 89-92.
Dongarra, J. and Sullivan, F. (2000). "The top 10 algorithms of the century". Compnt. Sci. Eng., 2, pp. 22-23. http://dx.doi.org/10.1109/MCISE.2000.814652
Dopico, F. M. and Molera, J. M. (2012). "Accurate solution of structured linear systems via rank-revealing decompositions". IMA J. Nnmer. Anal., 32 (3), pp. 1096-1116. http://dx.doi.org/10.1093/imanum/drr023
Golub, G. and Van Loan, C. (1996). Matrix, Computations. Baltimore, MD: Johns Hopkins University Press, 3rd edition.
Grcar, J. F. (2011a). "How ordinary elimination became Gaussian elimination". Historia Math., 38 (2), pp. 163-218. http://dx.doi.org/10.1016/j.hm.2010.06.003
Grcar, J. F. (2011b). "John von Neumann's analysis of Gaussian elimination and the origins of modern Numerical Analysis". SIAM Rev., 53 (4), pp. 607-682. http://dx.doi.org/10.1137/080734716
Grcar, J. F. (2011c). "Mathematicians of Gaussian elimination". Notices Amer. Math. Soc., 58 (6), pp. 782-792.
Grigori, L.; Demmel, J. W. and Xiang, H. (2011). "CALU: a communication optimal LU factorization algorithm". SIAM J. Matrix, Anal. Appl., 32 (4), pp. 1317-1350. http://dx.doi.org/10.1137/100788926
Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), second edition. http://dx.doi.org/10.1137/1.9780898718027
Higham, N. J. (2011). "Gaussian elimination". Wiley Interdisciplinary Reviews: Computational Statistics, 3, pp. 230-238. http://dx.doi.org/10.1002/wics.164
Hodges, A. (2012). Alan Turing: the Enigma. Princeton, NJ: Princeton University Press, centenary edition.
Hotelling, H. (1943). "Some new methods in matrix calculation". Ann. Math. Statistics, 14, pp. 1-34. http://dx.doi.org/10.1214/aoms/1177731489
Rigal, J.-L. and Gaches, J. (1967). "On the compatibility of a given solution with the data of a linear system". J. Assoc. Compnt. Mach., 14, pp. 543-548. http://dx.doi.org/10.1145/321406.321416
Rojas, R. and Hashagen, U. (eds.) (2000). The First Computers. History and Architectures. Cambridge, MA: MIT Press.
Trefethen, L. N. (2012). "The Smart Money's on Numerical Analysts". SIAM News, 45 (9), 1-5.
Trefethen, L. N. and David Bau III (1997). Numerical Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). http://dx.doi.org/10.1137/1.9780898719574
Turing, A. M. (1948). "Rounding-off errors in matrix processes". Quart. J. Mech. Appl. Math., 1, pp. 287-308. http://dx.doi.org/10.1093/qjmam/1.1.287
von Neumann, J. and Goldstine, H. H. (1947). "Numerical inverting of matrices of high order". Bull. Amer. Math. Soc., 53, pp. 1021-1099. http://dx.doi.org/10.1090/S0002-9904-1947-08909-6
Wilkinson, J. H. (1954). "Linear Algebra on the Pilot ACE". In Automatic Digital Computation, Her Majesty's Stationery Office, London.
Wilkinson, J. H. (1960). "Error analysis of floating-point computation". Numer. Math., 2, pp. 319-340. http://dx.doi.org/10.1007/BF01386233
Wilkinson, J. H. (1961). "Error analysis of direct methods of matrix inversion. I". J. Assoc. Comput. Mach., 8, pp. 281-330. http://dx.doi.org/10.1145/321075.321076
Wilkinson, J. H. (1963). Rounding Errors in Algebraic Processes. Englewood Cliffs, N.J.: Prentice-Hall Inc.
Wilkinson, J. H. (1965). The Algebraic Eigenvalue Problem. Oxford: Clarendon Press.
Wilkinson, J. H. (1971a). "Modern error analysis". SIAM Rev., 13, pp. 548-568. http://dx.doi.org/10.1137/1013095
Wilkinson, J. H. (1971b). "Some comments from a numerical analyst". J. Assoc. Comput. Mach., 18, pp. 137-147. http://dx.doi.org/10.1145/321637.321638
Published
How to Cite
Issue
Section
License
Copyright (c) 2013 Consejo Superior de Investigaciones Científicas (CSIC)
This work is licensed under a Creative Commons Attribution 4.0 International License.
© CSIC. Manuscripts published in both the printed and online versions of this Journal are the property of Consejo Superior de Investigaciones Científicas, and quoting this source is a requirement for any partial or full reproduction.All contents of this electronic edition, except where otherwise noted, are distributed under a “Creative Commons Attribution 4.0 International” (CC BY 4.0) License. You may read here the basic information and the legal text of the license. The indication of the CC BY 4.0 License must be expressly stated in this way when necessary.
Self-archiving in repositories, personal webpages or similar, of any version other than the published by the Editor, is not allowed.
