Math 707-001 Special Topics: Fast Numerical Algorithms

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:

• A Short Course on Fast Multipole Methods by Rick Beatson and Leslie Greengard

Topics will be selected from the list below.

1. Fast Multipole Methods (*)

2. The Fast Gauss Transform

3. Fast Fourier Transforms for Nonequispaced Data (*)

4. General Fast Summations/Transforms

5. Krylov-space-based Iterative Solvers: GMRES and Conjugate Gradient (*)

6. Introduction to Integral Equations (*)

7. Introduction to Potential Theory (*)

8. Fast Algorithms for Elliptic PDEs (*)

9. Compression of Low Rank Matrices

10. Fast Direct Solver for BVPs for Elliptic PDEs

11. Fast Algorithms for Two-Point Boundary Value Problems

12. Fast Algorithms for the Heat Equation

13. Fast Algorithms for the Wave Equation

14. Fast Algorithms for the Stokes Equation

15. Fast Algorithms for the Lippmann-Schwinger equation

16. Generalized Gaussian Quadrature and Sum-of-exponentials Approximation

17. Fast Algorithms for Nonreflecting Boundary Conditions

Main resources and suggested readings:

1. 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. (*)



2. 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.



3. 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.



4. 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.



5. 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



6. 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



7. 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.



8. 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.



9. 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.



10. 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.



11. 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. (*)



12. 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.



13. 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.



14. 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.



15. 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.



16. 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.



17. 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

1. Papers

   • Many of the above papers can be found and downloaded from MathSciNet.
   • If the paper is not downloadable from the MathSciNet, then you may try to download it from the following personal homepages:
     
     Vladimir Rokhlin | Leslie Greengard | Bradley Alpert | Gregory Beylkin | Ming Gu | John Strain | Eric Michielssen | Jacob White | Yu Chen | Jingfang Huang | Gunnar Martinsson | Mark Tygert | George Biros | Lexing Ying |



2. Codes

   • Netlib



3. Books

   • Handbook of Mathematical Functions by Abramowitz and Stegun
   • Numerical Recipes in Fortran 77

Supported in part by NSF