Parallel Spectral Numerical Methods/Overview
We start by taking a quick look at finite-precision arithmetic. We then discuss how to solve ordinary differential equations (ODE) and partial differential equations (PDE) using the technique of separation of variables. We then introduce numerical time-stepping schemes that can be used to solve ODEs and PDEs. Next we introduce pseudo spectral methods by giving an overview of the discrete Fourier Transform (DFT) and the Fast Fourier Transform (FFT) algorithm that is used to quickly calculate the DFT. Finally we will combine all of this to solve a couple of different PDEs first in a serial setting and then in a parallel setting. The programs will use Matlab and Fortran. A Python implementation of some of the Matlab programs is also provided.
We assume that the reader has introductory programming experience, for example using C, C++, Fortran, Matlab, Octave, Python or equivalent. Since detailed programming examples have been provided, we do not expect a significant programming background, but hope the required knowledge will be acquired as one works through the examples. We also assume the level of mathematical maturity obtained in a demanding calculus course, for example at the level of Courant and John's Introduction to Calculus and Analysis. A course in differential equations would also be helpful, but for many scientists or engineers, their fields of interest will provide numerous examples of these. More programming experience or mathematical background will make the material easier to understand. Checking whether the simulations are correct may also be easier for those with knowledge of the behavior of solutions of the partial differential equations that are being approximated, however we have tried to choose representative differential equations that will make it easy for one to use the programs and then adapt them to the use being considered.
Using the Programs
The programs have been tested on several different computers. The programs are located in program directories which correspond to the chapter in which the programs first appear. While they are not explicitly hyperlinked, one can find their locations either by reading the LaTeX source code or by searching the appropriate directory.
The Matlab programs are guaranteed to work with Matlab R2011b, but should also work with other recent versions of Matlab. They should also be easy to modify so that they work with [] which is freely available at www.gnu.org/software/octave/.
Since Matlab requires a licence, for those not wishing to use Octave, we have also included Python versions of some of the Matlab programs. These programs have been tested in Python 2.7 (which can be obtained from http://python.org/), they also require Matlplotlib (version 1.10, which can be obtained from http://matplotlib.sourceforge.net/index.html), Mayavi (http://github.enthought.com/mayavi/mayavi/index.html) and numpy (http://numpy.scipy.org/). These programs have been tested primarily with the Enthought Python distribution.
The Fortran programs have been tested primarily with the GCC 4.6.2 compiler suite, although they should work with most other recent compilers. If using an implementation of MPI that depends on a particular compiler, we suggest also using the GCC compiler. We expect that the programs should work with minor modifications with other compilers, but cannot guarantee this. For simplicity and to allow checking of program correctness, we have chosen to use a low compiler optimization level. We encourage users to increase the compiler optimization level and compiler ags once they have checked that the programs are working correctly on their systems. FFTW, a free Fast Fourier transform library, is also required to run the programs. This can be downloaded from http://fftw.org/. The MPI programs make use of the library 2DECOMP&FFT which can be downloaded from http://www.2decomp.org. Finally, the last part of the tutorial requires the use of the free and open source VisIt parallel visualization program, which can be obtained from https://wci.llnl.gov/codes/visit/home.html. If you expect to do large parallel simulations (A guide for large at present is 20% of the system for systems larger than 10,000 cores), it may be worth learning the most efficient system settings for performing output and for parallelization. We do not address this in this tutorial, but suggest that you contact your computing center for suggestions.
Course Outlines / Assessment Rubric
The material in these notes can form the basis of a short course. The most important portions are chapters 1 to 11. A selection can then be made from chapters 12, 13 and 14. A selection of the problems can be used to assess student learning. Note that problems in chapters 8. 12, 13 and 14 can develop into extensive research projects, so only a sample of these should be given to any students if they only have a limited time to solve them. A student will have successfully understood the material if they can run the example Matlab/Python, serial Fortran, OpenMP Fortran and MPI Fortran programs, and can also modify them to solve related problems. Successful completion of problems which test these abilities will be enough to indicate that students have understood the fundamental concepts.
- http://www.mathworks.com/products/matlab/index.html - if this is not available, we suggest modifying the Matlab programs to use Octave which can be freely downloaded at http://www.gnu.org/ software/octave/.
- Courant and John (1998).
- Courant and John (1999), .
Courant, R.; John, F. (1998). Introduction to Calculus and Analysis. I. Springer.
Courant, R.; John, F. (1999). Introduction to Calculus and Analysis. II. Springer.