Overview of CS 615:
Numerical Methods for Partial Differential Equations

I will be teaching CS 615, Numerical Methods for Partial Differential Equations, in Spring 2003.  Ideally, I'd like to emphasize the interdisciplinary nature of Scientific Computation.  Specifically, I would like to consider  AlgorithmsError Bounds,  Programming Languages, and Programming Systems, and their influence on numerical approximations of PDEs.

I plan to cover the following material, roughly in this order:

• Algorithms for Finite Difference and Finite Element methods for elliptic and parabolic partial differential equations.
• Algorithms for the conjugate-gradient method and multigrid method for solving positive-definite systems of linear equations.
• Error bounds for Finite Difference and Finite Element methods for elliptic and parabolic partial differential equations.
• Error bounds for the conjugate-gradient method and multigrid method for solving positive-definite systems of linear equations.

I would like to have the class engage in a group project to implement nearly all the numerical methods that are introduced in the course.  I hope to do this at a high level, so that many of the algorithms can be programmed in as few lines of code as it takes to describe them on the blackboard.

We shalll use a high-level, mainly functional programming system to implement all this code.  I plan to use Scheme, a dialect of Lisp, as implemented in the Gambit-C Scheme system by Marc Feeley.  This system has useful extensions for high-performance numerical computing, including homogenous vectors of double-precision floating-point values, and a compiler that, in unsafe mode, can compile numerical code to run at the speed of equivalent C code.  I also plan to use the Meroon object system, designed and implemented by Christian Queinnec, which offers many features of CLOS, the Common Lisp Object System, including generic functions, multimethods, classes, etc.  (It is somewhat simplified from CLOS; for example, it offers only single inheritance (as in Java), not multiple inheritance (as in CLOS and C++). There is an interesting essay about how the use of multimethods and a more dynamic object-oriented system like you find in CLOS, Meroon, Dylan, etc., removes the need for the current craze of Design Patterns, which seem, from the dynamic language perspective, to be hacks to implement more general control and data structures than are found, e.g., in bare Java or C++.)  This object system has been efficiently integrated into Gambit-C.

Writing programs in Scheme is not hard; I prefer the book The Schematics of Computation by Manis and Little as an introduction.  The best book ever written about computer programming is Structure and Interpretation and Computer Programs, by Abelson, Sussman, and Sussman, and it uses Scheme to program its examples.  If you plan to take 615 in the spring I suggest that you look at one of these books and the documentation for Meroon and Gambit-C.  Since each student's grade will depend on his or her performance in the project, it is imperative that you learn how to program, either before or very near the beginning of the class.

I anticipate that in the group project there will be room for people with many types of abilities and interests.  Typically graduate students from Mathematics have implemented numerical algorithms in the class; CS-oriented students could work on projects in Programming Languages, Object-Oriented Design, etc.  The previous year's material has more CS-type options listed.

So the material covered in the lectures will be algorithms and error bounds; the material in the group project will be implementation and comparison.

Expectations: I expect everyone in the class to have the following minimal qualifications and abilities, if not at the beginning of the class, at least at the end:  use an object-oriented system to program numerical algorithms in Scheme; follow a closely argued series of inequalities leading to a useful error bound.  For the latter, any of CS 514/614, MA 504, MA 523, MA 544, MA 611, etc. would be helpful.

Preparation: If you want to practice with Scheme, Gambit, or Meroon before the beginning of the class, you can download and install Gambit and Meroon on your own machines (see the files and instructions at the links above), or you can use Gambit-C on the math department Suns.  The compiler is called gsc, the interpreter is gsi; the compiler with Meroon pre-installed is gsc++, and the interpreter with Meroon is gsi++.   Documentation for Gambit-C is available here, and documentation for Meroon is available here.