Course description

In the January/February 2000 issue of Computing in Science and Engineering, Jack Dongarra and Francis Sullivan selected 10 algorithms with the greatest influence on science, numerical analysis, and engineering in the 20th century. In March 2016, Nick Higham (SIAM president, 2017-2018) presented a slightly revised list. In this course we will cover the motivations, ideas, history, and future impact of these ten algorithms.

Prerequities: A passion for numerical algorithms.

The top ten algorithms

• Newton and quasi-Newton methods,
• Matrix factorizations (LU, Cholesky, QR)
• SVD, QR and QZ algorithms,
• Monte-Carlo methods,
• Fast Fourier transform,
• Krylov subspace methods,
• JPEG,
• PageRank,
• Simplex method, and
• Kalman filter.

Honorable mentions: Bootstraping methods, fast multipole method, and quicksort.

Lecture notes
Lecture notes:

The lecture notes are written in Julia and published using Jupyter. Julia Cheat Sheet

Who, when, and where

Date and Time: Tu-Th, 11:40 - 12:45, Rockefeller 112
Instructors: Alex Townsend.

Evaluation
Whenever necessary there will be out-of-class exercises. These are mostly designed to save time in class.

Course project: The course project can be on anything related to a top-ten algorithm. Hopefully, the project will be on the student's research interest. A project report should be written up as a 5-7 page publication, i.e., clear and concise. It is a good idea to use LaTeX for the typesetting. Please select a project as soon as possible.

Important dates: 2nd and 4th of May, student presentation in-class. Written reports due on the 4th of May. Project information

Exercises
Here, are some exercises to aid the class discussion:

Matrix factorization: pdf
QR algorithm: pdf
Krylov subspace methods: pdf
Fast Fourier transform: pdf, Mat-vecs, Signal processing
JPEG: pdf
Quasi-Newton: pdf
Simplex:
Monte-Carlo:
PageRank: pdf
Fast Multipole method:

Classic publications
Classic publications on the ten algorithms:
• Quasi-Newton methods: "A class of methods for solving nonlinear simultaneous equations" by C. G. Broyden, 1965. Citation count 2220. pdf
• Matrix factorizations: "Unitary triangularization of a nonsymmetric matrix" by A. S. Householder, 1958. Citation count 483. pdf
• The QR algorithm: "The QR transformation a unitary analogue to the LR transformation -- Part 1", 1961. Citation count 874. pdf
• Monte-Carlo methods: "Equation of state calculations by fast computing machines" by Metropolis, Rosenbluth, Rosenbluth, Teller, and Teller, 1953. Citation count 33152. pdf
• The Fast Fourier transform: "An algorithm for the machine calculation of complex Fourier series", by J. W. Cooley and J. W. Tukey, 1965. Citation count 12084. pdf
• Conjugate gradient method: "Methods of conjugate gradients for solving linear systems", by M. R. Hestenes and E. Stiefel, 1952. Citation count 6855. pdf
• JPEG: "The JPEG still picture compression standard", by G. K. Wallace, 1992. Citation count 5526. pdf
• PageRank: "Google's patent" by Lawrence Page. html
• Simplex method: "The generalized simplex method for minimizing a linear form under linear inequality restraints, 1955. Citation count 599. pdf