Overview of CS 615:
Numerical Methods for Partial Differential Equations
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.
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 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).
The emphasis in the areas of object-oriented design, parallel programming
and computational geometry will be on functionality, not efficiency.
The emphasis of work in programming languages, system hacking, parallel
programming, and algorithm comparison will be on efficiency. (Yes, I know
parallel programming is in both lists.)
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.