Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators

In 1946, the Office of Naval Research asked NBS to help found a national center for mathematical computa-tion. This center was to have four parts, the first of which was the Institute for Numerical Analysis (INA). The NBS director, E. U. Condon, sent his assistant, John Curtiss, to the west coast, and it was decided to locate the institute on the campus of UCLA. The INA was successful in attracting several renowned scientists, including Cornelius Lanczos, who was then working at the Boeing Aircraft Company in Seattle. Lanczos, a physicist and applied mathematician, had already been very successful at devising algorithms for analyzing a variety of mathematical models, and he was well acquainted with the challenges of computation on desk calculators. Since part of the INA mission was to pro-mote the effective use of the new " high-speed" auto-matic digital computers, his expertise was quite relevant, and he was immediately successful in solving problems of interest to the researchers there.

Lanczos first turned his attention to the solution of linear systems of equations and matrix eigenvalue problems. The eigenvalue problem was of particular interest to him, as he notes at the beginning of his paper [1], since the " vibrations of elastic structures, the flutter problems of aerodynamics, the stability problem of electric networks, [and] the atomic and molecular vibra-tions of particle physics" [1, p. 255] can all be analyzed in this way.

Computational researchers of that era faced a variety of challenges. With only minimal understanding of the effects of round-off errors on computations, they also needed to deal with remarkably small computer memories and limited computational capabilities. The SWAC, for instance, the NBS Western Automatic Computer, came on line in July 1950, capable of 16,000 operations per second on its 256 words of memory [2, Appendix C]!

It was in this computational environment that Lanczos investigated his method of " minimized itera-tions," a continuation of some work begun at Boeing.

Lanczos' presentation in this paper is almost matrix-free, not at all like the exposition of his algorithm in contemporary textbooks [3, Chap. 9]. Yet the descrip-tion is spare and elegant. He begins by noting that linear differential and integral operator equations can be solved by considering either of two series: the " Liouville-Neumann expansion," which only requires application of the operator but can suffer convergence difficulties; or the " Schmidt series," which is unconditionally convergent but requires knowledge of the eigensystem (Section II). Lanczos makes the remarkable observation that the first idea (which now is more commonly called a Krylov subspace expansion) can be improved by choosing a different set of basis functions, and he pro-poses a basis that is computationally convenient and numerically better behaved. Even better, his basis gives a finite expansion, rather than a series expansion, and thus yields a terminating algorithm, better suited for automatic computers. He devotes considerable attention to a numerical example that illustrates the algorithm and [12]) presents a model for the bookkeeping involved in its use (Section VI). But part of the genius of the paper is that he doesn' t stop there, but turns his attention to the very real numerical difficulties that can develop if the algorithm is used on large matrices, which to him mean those of dimension 12 or higher (Section VII). These difficulties motivated a major improvement of the algorithm: the development of a way to compute a basis using a three-term recurrence. With this improvement, he demonstrates the algorithm's effectiveness on practi-cal problems, such as computing the lateral vibrations of a bar (Section IX) and vibrations of a membrane and a string (Section X), through computational experiments carried out by Fannie M. Gordon. In the last sections of the paper, he discusses how to overcome complications that arise when finding the eigensystem of an operator rather than a matrix.

This work fit in very nicely with other developments at INA. Researchers such as George Forsythe, J. Barkley Rosser, and Magnus Hestenes were also thinking about eigenvalue problems and the solution of linear systems, and during the next two or three years they proposed and tested a variety of approaches for " large" problems. Lanczos, too, discussed the solution of linear systems using the recurrence of his minimized iterations [4], and recognized that it was mathematically equivalent to the method of conjugate gradients [5], another noteworthy NBS discovery discussed elsewhere in this volume. Despite the original promise of the method of mini-mized iterations, very little attention was given to it during the following 10 years. Other algorithms were more successful on problems of moderate size, and when " large" came to mean of dimension 1000 or larger, even the three-term recurrence had significant numerical difficulties. But two research projects renewed interest in the algorithm. In 1966, Shmuel Kaniel [6] studied the accuracy of the eigenvalue and eigenvector estimates when Lanczos' iteration is termi-nated early, as it must be when the size of the matrix is prohibitively large. This opened the possibility of using the algorithm to approximate the eigensystem, rather than aim for full accuracy. In 1971, Chris Paige [7,8,9] showed that even though round-off error ruins the orthogonality of Lanczos' basis, the necessary level of accuracy can be maintained by judicious choice of parameters and selective use of reorthogonalization. Paige's form of Lanczos' algorithm was now a practical alternative for truly large matrices.

Since then, continuous attention has been given to the method. Almost 300 articles were published about Lanczos' algorithm and related Krylov methods in the 25 years following publication of Lanczos' paper [10], and copious citations to it continue to this day even though it is a standard topic in textbooks and many citations do not go back to this primary source. There are several widely used numerical software packages, including one due to Horst Simon and coworkers such as Beresford Parlett at the University of California, Berkeley, and another due to Jane Cullum and Ralph Willoughby, developed at IBM. A package by David Scott is available through NIST's Guide to Available Software (GAMS) project.

This Krylov subspace method of Lanczos, and its later application to the solution of linear systems, was recently designated one of the Top Ten Algorithms of the Century [11] by Computing in Science and Engineering, a joint publication of the IEEE Computer Society and the American Institute of Physics. A fascinating account of Lanczos' life is given in an essay by Barbara Gellai at the beginning of the six volumes of his collected works [12, Vol 1, (1-3) -( 1-31)]. Cornelius Lanczos (born KorneŽ l Loš wy) began and ended his life peacefully in Hungary, but his life pivoted on three exiles. He was born in 1893, the eldest son of a Jewish lawyer. He attended Jewish elementary school, Catholic secondary school, and the University of Budapest. His Ph. D. work concerning special relativity received some attention by Einstein, but political turmoil in Hungary and a ceiling for the number of Jews at universities led Lanczos to move to Germany. He continued his work in physics, and published an integral formulation of the Schroš dinger equation [13] just before Schroš dinger published his differential equation formula-tion, but Lanczos' paper was misinterpreted for many years. During this period, he spent a year as Einstein's assistant, continued his work, and married a German, Maria Rupp.

In 1931, Lanczos began a second exile, as economic and political troubles made life in Germany difficult. Lanczos took a visiting position at Purdue University, but unfortunately had to travel without his wife, who had contracted tuberculosis and could not get a visa. He continued his work on Einstein's field equations, Dirac's equation, and other topics in physics, but increasingly his attention focused on mathematical techniques, and he developed the Tau method for approximating functions by telescoping series [14]. His wife died in 1939, and he brought his son to the United States. Dur-ing this period he also became known as an excellent teacher, eventually writing many popular and ground-breaking textbooks, celebrated for their clarity and their use of vivid examples. His approach to computation was unique for the time: he worked with calculator, not slide rule, and this led him to novel algorithmic approaches. In the early 1940s he derived a method for evaluating Fourier coefficients quickly [15], although the idea did not become widely known until the popularization of the (equivalent) Cooley-Tukey FFT algorithm.

During 1943-44, Lanczos had his first association with NBS, working on the Mathematical Tables Project, during a leave from Purdue. After some time at Boeing Aircraft Company in Seattle, he joined the Institute for Numerical Analysis of the NBS. This provided a fertile working environment, and Lanczos investigated algorithms for solving linear systems of equations and eigenvalue problems. But eventually, politicized investi-gations led to the resignation of Edward Condon as Director of NBS. Lanczos, too, came under investigation for allegedly being a communist sympathizer, and this may have contributed to his decision to begin a third exile, in 1952, and then permanently in 1954, to the Dublin Institute for Advanced Studies.

For the rest of his life, Lanczos maintained his ties to Dublin, although he traveled and lectured extensively. His expository skills were much renowned, and he won the Chauvenet Prize for mathematical exposition in 1960 for one of his papers [16]. He married another German, Ilse Hildebrand, and resumed his concentration on physics research, including the geometry of space-time, although his publications in mathematics contin-ued. He died of a heart attack on his second visit back to Hungary, in 1974.

Interest in Lanczos' work continues, however. A centenary celebration was held at North Carolina State University, and his eigenvalue paper [1] in particular continues to be a cornerstone of contemporary eigenvalue computation and research, with over 850 citations in Science Citation Index between 1983 and 1999.

Prepared by Dianne P. O' Leary.


[1] Cornelius Lanczos, An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Opera-tors, J. Res. Natl. Bur. Stand. 45, 255-282 (1950).

[2] Magnus R. Hestenes and John Todd, NBS-INA— The Institute for Numerical Analysis— UCLA 1947-1954, NIST Special Publica-tion 730, National Institute of Standards and Technology, Gaithersburg, MD (1991).

[3] Gene H. Golub and Charles F. Van Loan, Matrix Computations, Third Edition, Johns Hopkins University Press, Baltimore, MD (1996).

[4] Magnus R. Hestenes and Eduard Stiefel, Methods of Conjugate Gradients for Solving Linear Systems, J. Res. Natl. Bur. Stand. 49, 409-436 (1952).

[5] Cornelius Lanczos, Solution of Systems of Linear Equations by Minimized Iterations, J. Res. Natl. Bur. Stand. 49, 33-53 (1952).

[6] Shmuel Kaniel, Estimates for Some Computational Techniques in Linear Algebra, Math. Comp. 20, 369-378 (1966).

[7] C. C. Paige, The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices, Ph. D. Dissertation, University of London (1971).

[8] C. C. Paige, Practical Use of the Symmetric Lanczos Process with Re-Orthogonalization, BIT 10, 183-195 (1970).

[9] C. C. Paige, Computational Variants of the Lanczos Method for the Eigenproblem, J. Inst. Math. Appl. 10, 373-381 (1972).

[10] Gene H. Golub and Dianne P. O' Leary, Some History of the Conjugate Gradient and Lanczos Algorithms: 1948-1976, SIAM Rev. 31, 50-102 (1989).

[11] Top 10 Algorithms of the Century, Comput. Sci. Eng. 2 (1), (2000).

[12] William R. Davis, ed., Cornelius Lanczos, Collected Published Papers with Commentaries, College of Physical and Mathe-matical Sciences, North Carolina State University, Raleigh, NC (1998).

[13] Kornel Lanczos, U š ber eine feldmaš .ige Darstellung der neuen Quantenmechanik, Z. Phys. 35, 812-830 (1926).

[14] C. Lanczos, Trigonometric Interpolation of Empirical and Analytical Functions, J. Math. Phys. 17, 123-199 (1938).

[15] G. C. Danielson and C. Lanczos, Some Improvements in Practical Fourier Analysis and Their Application to X-Ray Scattering from Liquids, J. Franklin Inst. 233, 365-380, 435-452 (1942).

[16] C. Lanczos, Linear Systems in Self-Adjoint Form, Amer. Math. Monthly 65, 665-679 (1958).

Fig. 1. Cornelius Lanczos in 1946 (Courtesy of Mrs. Eleanor Boyk; used with permission from North Carolina State University

Fig. 2. Olga Taussky Todd and Cornelius Lanczos. Taussky Todd (1906-1995) was one of the original members of the NBS Institute for Numerical Analysis (1947-48) and was subsequently a consultant to the NBS Applied Mathematics Division in Washington (1949-54). She was an insightful and prolific mathematician who made many important contributions to early numerical analysis, especially in the areas of linear algebra and matrix theory.