Math 707-001 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 state-of-the-art analysis-based 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. 2-97), 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
-
Krylov-space-based 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 Two-Point 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 Lippmann-Schwinger equation
-
Generalized Gaussian Quadrature and Sum-of-exponentials 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, 325--348. (*)
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, 669--686.
-
Rokhlin, V. Rapid solution of integral equations of scattering theory in two dimensions. J. Comput. Phys. 86 (1990), no. 2, 414--439. (*)
-
Nabors, K.; Korsmeyer, F. T.; Leighton, F. T.; White, J. Preconditioned, adaptive,
multipole-accelerated iterative methods for three-dimensional first-kind integral
equations of potential theory. Iterative methods in numerical linear algebra (Copper
Mountain Resort, CO, 1992). SIAM J. Sci. Comput. 15 (1994), no. 3, 713--735. (*)
-
Rokhlin, V. Diagonal forms of translation operators for the Helmholtz
equation in three dimensions. Appl. Comput. Harmon. Anal. 1 (1993),
no. 1, 82--93.
-
Greengard, Leslie; Rokhlin, Vladimir A new version of the fast multipole method for
the Laplace equation in three dimensions. Acta numerica, 1997, 229--269, 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, 1804--1826 (*)
-
Cheng, H.; Greengard, L.; Rokhlin, V. A fast adaptive multipole algorithm in three dimensions. J. Comput. Phys. 155 (1999), no. 2, 468--498.
-
Yarvin, Norman; Rokhlin, Vladimir An improved fast multipole algorithm for potential fields on the line. SIAM J. Numer. Anal. 36 (1999), no. 2, 629--666
-
Sun, Xiaobai; Pitsianis, Nikos P. A matrix version of the fast multipole method.
SIAM Rev. 43 (2001), no. 2, 289--300 (*)
-
Gimbutas, Zydrunas; Rokhlin, Vladimir A generalized fast multipole method for nonoscillatory kernels. SIAM J. Sci. Comput. 24 (2002), no. 3, 796--817
-
Ying, Lexing; Biros, George; Zorin, Denis A kernel-independent adaptive fast multipole algorithm in two and three dimensions. J. Comput. Phys. 196 (2004), no. 2, 591--626. (*)
-
The Fast Gauss Transform
-
Greengard, Leslie; Strain, John The fast Gauss transform. SIAM
J. Sci. Statist. Comput. 12 (1991), no. 1, 79--94. (*)
-
Strain, John The fast Gauss transform with variable scales. SIAM J. Sci. Statist. Comput. 12 (1991), no. 5, 1131--1139.
-
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, 575--584.
-
Andersson, Fredrik; Beylkin, Gregory The fast Gauss transform with complex parameters. J. Comput. Phys. 203 (2005), no. 1, 274--286.
-
Fast Fourier Transforms for Nonequispaced Data
-
Dutt, A.; Rokhlin, V. Fast Fourier transforms for nonequispaced data. SIAM J. Sci. Comput. 14 (1993), no. 6, 1368--1393.
(pdf)
-
Dutt, A.; Rokhlin, V. Fast Fourier transforms for nonequispaced data. II. Appl. Comput. Harmon. Anal. 2 (1995), no. 1, 85--100.
-
Greengard, Leslie; Lee, June-Yub Accelerating the nonuniform fast Fourier transform.
SIAM Rev. 46 (2004), no. 3, 443--454 (*)
-
Lee, June-Yub; Greengard, Leslie The type 3 nonuniform FFT and its applications. J. Comput. Phys. 206 (2005), no. 1, 1--5.
-
General Fast Summations/Transforms
-
Strain, John Fast potential theory. II. Layer potentials and discrete sums. J. Comput. Phys. 99 (1992), no. 2, 251--270.
-
Gu, Ming; Eisenstat, Stanley C. A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem. SIAM J. Matrix Anal. Appl. 16 (1995), no. 1, 172--191.
-
Rokhlin, Vladimir and Mark Tygert, "Fast algorithms for spherical harmonic expansions," SIAM Journal on Scientific Computing, 27 (6): 1903-1928, 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 analysis-based fast transforms" Technical Report 1384, Yale University, Department of Computer Science, August 2007.
-
Krylov-space-based 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: 0-89871-389-7
-
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: 0-521-58391-8
-
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: 0-486-68889-5
-
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, 395--403.
-
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, 47--74.
-
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. 1-4, 216--225.
-
Greenbaum, A.; Greengard, L.; McFadden, G. B. Laplace's equation and the Dirichlet-Neumann map in multiply connected domains. J. Comput. Phys. 105 (1993), no. 2, 267--278.
-
Strain, John Fast spectrally-accurate solution of variable-coefficient elliptic problems. Proc. Amer. Math. Soc. 122 (1994), no. 3, 843--850.
-
McKenney, A.; Greengard, L.; Mayo, A. A fast Poisson solver for complex geometries. J. Comput. Phys. 118 (1995), no. 2, 348--355.
-
Greengard, Leslie; Lee, June-Yub A direct adaptive Poisson solver of arbitrary order accuracy. J. Comput. Phys. 125 (1996), no. 2, 415--424.
-
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, 122--141.
-
Ethridge, Frank; Greengard, Leslie A new fast-multipole accelerated Poisson solver in two dimensions. SIAM J. Sci. Comput. 23 (2001), no. 3, 741--760.
-
Nishimura, N. Fast multipole accelerated boundary integral equation
methods. Appl. Mech. Rev. vol 55 (2002), no. 4, 299--324. (*)
-
Ying, Lexing; Biros, George; Zorin, Denis A high-order 3D boundary integral equation solver for elliptic PDEs in smooth domains. J. Comput. Phys. 219 (2006), no. 1, 247--275.
-
Compression of Low Rank Matrices
-
Gu, Ming; Eisenstat, Stanley C. Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM J. Sci. Comput. 17 (1996), no. 4, 848--869.
-
Cheng, H.; Gimbutas, Z.; Martinsson, P. G.; Rokhlin, V. On the compression of low
rank matrices. SIAM J. Sci. Comput. 26 (2005), no. 4, 1389--1404 (*)
-
Per-Gunnar 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, 1--23. (*)
-
Martinsson, P. G.; Rokhlin, V. A fast direct solver for scattering problems involving elongated structures. J. Comput. Phys. 221 (2007), no. 1, 288--302.
-
Fast Algorithms for Two-Point Boundary Value Problems
-
Greengard, L.; Rokhlin, V. On the numerical solution of two-point boundary value problems. Comm. Pure Appl. Math. 44 (1991), no. 4, 419--452.
-
Starr, Page; Rokhlin, Vladimir On the numerical solution of two-point boundary value problems. II. Comm. Pure Appl. Math. 47 (1994), no. 8, 1117--1159.
-
Lee, June-Yub; Greengard, Leslie A fast adaptive numerical method for stiff two-point
boundary value problems. SIAM J. Sci. Comput. 18 (1997), no. 2, 403--429. (*)
-
Fast Algorithms for the Heat Equation
-
Strain, John Fast adaptive methods for the free-space heat equation. SIAM J. Sci. Comput. 15 (1994), no. 1, 185--206.
-
Greengard, Leslie; Strain, John A fast algorithm for the evaluation of heat potentials. Comm. Pure Appl. Math. 43 (1990), no. 8, 949--963.
-
Greengard, Leslie; Lin, Patrick Spectral approximation of the free-space heat kernel. Appl. Comput. Harmon. Anal. 9 (2000), no. 1, 83--97.
-
Veerapaneni S.K. and Biros G.
A fast high-order 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 three-dimensional transient wave fields using diagonal translation operators. J. Comput. Phys. 146 (1998), no. 1, 157--180.
-
Ergin AA, Shanker B, and Michielssen E, The plane-wave time-domain algorithm for the
fast analysis of transient wave phenomena, IEEE Antennas Propag. Mag. 41, 39-52 (1999).
-
Ergin AA, Shanker B, and Michielssen E, Fast transient analysis of acoustic wave
scattering from rigid bodies using a two-level plane wave time domain algorithm,
J. Acoust. Soc. Am. (1999) 106, 2405-2416.
-
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, 1168-1178.
-
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), 24--33, 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, 403--414.
-
Greengard, Leslie; Kropinski, Mary Catherine An integral equation approach to the incompressible Navier-Stokes equations in two dimensions. SIAM J. Sci. Comput. 20 (1998), no. 1, 318--336.
-
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, 317--348.
-
Greengard, Leslie; Kropinski, Mary Catherine Integral equation methods for Stokes
flow in doubly-periodic domains. J. Engrg. Math. 48 (2004), no. 2, 157--170.
-
Fast Algorithms for the Lippmann-Schwinger equation
-
Chen, Yu A fast, direct algorithm for the Lippmann-Schwinger integral equation in two dimensions. Modeling and computation in optics and electromagnetics. Adv. Comput. Math. 16 (2002), no. 2-3, 175--190.
-
Generalized Gaussian Quadrature and Sum-of-exponentials Approximation
-
Ma, J.; Rokhlin, V.; Wandzura, S. Generalized Gaussian quadrature rules for systems of arbitrary functions. SIAM J. Numer. Anal. 33 (1996), no. 3, 971--996.
-
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, 901--923.
-
Yarvin, N.; Rokhlin, V. Generalized Gaussian quadratures and singular value decompositions of integral operators. SIAM J. Sci. Comput. 20 (1998), no. 2, 699--718
-
Beylkin, Gregory; Monz¨Žn, Lucas On approximation of functions by exponential sums. Appl. Comput. Harmon. Anal. 19 (2005), no. 1, 17--48.
-
Beylkin, G.; Monz¨Žn, L. On generalized Gaussian quadratures for exponentials and their applications. Appl. Comput. Harmon. Anal. 12 (2002), no. 3, 332--373.
-
Fast Algorithms for Nonreflecting Boundary Conditions
-
Alpert, Bradley; Greengard, Leslie; Hagstrom, Thomas Rapid evaluation of nonreflecting boundary kernels for time-domain wave propagation. SIAM J. Numer. Anal. 37 (2000), no. 4, 1138--1164.
-
Alpert, Bradley; Greengard, Leslie; Hagstrom, Thomas Nonreflecting boundary conditions for the time-dependent wave equation. J. Comput. Phys. 180 (2002), no. 1, 270--296.
Web Resources
-
Papers
-
Codes
-
Books
Supported in part by NSF