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