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


Prerequisites:


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

(suggested readings are marked with * sign)
  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



Web Resources

  1. Papers


  2. Codes


  3. Books



Supported in part by NSF