Contents of this file: [1] Trefethen NA-net posting of 9 May 1993 [2] bibliographic citations for 13 "classic papers" [3] longer list of papers we considered reading [4] copy of handout to class describing course organization [5] weekly assignments These items are separated by dashed lines. ----------------------------------------------------------------- | Prof. L. N. Trefethen Phone: (607) 255-4222 | | Dept. of Computer Science Fax: " 255-4428 | | Upson Hall, Cornell University | | Ithaca, NY 14853-7501 Email: lnt@cs.cornell.edu | ----------------------------------------------------------------- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - [1] Trefethen NA-net posting of 9 May 1993 From: Nick Trefethen Date: Thu, 6 May 93 10:36:16 -0400 Subject: Classic Papers in Numerical Analysis "CLASSIC PAPERS IN NUMERICAL ANALYSIS" NA-Netters may be interested to hear of my experiences this spring teaching a seminar with the above title to a dozen Cornell graduate students (three of whom were actually post-docs or faculty). Comp. Sci. 722 met once a week for two hours, and in the course of the semester we read thirteen papers: 1. Cooley & Tukey (1965) the Fast Fourier Transform 2. Courant, Friedrichs & Lewy (1928) finite difference methods for PDE 3. Householder (1958) QR factorization of matrices 4. Curtiss & Hirschfelder (1952) stiffness of ODEs; BD formulas 5. de Boor (1972) calculations with B-splines 6. Courant (1943) finite element methods for PDE 7. Golub & Kahan (1965) the singular value decomposition 8. Brandt (1977) multigrid algorithms 9. Hestenes & Stiefel (1952) the conjugate gradient iteration 10. Fletcher & Powell (1963) optimization via quasi-Newton updates 11. Wanner, Hairer & Norsett (1978) order stars and applications to ODE 12. Karmarkar (1984) interior pt. methods for linear prog. 13. Greengard & Rokhlin (1987) multipole methods for particles Most weeks, one or two related readings were also assigned, typically from a recent textbook or survey article. For example, along with the Fletcher & Powell paper we read an extract from the 1983 text by Dennis & Schnabel. Our weekly meetings followed a regular format. First, this week's Historian distributed a handout containing information he/she had obtained about the historical context of the paper, including biographical information about the author(s) and a plot of citations as a function of time. Next, the Mathematician gave a presentation of some of the central ideas of the paper. Third and fourth, two Experimentalists reported the results of Matlab, C, or Fortran experiments conducted to illustrate some of the properties of the algorithm under discussion. Finally, the Professor added a few remarks. To me and at least some of the students, this course provided a satisfying vision of the broad scope of numerical analysis and a sense of excitement at what a diversity of beautiful and powerful ideas have been invented in this field. The thirteen papers were selected partly for their variety; they touch upon nearly all the main problems of numerical computation. We found that although they vary greatly in style, most are quite readable. Indeed it was a pleasure, week after week, to be in the hands of the masters. These authors are for the most part extraordinary people, including some about whom most numerical analysts know little (such as Hirschfelder, one of the leading American chemists of this century). We were struck by how young many of the authors were when they wrote these papers (average age: 34), and by how short an influential paper can be (Householder: 3.3 pages, Cooley & Tukey: 4.4). Our readings also uncovered a few surprises. For example, Curtiss and Hirschfelder inexplicably define stiffness in terms of exponentially diverging trajectories, not converging ones; nevertheless they invent the right cure for the problem in the shape of backward differentiation formulas. For another example, did you know that the classic SVD paper by Golub & Kahan makes no mention of the QR algorithm? Our thirteen papers fall into three categories: Finite algorithms for finite problems: papers 1,3,5 Infinite algorithms for infinite problems: papers 2,4,6,7,10,11 Infinite algorithms for finite problems: papers 8,9,12,13 (An infinite algorithm is one that depends on an iteration or discretization parameter; an infinite problem is one for which all exact algorithms must be infinite.) The third category is particularly interesting. Evidently four of the most exciting modern developments in numerical analysis -- multigrid iterations, conjugate gradient iterations, interior point methods, and multipole methods -- have in common that they depend on the approximate computation of quantities that might in principle be computed exactly. Most readers of this note will have thought of other classic authors and papers that should have been on the list. We agree! We are saving up ideas for the next run of CS 722 in a couple of years. Nick Trefethen Dept. of Computer Science Cornell University - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - [2] bibliographic citations for 13 "classic papers" Fuller bibliographic citations: 1. James W. Cooley and John W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Mathematics of Computation 19 (1965), 297-301. 2. R. Courant, K. O. Friedrichs and H. Lewy, "Ueber die partiellen Differenzengleichungen der mathematischen Physik," Mathematische Annalen 100 (1928), 32-74. Translated as: "On the partial difference equations of mathematical physics," IBM Journal of Resarch and Development 11 (1967), 215-234. 3. A. S. Householder, "Unitary triangularization of a nonsymmetric matrix," Journal of the Association of Computing Machinery 5 (1958), 339-342. 4. C. F. Curtiss and J. O. Hirschfelder, "Integration of stiff equations," Proceedings of the National Academy of Sciences 38 (1952), 235-243. 5. C. de Boor, "On calculating with B-splines," Journal of Approximation Theory 6 (1972), 50-62. 6. R. Courant, "Variational methods for the solution of problems of equilibrium and vibrations," Bulletin of the American Mathematical Society 49 (1943), 1-23. 7. G. Golub and W. Kahan, "Calculating the singular values and pseudo-inverse of a matrix," SIAM Journal on Numerical Analysis 2 (1965), 205-224. 8. A. Brandt, "Multi-level adaptive solutions to boundary-value problems," Mathematics of Computation 31 (1977), 333-390. 9. Magnus R. Hestenes and Eduard Stiefel, "Methods of conjugate gradients for solving linear systems," Journal of Research of the National Bureau of Standards 49 (1952), 409-436. 10. R. Fletcher and M. J. D. Powell, "A rapidly convergent descent method for minimization," Computer Journal 6 (1963), 163-168. 11. G. Wanner, E. Hairer and S. P. Norsett, "Order stars and stability theorems," BIT 18 (1974), 475-489. 12. N. Karmarkar, "A new polynomial-time algorithm for linear programming," Combinatorica 4 (1984), 373-395. 13. L. Greengard and V. Rokhlin, "A fast algorithm for particle simulations," Journal of Computational Physics 72 (1987), 325-348. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - [3] longer list of papers we considered reading LINEAR ALGEBRA - SYSTEMS OF EQUATIONS AND LEAST-SQUARES Frankel (1950) optimal omega for SOR iteration Hestenes & Stiefel (1952) the conjugate gradient iteration Young (1954) theory of classical iterative methods Householder (1958) QR decomposition Wilkinson (1961) error analysis for systems of eqs. Golub (1965) least-squares problems Strassen (1969) Gaussian elimination is not optimal George (1973) nested dissection Gill, Golub, Murray & Saunders (1974) updating matrix factorizations Concus, Golub & O'Leary (1976) preconditioned conjugate gradients Meijerink & van der Vorst (1977) incomplete LU preconditioning Skeel (1980) iterative refinement and stability Saad & Schultz (1986) GMRES for nonsymmetric systems LINEAR ALGEBRA - EIGENVALUES AND SVD Jacobi (1846) Jacobi's method for matrix eigenvalues Henrici (1958) convergence of the Jacobi method Rutishauser (1958) the LR algorithm Kublanovskaya (1961) the QR algorithm Francis (1961) the QR algorithm Golub & Kahan (1965) computation of the SVD Moler & Stewart (1973) QZ algorithm for gen'd eigenvalues Cuppen (1981) divide and conquer for eigenvalues OPTIMIZATION Dantzig (1951) simplex method for linear programming Davidon (1959) variable metric methods Fletcher & Powell (1963) DFP quasi-Newton update formula Broyden/Fletcher/Goldfarb/Shanno (`70) BFGS quasi-Newton update formula Karmarkar (1984) interior pt methods for linear prog. INTEGRATION Golub & Welsch (1969) Gauss quadrature rules de Boor (1971) adaptive quadrature algorithms APPROXIMATION Remes (1934) Remes algorithm for Chebyshev approx. Schoenberg (1946) splines Powell (1967) near-optimality of Chebyshev interp. Reinsch (1967) smoothing with splines Cox (1972) calculation with B-splines de Boor (1972) calculation with B-splines OTHER Aitken (1932) Aitken extrapolation Cooley & Tukey (1965) the fast Fourier transform Greengard & Rokhlin (1987) fast multipole methods ODEs Curtiss & Hirschfelder (1952) stiffness and BD formulas Dahlquist (1956) stability and convergence Dahlquist (1963) A-stability Butcher (1965) Runge-Kutta methods Gear (1969) stiff ODEs Wanner, Hairer & Norsett (1978) order stars and stability theorems ELLIPTIC PDEs Peaceman & Rachford (1955) ADI Douglas (1955) ADI Strang (1971 or 1973) finite elements and approx. theory Buzbee, Golub & Nielsen (1970) fast Poisson via cyclic reduction Hockney (1965) fast Poisson via FFT Fedorenko (1961) multigrid methods Brandt (1977) multigrid methods PARABOLIC AND HYPERBOLIC PDEs Courant, Friedrichs & Lewy (1928) the CFL condition Crank & Nicolson (1947) finite differences for parabolic PDE O'Brien, Hyman & Kaplan (1951) Von Neumann stability analysis Lax & Richtmyer (1956) general stability theory Lax & Wendroff (1960,1962,1964) methods for solving conservation laws Kreiss (1962) more general stability theory Orszag (1971) spectral methods Kreiss and Oliger (1972) spectral methods Gustafsson, Kreiss & Sundstrom (1972) stability of boundary conditions Chorin (1973) vortex methods for CFD Engquist & Majda (1977) absorbing boundary conditions - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - [4] copy of handout to class describing course organization [contains some idiosyncratic Trefethen TeX macros; sorry] \input mac {\large \ctr{\bf ``Classic Papers in Numerical Analysis''} \ss \ctr{\fourteenpt CS 722, Spring 1993} \par} \ms\vfill Instructor: Nick Trefethen, Upson 4148, 255-4222, LNT@cs.cornell.edu Meetings: one two-hour meeting each week at a time and place to be determined Prerequisites: (1) ideally, at least two of CS 621, 622, 624 or their equivalents; and\hb \hbox{\phantom{Prerequisites: }(2) a serious commitment to numerical analysis.} All students, even those on reduced tuition, must register to take the course for a grade (i.e., no auditors). The grade will be A for those students who remain involved with the course throughout the semester and contribute to its success. Non-students may also participate provided they agree to act like students. There will be thirteen weekly meetings, each organized around a classic paper and related readings. Each student should read all the readings each week and be prepared to participate in discussions. Our aim each week will be to have a lively discussion and a good time. Each week's meeting will be organized about the following principal players: \par \ss {\leftskip 1.5in\parskip=3pt\obeylines The {\bf Historian} The {\bf Mathematician} Two {\bf Experimentalists} The {\bf Professor} (L.N.~Trefethen, ex officio) } \vfill A rough agenda will be as follows: \def\item #1. (#2) {\par\hangindent 0 pt\hangafter=0\indent \llap{#1. }($\approx #2$~mins.) } \def\itemeach #1. (#2) {\par\hangindent 0 pt\hangafter=0\indent \llap{#1. }($\approx #2$~mins.~each)~~} \vfill \item 1. (15) The Historian will distribute to the class a handout containing information he/she has obtained about the historical context of the paper. This handout should include a plot of citations as a function of time (e.g.\ from the {\sl Science Citation Index.})~~Examples of other interesting information might be the original review in {\sl Math.~Reviews\/} or the {\sl Zentralblatt f\"ur Mathematik,} biographical entries from {\sl Who's Who,} obituaries from the {\sl New York Times,} historical remarks found in numerical analysis textbooks, results of a conversation with a relevant Cornell faculty member, a survey of impact on software libraries, etc. \item 2. (30) The Mathematician is responsible for reading the main paper with exceptional care. Ideally, he/she will understand all the details of the paper, though it is recognized that this will not always be possible. His/her assignment is to speak with the class about the technical aspects of the paper. Depending on his/her inclinations, this might take the form of a systematic lecture presentation or of a guided discussion of certain interesting points. \itemeach 3,$\,$4. (15) During the week, each Experimentalist will have played with this week's topic on the computer. In most cases this can best be done in Matlab. He/she is responsible for preparing a handout with plots and/or numbers that will form the basis of a class discussion. In certain cases it may be appropriate simply to perform experiments illustrating the results obtained in the paper. In other cases it is hoped the Experimentalists will explore nontrivial applications or unexplained phenomena. \item 5. (15) Finally, the Professor will add whatever comments he deems appropriate. \vfill Some of the roles above may sometimes be played by pairs of students rather than individuals. In particular, it may be more fun for an Experimentalist to be a pair rather than a solo. This agenda is just a proposal---I am open to suggestions for changes. \eject\end - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - [5] weekly assignments [contains some idiosyncratic Trefethen TeX macros; sorry] \ctr{\fourteenpt\bf Week 1} \ul{Paper} \hangindent 20pt Cooley \& Tukey (1965): ``An algorithm for the machine calculation of complex Fourier series'' \bs \ul{Related readings} \hangindent 20pt Heideman, Johnson, and Burrus (1984): ``Gauss and the history of the fast Fourier transform'' Cooley (1987): ``How the FFT gained acceptance'' Burrus (1990): ``Notes on the FFT'' \ctr{\fourteenpt\bf Week 2} \ul{Paper} \hangindent 20pt Courant, Friedrichs, and Lewy (1928): ``On the partial differential equations of mathematical physics,'' 1967 English translation (especially Part II) \bs \ul{Related readings} \hangindent 20pt Lax (1967): ``Hyperbolic difference equations: A review of the Courant-Friedrichs-Lewy paper in the light of recent developments'' \hangindent 20pt Sod (1985): {\sl Numerical Methods in Fluid Mechanics,} sec.~III.2 on ``The Courant-Fried\-richs-Lewy condition'' \ctr{\fourteenpt\bf Week 3} \ul{Paper} \hangindent 20pt Householder (1958): ``Unitary triangularization of a nonsymmetric matrix'' \bs \ul{Related reading} \hangindent 20pt Golub (1965): ``Numerical methods for solving linear least squares problems'' \ctr{\fourteenpt\bf Week 4} \ul{Paper} \hangindent 20pt Curtiss \& Hirschfelder (1952): ``Integration of stiff equations'' \bs \ul{Related readings} \hangindent 20pt Dahlquist (1963): ``A special stability problem for linear multistep methods'' \hangindent 20pt Hairer \& Wanner (1991): {\sl Solving Ordinary Differential Equations II,} pp.~1--25. \ctr{\fourteenpt\bf Week 5} \ul{Paper} \hangindent 20pt de Boor (1972): ``On calculating with $B$-splines'' \bs \ul{Related readings} \hangindent 20pt Cox (1972): ``The numerical evaluation of $B$-splines'' \hangindent 20pt M.J.D. Powell (1981): ``Approximation Theory and Methods,'' chaps.~18 \& 19 \ctr{\fourteenpt\bf Week 6} \ul{Paper} \hangindent 20pt Courant (1943): ``Variational methods for the solution of problems of equilibrium and vibrations'' \bs \ul{Related reading} \hangindent 20pt Strang (1973): ``Piecewise polynomials and the finite element method'' \ctr{\fourteenpt\bf Week 7} \ul{Paper} \hangindent 20pt Golub \& Kahan (1965): ``Calculating the singular values and pseudo-inverse of a matrix'' \bs \ul{Related reading} \hangindent 20pt Francis (1961): ``The QR transformation: a unitary analogue to the LR transformation'' (parts I \& II) \ctr{\fourteenpt\bf Week 8} \ul{Paper} \hangindent 20pt Brandt (1977): ``Multilevel adaptive solutions to boundary-value problems'' \bs \ul{Related readings} \hangindent 20pt none \ctr{\fourteenpt\bf Week 9} \ul{Paper} \hangindent 20pt Hestenes \& Stiefel (1952): ``Methods of conjugate gradients for solving linear systems'' \bs \ul{Related reading} \hangindent 20pt Trefethen (1990): ``Approximation theory and numerical linear algebra''\hb (sections 1 and 2) \ctr{\fourteenpt\bf Week 10} \ul{Paper} \hangindent 20pt Fletcher \& Powell (1963): ``A rapidly convergent descent method for minimization'' \bs \ul{Related readings} \hangindent 20pt Dennis \& Schnabel (1983): extracts from {\it Numerical Methods for Unconstrained Optimization and Nonlinear Equations} \hangindent 20pt Davidon (1959): ``Variable metric method for optimization'' (1991 reprinting) \ctr{\fourteenpt\bf Week 11} \ul{Paper} \hangindent 20pt Wanner, Hairer \& N\o rsett (1978): ``Order stars and stability theorems" \bs \ul{Related reading} \hangindent 20pt Hairer \& Wanner (1991): {\it Solving Ordinary Differential Equations II\/} (section IV.4) \ctr{\fourteenpt\bf Week 12} \ul{Paper} \hangindent 20pt Karmarkar (1984): ``A new polynomial-time algorithm for linear programming'' \bs \ul{Related readings} \hangindent 20pt Wright (1992): ``Interior methods for constrained optimization'' \ctr{\fourteenpt\bf Week 13} \ul{Paper} \hangindent 20pt Greengard \& Rokhlin (1987): ``A fast algorithm for particle simulations'' \bs \ul{Related reading} \hangindent 20pt none