In the 1000 or so pages of The Princeton Companion to Applied Mathematics the 165 authors offer insight, wisdom, and humour. Here is a selection of quotes from the book.

• Gil Strang (page 939)

“Our subject is extremely large!”

• David Tong (page 374)

“Classical mechanics is an ambitious subject. Its purpose is to predict the future and reconstruct the past, to determine the history of every particle in the universe.”

• Heather Mendick (page 949)

“Jurassic Park, which … contains perhaps the only screen example of a `cool’ mathematician.”

• Sergio Verdu (page 545)

“Authored in 1948 by Claude Shannon (1916–2001), `A mathematical theory of communication’ is the Magna Carta of the information age and information theory’s big bang.”

• Ya-xiang Yuan (page 953)

“China … has a long tradition of mathematicians being well respected, and famous mathematicians are often put into high-ranking positions in government.”

• Ian Stewart (page 912)

“Always wanted to write a book? Then do so. Just be aware of what you are letting yourself in for.”

In the January/February 2000 issue of Computing in Science and Engineering, Jack Dongarra and Francis Sullivan chose the “10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century” and presented a group of articles on them that they had commissioned and edited. (A SIAM News article by Barry Cipra gives a summary for anyone who does not have access to the original articles). This top ten list has attracted a lot of interest.

Sixteen years later, I though it would be interesting to produce such a list in a different way and see how it compares with the original top ten. My unscientific—but well defined— way of doing so is to determine which algorithms have the most page locators in the index of The Princeton Companion to Applied Mathematics (PCAM). This is a flawed measure for several reasons. First, the book focuses on applied mathematics, so some algorithms included in the original list may be outside its scope, though the book takes a broad view of the subject and includes many articles about applications and about topics on the interface with other areas. Second, the content is selective and the book does not attempt to cover all of applied mathematics. Third, the number of page locators is not necessarily a good measure of importance. However, the index was prepared by a professional indexer, so it should reflect the content of the book fairly objectively.

A problem facing anyone who compiles such a list is to define what is meant by “algorithm”. Where does one draw the line between an algorithm and a technique? For a simple example, is putting a rational function in partial fraction form an algorithm? In compiling the following list I have erred on the side of inclusion. This top ten list is in decreasing order of the number of page locators.

1. Newton and quasi-Newton methods
2. Matrix factorizations (LU, Cholesky, QR)
3. Singular value decomposition, QR and QZ algorithms
4. Monte-Carlo methods
5. Fast Fourier transform
6. Krylov subspace methods (conjugate gradients, Lanczos, GMRES, minres)
7. JPEG
8. PageRank
9. Simplex algorithm
10. Kalman filter

Note that JPEG (1992) and PageRank (1998) were youngsters in 2000, but all the other algorithms date back at least to the 1960s.

By comparison, the 2000 list is, in chronological order (no other ordering was given)

• Metropolis algorithm for Monte Carlo
• Simplex method for linear programming
• Krylov subspace iteration methods
• The decompositional approach to matrix computations
• The Fortran optimizing compiler
• QR algorithm for computing eigenvalues
• Quicksort algorithm for sorting
• Fast Fourier transform
• Integer relation detection
• Fast multipole method

The two lists agree in 7 of their entries. The differences are:

PCAM list	2000 list
Newton and quasi-Newton methods	The Fortran Optimizing Compiler
Jpeg	Quicksort algorithm for sorting
PageRank	Integer relation detection
Kalman filter	Fast multipole method

Of those in the right-hand column, Fortran is in the index of PCAM and would have made the list, but so would C, MATLAB, etc., and I draw the line at including languages and compilers; the fast multipole method nearly made the PCAM table; and quicksort and integer relation detection both have one page locator in the PCAM index.

There is a remarkable agreement between the two lists! Dongarra and Sullivan say they knew that “whatever we came up with in the end, it would be controversial”. Their top ten has certainly stimulated some debate, but I don’t think it has been too controversial. This comparison suggests that Dongarra and Sullivan did a pretty good job, and one that has stood the test of time well.

Finally, I point readers to a talk Who invented the great numerical algorithms? by Nick Trefethen for a historical perspective on algorithms, including most of those mentioned above.

The BBC Earth website has just published a selection of short articles on beautiful mathematical equations and is asking readers to vote for their favourite.

I wondered if we had included these equations in The Princeton Companion to Applied Mathematics (PCAM), specifically in Part III: Equations, Laws, and Functions of Applied Mathematics. We had indeed included the ones most relevant to applied mathematics. Here are those equations, with links to the BBC articles.

• The wave equation (which quotes PCAM author Ian Stewart). PCAM has a short article by Paul Martin of the same title (III.31), and the wave equation appears throughout the book.
• Einstein’s field equation. PCAM has a 2-page article Einstein’s Field Equations (note the plural), by Malcolm MacCallum (article III.10).
• The Euler-Lagrange equation. PCAM article III.12 by Paul Glendinning is about these equations, and more appears in other articles, especially The Calculus of Variations (IV.6), by Irene Fonseca and Giovanni Leoni.
• The Dirac equation. A 3-page PCAM article by Mark Dennis (III.9) describes this equation and its quantum mechanics roots.
• The logistic map. PCAM article The logistic equation (III.19), by Paul Glendinning treats this equation, in both differential and difference forms. It occurs in several places in the book.
• Bayes’ theorem. This theorem appears in the PCAM article Bayesian Inference in Applied Mathematics (V.11), by Des Higham, and in other articles employing Bayesian methods.

A natural equation is: Are there other worthy equations that are the subject of articles in Part III of PCAM that have not been included in the BBC list? Yes! Here are some examples (assuming that only single equations are allowed, which rules out the Cauchy-Riemann equations, for example).

• The Black-Scholes equation.
• The diffusion (or heat) equation.
• Laplace’s equation.
• The Riccati equation.
• Schrödinger’s equation.

The Princeton Companion to Applied Mathematics, discussed in these previous posts, has a wide target audience, which includes mathematicians at undergraduate level or above; students, researchers, and professionals in other subjects who use mathematics; and mathematically interested lay readers.

Here are some examples of how different people can use the book.

• Undergraduate students can use it to get an overview of topics they are studying and to find out what areas of applied mathematics they might like to pursue at graduate level. Many of the articles have minimal pre-requisites (indeed some contain few, if any, equations). My article Color Spaces and Digital Imaging, for example, requires just knowledge of integration and basic linear algebra.
• A teacher might find useful the articles The History of Applied Mathematics and the four-part article Teaching Applied Mathematics, as well as the various short articles on interesting problems and applications (e.g., Cloaking, Bubbles, The Flight of a Golf Ball, Robotics, Medical Imaging, Text Mining, and Voting Systems).
• Researchers can use the book to find out about topics outside their area that they encounter in seminars but never have the time to study in the research literature.
• Engineers can use the book to find out about some of the latest mathematical developments relevant to their interests. The articles Aircraft Noise, Inerters, and Signal Processing, and the index entries “aerodynamics”, “energy-efficient buildings”, and “finite-element methods”, are good starting points.
• Students at all levels can learn about how to read and write mathematics, including the use of relevant computer tools, from several articles in Part VII, “Final Perspectives”.
• Anyone can use the book for reference. Although it is not a dictionary, encyclopedia, or handbook, The Companion‘s extensive index makes it easy to locate material, including definitions, equations, functions, laws, theorems, and so on.

• The book, produced with , is a great example of how to typeset mathematics, with examples of all kinds of equations, figures, and tables. For those learning or new to mathematical typesetting it should be a source of ideas and inspiration. The source code is not provided, but feel free to contact me with questions about how things were done and I will write a post that answers the most common questions.
• The final collection of articles, by mathematicians from China, France, the UK, and the USA, gives advice on how to make the case for mathematics to politicians, and will be of interest to anyone who wishes to promote the importance of mathematics.

A lot of applied mathematics relies on computation, whether symbolic or numeric, so many applied mathematicians need to program as part of their work. It was therefore natural to include an article on programming languages in The Princeton Companion to Applied Mathematics.

The article, which I wrote, has two main purposes. The first is to give a history of those programming languages relevant to applied mathematics. The first such language, and indeed the first high-level programming language, was Fortran (1957). The language was standardized in 1966 and it is still going strong, with the most recent standard published in 2008. Developments in programming languages show no sign of abating, with the introduction in recent years of new languages such as Scala (2003), Clojure (2007, a dialect of Lisp), and Julia (2012), as well as new standards for older languages such as C (2011) and C++ (2011).

The second purpose of the article is to discuss mathematical aspects of programming, including

• notation (infix, prefix, reverse-Polish)
• implementation of complex arithmetic
• floating-point semantics
• high-precision computations
• types
• complexity analysis of codes
• structured programming
• literate programming
• domain-specific languages

One issue that I discuss is the mutually beneficial influences that mathematics and programming languages have had on each other. For example, the notation for the ceiling and floor functions that map a real number to the next larger or smaller integer, respectively, illustrated by and , was first introduced in the programming language APL. The colon notation for array subscripting, A(i:j,r:s), used in Algol 68 and MATLAB, is now routinely used in linear algebra, in both equations and in pseudocode.

On the other hand, mathematics has influenced, or anticipated, syntax in programming languages. In the 1800s Cayley proposed two different notations to distinguish between the products and in the context of groups, but both were ungainly and difficult to typeset. In 1928, Hensel suggested the notation and . Although his suggestion appears to have attracted little or no attention, it was was reinvented by Cleve Moler for MATLAB and is now a notation familiar to anyone who works in numerical linear algebra.

At the start of the article I include a figure containing the first program written for a stored-program computer, namely the highest factor routine that ran on the Manchester “Baby” on June 21, 1948. The program was by Tom Kilburn and is taken from Geoff Tootill‘s notebook. Tootill is still alive (aged 93), and he kindly gave permission for me to reproduce the image.

The article, which has the same title as this post, can be downloaded in pre-publication form as an EPrint.