I will be teaching CS 615, Numerical Methods for Partial Differential Equations, in Spring 2000.  I hope to emphasize the interdisciplinary nature of Scientific Computation.  Specifically, I would like to consider  Programming Languages, Programming Systems, Algorithms, and Error Bounds 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.

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 within 50% of the speed of equivalent C code.  I also plan to use the Meroon object system, 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.

I anticipate that in the group project there will be room for people with many types of abilities and interests.  Specifically, I see the following areas for contributions:

• Programming Languages: Implement inlining (beta-reduction), partial evaluation, analysis and elimination of temporary structures, partial evaluation  with or without the presence of side effects, Continuation-Passing Style transformations, type inference (soft typing), etc.  References: CS 565; Essentials of Programming Languages, by Friedman, Wand, and Haynes; the chapter on functional programming languages in Appel's Modern Compiler Design in Java, recent papers from the Programming Language Theory group at Rice on soft typing systems.
• Object oriented design: Design classes, meta-classes, generic functions, and multimethods of an object hierarchy for Linear Algebra, beginning with an abstraction level of Linear Spaces and Linear Operators (i.e., above the level of matrices and vectors).  Reference: I don't really know; stuff on CLOS (e.g., The Art of the Metaobject Protocol or Object Oriented Programming in Common Lisp : A Programmers Guide to the Common Lisp Object System  by Keene), some knowledge of existing matrix C++ classes or Veldhuizen's  C++ template library.
• Parallel Programming: Scientific computation often benefits from parallel programming.  In this area, one could implement parallel versions of various algorithms; add an MPI or PVM interface to Gambit (easy); implement multiple threads on shared multiprocessors for Gambit (harder, but the hooks are there; distributed memory allocation is easy, for garbage collection it would probably be easiest to use the existing mark-and-copy gc routines after thread synchronization). References: Books on parallel processing (like the one by Grama, Kumar, et al.); Queinnec's book Lisp in Small Pieces; Wilson's book on the web about garbage collection.
• Low-level system hacking: The global register allocator for the development version of gcc uses an algorithm that is quadratic in the number of register temporaries; rewrite it to be linear or N log N in the number of temporaries (a description of how to do this is available).  Gcc's register allocator cannot deal well with certain constraints on register allocation on the Alpha for IEEE floating-point code; fix the register allocator.  References: CS 502; the gcc cvs development tree and mailing lists; Muchnick's book on Advanced Compiler Design and Implementation.
• Computational Geometry: Write object-oriented system to triangulate polygonal domains; implement code to refine triangulations, project functions from the fine triangulations to coarse triangulations and injections from coarse to fine; extend it to domains with smooth boundaries and parametric elements on the boundary.  If you really want to be brave, do this in three dimensions.  Reference: Ridgway Scott and Sue Brenner's book on the finite element method, Doug Arnold's recent papers on finite element methods in three dimensions for the modelling of relativistic gravity waves.
• Algorithm comparison: Compare finite difference and finite element algorithms along the following lines: complexity of implementation; run-time versus accuracy.  Compare high-order with low-order schemes---how much accuracy is necessary, and how much CPU time is required to achieve that accuracy for various methods.
• Error bounds: Provide error bounds for methods or problems not covered in class (e.g., elliptic problems with large first-order terms; problems that arise in mathematical finance; problems with funny boundary conditions).

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

Note: This is just a list of possible topics for people to work on for the group project.  It is inconceivable that all of these projects will be completed, or even started, next semester.  It is also inconceivable that any one student will contribute in all, or even most, areas.

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.  So if you're not interested in one of the subprojects listed above, you can restrict your activities in the project to programming the algorithms given in class.

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++.  Make sure that /usr/local/bin in in your path, and /usr/local/lib is in your LD_LIBRARY_PATH.  Documentation for Gambit-C is available here, and documentation for Meroon is available here.