Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Many physics and engineering problems can be reduced to solving a Poisson (or Helmholtz) problem, with appropriate boundary conditions. Numerical methods have been developed, such as finite difference schemes, which reduce the continuous partial differential equation to solving a matrix equation. Using standard Gaussian Elimination the corresponding matrix problem can be solved in O(N^3) time where N is the number of grid points used to discretize the problem.

We introduce a numerical method which solves the matrix problem, in O(N log(N)) time. The method is based on a change of basis from the Standard basis to the discrete Fourier basis (or sine or cosine basis), which costs O(N\log(N)) time. In the appropriate basis the linear operator is diagonalized and can be solved in O(N) time. Then the solution vector in the discrete Fourier basis (or sine or cosine basis) can then be transformed back to the Standard basis in O(N\log(N)) time.