Ganesh Swami

One of the many things I learnt from my nonlinear physics project is the pseudospectral method. I’m going to try explaining this method the way I understand it.

Any function can be expressed as an infinite sum of the set of basis functions:

For the purpose of an example, if we take the polynomial basis of order 2, then the function can be approximated as

The coefficients can be solved for by building a system of equations. The three unknowns require three points on the interval where we know the exact value of the function. Let these three points be x0, x1 and x2 and the value of the function at these points be b0, b1 and b3.

The system of equations is now,

written compactly as

The system can be solved by inverting the matrix A, which is of complexity . The function p(x) is an interpolating polynomial in the interval of interest. As you can see, using a higher order polynomial quickly becomes prohibitively expensive.

Instead of picking the polynomial basis, you can pick any other basis. The Chebyshev basis is commonly used. A friend of mine picked the Fourier-Bessel basis. Depends on the application.

Fourier basis

The Fourier basis is fundamental to linear systems theory. Linear operators become diagonal in the Fourier basis. This fact comes handy in numerical schemes such as exponential integrators, where you’ll have to take the exponential of a matrix.

The second advantage falls out of the uncertainty principle. Increasing the number of modes in the Fourier domain is equivalent to shrinking the spacing between steps in the space domain. This leads to an exponential convergence in the number of points required as opposed to the usual polynomial convergence with finite differences.

The third key point in the use of the Fourier basis is that the FFT lets us do the equivalent of a matrix inversion in . This is very fast.

Summary

In summary, three random facts come together to form a beautiful theory:

• The FFT is much faster than a matrix inversion.
• Linear operators are diagonal in the Fourier basis.
• Exponential convergence of spectral methods.

Hope you enjoyed reading this post as much as I enjoyed writing it.

Possibly related:

• Statistical and Stochastic
• Fitting data with Python
• Nonlinear Physics
• Amazon Recommendations
• Classic Math Papers

This entry was posted on Sunday, April 22nd, 2007 at 12:41 pm and is filed under Physics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.