I. Introduction to Applied Mathematics - Princeton University

1 48I. Introduction to Applied Mathematics7 Randomized AlgorithmsAll the algorithms described so far in this article aredeterministic: if they are run repeatedly on the samedata, they produce the same result every time. Somealgorithms make random choices and so generally pro-duce a different result every time they are run. Forexample, we might approximate 10f(x)dx 1nn i=1f(xi),where thexiare independent random numbers uni-formly distributed in[0,1]. The standard deviation ofthe error in this approximation is of ordern 1/2. Thisis an example of aMonte Carlo algorithm; such algo-rithms have a deterministic run time and produce anoutput that is correct (or has a given accuracy) witha certain probability.

2 Of course, there are much moreefficient ways to estimate a one-dimensional integral,but Monte Carlo algorithms come into their own formultidimensional integrals over complicated Vegas algorithmalways produces a correctresult, but its run time is nondeterministic. A classicexample is the quicksort algorithm for sorting a list ofnumbers, for which a randomized choice of the parti-tion element makes the algorithm much faster on aver-age than in the worst case (O(nlogn)running timeversusO(n2), fornnumbers).Randomized algorithms can be much simpler thandeterministic alternatives, they may be more able toexploit modern computing architectures, and they maybe better suited to large data sets.

3 There is a wide vari-ety of randomized algorithms, and they are studied inmathematics, computer science, statistics, and active area of research is randomized algorithmsfor numerical linear algebra problems, based on ran-dom sampling and random projections. For example,fast algorithms exist for computing low-rank approx-imations to a given matrix. The general framework isthat random sampling is used to identify a subspacethat captures most of the action of the matrix, thematrix is then compressed to this subspace, and alow-rank factorization is computed from the of randomized algorithms mentioned inthis book are the GooglePageRank algorithm[ ],with its use of a random surfer, thek-means algo-rithm[ ] for clustering, andmarkov chainmonte carlo algorithms[ 3].

4 8 Some Key Algorithmsin Applied MathematicsTable 2 lists a selection of algorithms mentioned inthis book. Very general methods such as precondition-ing and the finite-element method, which require muchmore information to produce a particular algorithm,are omitted. The table illustrates the wide variety ofimportant algorithms in Applied Mathematics , rangingfrom the old to the relatively notable feature of some of the algorithms is thatthey are iterative algorithms, which in principle take aninfinite number of steps, for solving problems that canbe solved directly, that is, in a finite number of opera-tions. The conjugate gradient and multigrid methodsare iterative methods for solving a linear system ofequations, and for suitably structured systems theycan provide a given level of accuracy much faster thanGaussian elimination, which is a direct method.

5 Sim-ilarly, interior point methods are iterative methodsfor linear programming, competing with the simplexmethod, which is a direct ReadingA classic reference for algorithms and their analy-sis is Donald Knuth sThe Art of Computer Program-ming. The first volume appeared in 1968 and the devel-opment is ongoing. Current volumes areFundamen-tal Algorithms(volume 1),Seminumerical Algorithms(volume 2),Sorting and Searching(volume 3), andCombinatorial Algorithms(volume 4), all published byAddison-Wesley (Reading, MA).Bentley, J. L. Pearls. Reading, , G., and P. Bratley. of Algorith-mics. Englewood Cliffs, NJ: , T. H.

6 , C. E. Leiserson, R. L. Rivest, and C. Stein. to Algorithms, 3rd edn. Cambridge, MA: , N. J. and Stability of NumericalAlgorithms, 2nd edn. Philadelphia, PA: Goals of Applied MathematicalResearchNicholas J. HighamA large body of existing mathematical knowledge isencapsulated in theorems, methods , and algorithms,some of which have been known for centuries. Butapplied Mathematics is not simply the application of Copyright, Princeton University Press. No part of this book may be distributed, posted, or reproduced in any form by digital or mechanical means without prior written permission of the publisher. For general queries, contact Goals of Applied Mathematical Research49 Table 2 Some algorithms mentioned in this early figuresGaussian 2 Ancient Chinese (ca.)

7 , Gauss (1809); formulatedas LU factorization by various authors from 1940sNewton s (1669), Raphson (1690)Fast Fourier (1805), Cooley and Tukey (1965)Cholesky 2 Cholesky (1910)Remez , 2 Remez (1934)Simplex (1947)(linear programming)Conjugate gradient 9 Hestenes and Stiefel (1952), Lanczos (1952)Lanczos methodsFord Fulkerson 7 Ford and Fulkerson (1956)k-means (1957), Steinhaus (1957)QR 2 Givens (1958), Householder (1958)Dijkstra s (1959)Quasi-Newton (1959), Broyden, Fletcher, Goldfarb, Powell,Shanno (early 1960s)QR (1961), Kublanovskaya (1962)QZ and Stewart (1973)Singular and Kahan (1965), Golub and Reinsch (1970)decompositionStrassen s 4 Strassen (1968) 9, 3, (1964), Brandt (1973), Hackbusch (1977)Interior point (1984)Generalized 9 Saad and Schulz (1986)residual methodFast multipole and Rokhlin (1987) 5, of the Joint Photographic Experts Group (1992) and Page (1998) (1999)existing mathematical ideas to practical problems: newresults are continually being developed, usually build-ing on old ones.

8 Applied mathematicians are alwaysinnovating, and the constant arrival of new or modifiedproblems provides direction and motivation for this article we describe some goals of researchin Applied Mathematics from the perspectives of theancient problem of solving equations, the more con-temporary theme of exploiting structure, and the prac-tically important tasks of modeling and prediction. Wealso discuss the strategy behind Solving EquationsA large proportion of Applied Mathematics researchpapers are about analyzing or solving equations. Theequations may be algebraic, such as linear or nonlin-ear equations in one or more variables.

9 They may beordinary differential equations (ODEs), partial differen-tial equations (PDEs), integral equations, or differential-algebraic wide variety of equations reflects the many dif-ferent ways in which one can attempt to capture thebehavior of the system being modeled. Whatever theequation, an Applied mathematician is interested inanswering a number of Does the Equation Have a Solution?We are interested in whether there is a unique solu-tion and, if there is more than one solution, how manythere are and how they are characterized. Existence ofsolutions may not be obvious, and one occasionally Copyright, Princeton University Press.

10 No part of this book may be distributed, posted, or reproduced in any form by digital or mechanical means without prior written permission of the publisher. For general queries, contact Introduction to Applied Mathematicshears tales of mathematicians who have solved equa-tions for which a proof is later given that no solutionexists. Such a circumstance may sound puzzling: is itnot easy to check that a putative solution actually isa solution? Unfortunately, checking satisfaction of theequation may not be easy, especially if one is workingin a function space. Moreover, the problem specifica-tion may require the solution to have certain proper-ties, such as existence of a certain number of deriva-tives, and the claimed solution might satisfy the equa-tion but fail to have some of the required of analyzing the problem in the precise form inwhich it is given, it may be better to investigate whatadditional properties must be imposed for an equationto have a unique Is the Equation Well-Posed?