Math 707001 Special Topics: Fast Numerical Algorithms
The future belongs to "fast" methods. 
Vladimir Rokhlin in his response to 2001 Steele Prize Seminal Contribution to Research
The faster the computer, the more important the speed of algorithms. 
Lloyd N. Trefethen
in his essay "The Definition of Numerical Analysis" (SIAM News, 1992)
Multipole methods and their descedants will be ubiquitous.  Lloyd N. Trefethen in
his essay
"Predictions for Scientific Computing Fifty Years From Now" (Mathematics Today, 2000)
Introduction

This is an advanced graduate course in numerical methods. The course
will cover stateoftheart analysisbased fast numerical algorithms for computing discrete
summations/transforms and for solving differential/integral
equations which are developed only in last twenty years. In particular, the course
discusses fast multipole methods and their descendants. The fast multipole method is
ranked as one of the
top ten
algorithms of the 20th century by the journal Computing in Science &
Engineering (January 2000
Volume 2, Issue 1, pp. 297), a joint publication of the American Institute
of Physics and the IEEE Computer Society.
Prerequisites:

Linear Algebra, Advanced Calculus, Partial Differential Equations, and
Programming Experience in either Fortran or C++
Textbook:
There is no textbook for this course since the subject is quite new and
still under active development. However, the following lecture notes
should be very useful:
Topics will be selected from the list below.
(* sign indicates that the topic will definitely be covered.
)

Fast Multipole Methods (*)

The Fast Gauss Transform

Fast Fourier Transforms for Nonequispaced Data (*)

General Fast Summations/Transforms

Krylovspacebased Iterative Solvers: GMRES and Conjugate Gradient (*)

Introduction to Integral Equations (*)

Introduction to Potential Theory (*)

Fast Algorithms for Elliptic PDEs (*)

Compression of Low Rank Matrices

Fast Direct Solver for BVPs for Elliptic PDEs

Fast Algorithms for TwoPoint Boundary Value Problems

Fast Algorithms for the Heat Equation

Fast Algorithms for the Wave Equation

Fast Algorithms for the Stokes Equation

Fast Algorithms for the LippmannSchwinger equation

Generalized Gaussian Quadrature and Sumofexponentials Approximation

Fast Algorithms for Nonreflecting Boundary Conditions
Main resources and suggested readings:
(suggested readings are marked with * sign)

Fast Multipole Methods

Greengard, L.; Rokhlin, V. A fast algorithm for particle simulations.
J. Comput. Phys. 73 (1987), no. 2, 325348. (*)
2001 Steele Prize Seminal
Contribution to Research

Carrier, J.; Greengard, L.; Rokhlin, V. A fast adaptive multipole algorithm for particle simulations. SIAM J. Sci. Statist. Comput. 9 (1988), no. 4, 669686.

Rokhlin, V. Rapid solution of integral equations of scattering theory in two dimensions. J. Comput. Phys. 86 (1990), no. 2, 414439. (*)

Nabors, K.; Korsmeyer, F. T.; Leighton, F. T.; White, J. Preconditioned, adaptive,
multipoleaccelerated iterative methods for threedimensional firstkind integral
equations of potential theory. Iterative methods in numerical linear algebra (Copper
Mountain Resort, CO, 1992). SIAM J. Sci. Comput. 15 (1994), no. 3, 713735. (*)

Rokhlin, V. Diagonal forms of translation operators for the Helmholtz
equation in three dimensions. Appl. Comput. Harmon. Anal. 1 (1993),
no. 1, 8293.

Greengard, Leslie; Rokhlin, Vladimir A new version of the fast multipole method for
the Laplace equation in three dimensions. Acta numerica, 1997, 229269, Acta
Numer., 6, Cambridge Univ. Press, Cambridge, 1997. (*)

Hrycak, Tomasz; Rokhlin, Vladimir An improved fast multipole algorithm for potential fields. SIAM J. Sci. Comput. 19 (1998), no. 6, 18041826 (*)

Cheng, H.; Greengard, L.; Rokhlin, V. A fast adaptive multipole algorithm in three dimensions. J. Comput. Phys. 155 (1999), no. 2, 468498.

Yarvin, Norman; Rokhlin, Vladimir An improved fast multipole algorithm for potential fields on the line. SIAM J. Numer. Anal. 36 (1999), no. 2, 629666

Sun, Xiaobai; Pitsianis, Nikos P. A matrix version of the fast multipole method.
SIAM Rev. 43 (2001), no. 2, 289300 (*)

Gimbutas, Zydrunas; Rokhlin, Vladimir A generalized fast multipole method for nonoscillatory kernels. SIAM J. Sci. Comput. 24 (2002), no. 3, 796817

Ying, Lexing; Biros, George; Zorin, Denis A kernelindependent adaptive fast multipole algorithm in two and three dimensions. J. Comput. Phys. 196 (2004), no. 2, 591626. (*)

The Fast Gauss Transform

Greengard, Leslie; Strain, John The fast Gauss transform. SIAM
J. Sci. Statist. Comput. 12 (1991), no. 1, 7994. (*)

Strain, John The fast Gauss transform with variable scales. SIAM J. Sci. Statist. Comput. 12 (1991), no. 5, 11311139.

Greengard, Leslie; Sun, Xiaobai A new version of the fast Gauss
transform. Proceedings of the International Congress of Mathematicians, Vol. III
(Berlin, 1998). Doc. Math. 1998, Extra Vol. III, 575584.

Andersson, Fredrik; Beylkin, Gregory The fast Gauss transform with complex parameters. J. Comput. Phys. 203 (2005), no. 1, 274286.

Fast Fourier Transforms for Nonequispaced Data

Dutt, A.; Rokhlin, V. Fast Fourier transforms for nonequispaced data. SIAM J. Sci. Comput. 14 (1993), no. 6, 13681393.
(pdf)

Dutt, A.; Rokhlin, V. Fast Fourier transforms for nonequispaced data. II. Appl. Comput. Harmon. Anal. 2 (1995), no. 1, 85100.

Greengard, Leslie; Lee, JuneYub Accelerating the nonuniform fast Fourier transform.
SIAM Rev. 46 (2004), no. 3, 443454 (*)

Lee, JuneYub; Greengard, Leslie The type 3 nonuniform FFT and its applications. J. Comput. Phys. 206 (2005), no. 1, 15.

General Fast Summations/Transforms

Strain, John Fast potential theory. II. Layer potentials and discrete sums. J. Comput. Phys. 99 (1992), no. 2, 251270.

Gu, Ming; Eisenstat, Stanley C. A divideandconquer algorithm for the symmetric tridiagonal eigenproblem. SIAM J. Matrix Anal. Appl. 16 (1995), no. 1, 172191.

Rokhlin, Vladimir and Mark Tygert, "Fast algorithms for spherical harmonic expansions," SIAM Journal on Scientific Computing, 27 (6): 19031928, 2006.

Tygert, Mark, "Recurrence relations and fast algorithms," Technical Report 1343, Yale University, Department of Computer Science, December 2005.

Mark Tygert, "Fast algorithms for spherical harmonic expansions, II," Technical Report 1381, Yale University, Department of Computer Science, May 2007.

Michael O'Neal and Vladimir Rokhlin "A new class of analysisbased fast transforms" Technical Report 1384, Yale University, Department of Computer Science, August 2007.

Krylovspacebased Iterative Solvers: GMRES and Conjugate Gradient

Trefethen, Lloyd N.; Bau, David, III Numerical linear algebra. SIAM, Philadelphia, PA, 1997.

Demmel, James W. Applied numerical linear algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. ISBN: 0898713897

Introduction to Integral Equations

Atkinson, Kendall E. The numerical solution of integral equations of the second kind. Cambridge Monographs on Applied and Computational Mathematics, 4. Cambridge University Press, Cambridge, 1997. xvi+552 pp. ISBN: 0521583918

Guenther, Ronald B.; Lee, John W. Partial differential equations of mathematical physics and integral equations. Corrected reprint of the 1988 original. Dover Publications, Inc., Mineola, NY, 1996. xii+562 pp. ISBN: 0486688895

Introduction to Potential Theory

Kellogg, Oliver Dimon Foundations of potential theory. Dover, 1953.

Jiang, Shidong Jump relations of the quadruple layer potential on a regular surface in three dimensions. Appl. Comput. Harmon. Anal. 21 (2006), no. 3, 395403.

Kolm, Petter; Jiang, Shidong; Rokhlin, Vladimir Quadruple and octuple layer potentials in two dimensions. I. Analytical apparatus. Appl. Comput. Harmon. Anal. 14 (2003), no. 1, 4774.

Fast Algorithms for Elliptic PDEs

Greenbaum, Anne; Greengard, Leslie; Mayo, Anita On the numerical solution of the biharmonic equation in the plane. Experimental mathematics: computational issues in nonlinear science (Los Alamos, NM, 1991). Phys. D 60 (1992), no. 14, 216225.

Greenbaum, A.; Greengard, L.; McFadden, G. B. Laplace's equation and the DirichletNeumann map in multiply connected domains. J. Comput. Phys. 105 (1993), no. 2, 267278.

Strain, John Fast spectrallyaccurate solution of variablecoefficient elliptic problems. Proc. Amer. Math. Soc. 122 (1994), no. 3, 843850.

McKenney, A.; Greengard, L.; Mayo, A. A fast Poisson solver for complex geometries. J. Comput. Phys. 118 (1995), no. 2, 348355.

Greengard, Leslie; Lee, JuneYub A direct adaptive Poisson solver of arbitrary order accuracy. J. Comput. Phys. 125 (1996), no. 2, 415424.

Cheng, Hongwei; Greengard, Leslie A method of images for the evaluation of electrostatic fields in systems of closely spaced conducting cylinders. SIAM J. Appl. Math. 58 (1998), no. 1, 122141.

Ethridge, Frank; Greengard, Leslie A new fastmultipole accelerated Poisson solver in two dimensions. SIAM J. Sci. Comput. 23 (2001), no. 3, 741760.

Nishimura, N. Fast multipole accelerated boundary integral equation
methods. Appl. Mech. Rev. vol 55 (2002), no. 4, 299324. (*)

Ying, Lexing; Biros, George; Zorin, Denis A highorder 3D boundary integral equation solver for elliptic PDEs in smooth domains. J. Comput. Phys. 219 (2006), no. 1, 247275.

Compression of Low Rank Matrices

Gu, Ming; Eisenstat, Stanley C. Efficient algorithms for computing a strong rankrevealing QR factorization. SIAM J. Sci. Comput. 17 (1996), no. 4, 848869.

Cheng, H.; Gimbutas, Z.; Martinsson, P. G.; Rokhlin, V. On the compression of low
rank matrices. SIAM J. Sci. Comput. 26 (2005), no. 4, 13891404 (*)

PerGunnar Martinsson, Vladimir Rokhlin, and Mark Tygert, "A randomized algorithm for the approximation of matrices," Technical Report 1361, Yale University, Department of Computer Science, June 2006.

Franco Woolfe, Edo Liberty, Vladimir Rokhlin, and Mark Tygert, "A fast randomized
algorithm for the approximation of matrices," Technical Report 1386, Yale University,
Department of Computer Science, July 2007.

Fast Direct Solver for BVPs for Elliptic PDEs

Martinsson, P. G.; Rokhlin, V. A fast direct solver for boundary integral equations
in two dimensions. J. Comput. Phys. 205 (2005), no. 1, 123. (*)

Martinsson, P. G.; Rokhlin, V. A fast direct solver for scattering problems involving elongated structures. J. Comput. Phys. 221 (2007), no. 1, 288302.

Fast Algorithms for TwoPoint Boundary Value Problems

Greengard, L.; Rokhlin, V. On the numerical solution of twopoint boundary value problems. Comm. Pure Appl. Math. 44 (1991), no. 4, 419452.

Starr, Page; Rokhlin, Vladimir On the numerical solution of twopoint boundary value problems. II. Comm. Pure Appl. Math. 47 (1994), no. 8, 11171159.

Lee, JuneYub; Greengard, Leslie A fast adaptive numerical method for stiff twopoint
boundary value problems. SIAM J. Sci. Comput. 18 (1997), no. 2, 403429. (*)

Fast Algorithms for the Heat Equation

Strain, John Fast adaptive methods for the freespace heat equation. SIAM J. Sci. Comput. 15 (1994), no. 1, 185206.

Greengard, Leslie; Strain, John A fast algorithm for the evaluation of heat potentials. Comm. Pure Appl. Math. 43 (1990), no. 8, 949963.

Greengard, Leslie; Lin, Patrick Spectral approximation of the freespace heat kernel. Appl. Comput. Harmon. Anal. 9 (2000), no. 1, 8397.

Veerapaneni S.K. and Biros G.
A fast highorder integral equation solver for the heat equation with moving boundaries in 1d,
(to appear) siam journal on scientific computing, 2007.

Fast Algorithms for the Wave Equation

Ergin, A. Arif; Shanker, Balasubramaniam; Michielssen, Eric Fast evaluation of threedimensional transient wave fields using diagonal translation operators. J. Comput. Phys. 146 (1998), no. 1, 157180.

Ergin AA, Shanker B, and Michielssen E, The planewave timedomain algorithm for the
fast analysis of transient wave phenomena, IEEE Antennas Propag. Mag. 41, 3952 (1999).

Ergin AA, Shanker B, and Michielssen E, Fast transient analysis of acoustic wave
scattering from rigid bodies using a twolevel plane wave time domain algorithm,
J. Acoust. Soc. Am. (1999) 106, 24052416.

Ergin AA, Shanker B, and Michielssen E, Fast analysis of transient acoustic wave
scattering from rigid bodies using a multilevel plane wave time domain algorithm,
J. Acoust. Soc. Am. (2000) 107, 11681178.

Michielssen, Eric; Ergin, Arif; Shanker, Balasubramaniam; Weile, Daniel The multilevel plane wave time domain algorithm and its applications to the rapid solution of electromagnetic scattering problems: a review. Mathematical and numerical aspects of wave propagation (Santiago de Compostela, 2000), 2433, SIAM, Philadelphia, PA, 2000.

Fast Algorithms for the Stokes Equation

Greengard, Leslie; Kropinski, Mary Catherine; Mayo, Anita Integral equation methods for Stokes flow and isotropic elasticity in the plane. J. Comput. Phys. 125 (1996), no. 2, 403414.

Greengard, Leslie; Kropinski, Mary Catherine An integral equation approach to the incompressible NavierStokes equations in two dimensions. SIAM J. Sci. Comput. 20 (1998), no. 1, 318336.

Biros, George; Ying, Lexing; Zorin, Denis A fast solver for the Stokes equations with distributed forces in complex geometries. J. Comput. Phys. 193 (2004), no. 1, 317348.

Greengard, Leslie; Kropinski, Mary Catherine Integral equation methods for Stokes
flow in doublyperiodic domains. J. Engrg. Math. 48 (2004), no. 2, 157170.

Fast Algorithms for the LippmannSchwinger equation

Chen, Yu A fast, direct algorithm for the LippmannSchwinger integral equation in two dimensions. Modeling and computation in optics and electromagnetics. Adv. Comput. Math. 16 (2002), no. 23, 175190.

Generalized Gaussian Quadrature and Sumofexponentials Approximation

Ma, J.; Rokhlin, V.; Wandzura, S. Generalized Gaussian quadrature rules for systems of arbitrary functions. SIAM J. Numer. Anal. 33 (1996), no. 3, 971996.

Cheng, H.; Rokhlin, V.; Yarvin, N. Nonlinear optimization, quadrature, and interpolation. Dedicated to John E. Dennis, Jr., on his 60th birthday. SIAM J. Optim. 9 (1999), no. 4, 901923.

Yarvin, N.; Rokhlin, V. Generalized Gaussian quadratures and singular value decompositions of integral operators. SIAM J. Sci. Comput. 20 (1998), no. 2, 699718

Beylkin, Gregory; Monz¨Žn, Lucas On approximation of functions by exponential sums. Appl. Comput. Harmon. Anal. 19 (2005), no. 1, 1748.

Beylkin, G.; Monz¨Žn, L. On generalized Gaussian quadratures for exponentials and their applications. Appl. Comput. Harmon. Anal. 12 (2002), no. 3, 332373.

Fast Algorithms for Nonreflecting Boundary Conditions

Alpert, Bradley; Greengard, Leslie; Hagstrom, Thomas Rapid evaluation of nonreflecting boundary kernels for timedomain wave propagation. SIAM J. Numer. Anal. 37 (2000), no. 4, 11381164.

Alpert, Bradley; Greengard, Leslie; Hagstrom, Thomas Nonreflecting boundary conditions for the timedependent wave equation. J. Comput. Phys. 180 (2002), no. 1, 270296.
Web Resources

Papers

Codes

Books
Supported in part by NSF