School of Mathematics

Automatic Generation and Differentiation of Partial Differential Equation Solvers with Index-Free Scripts

Jitse Niesen. Automatic Generation and Differentiation of Partial Differential Equation Solvers with Index-Free Scripts.
Master's thesis, Department of Computer Science, University of Twente, the Netherlands, 1999.
Download scanned version as PDF file (34M).

Abstract

In this thesis, a system for the automatic generation of a numerical solver for partial differential equations using finite differences is developed. Due to the high performance demands in scientific computing, the efficiency of the generated code should be comparable to hand-written code. The input consists of a high-level specification of the difference scheme. Only explicit schemes are considered. Besides generating the code for the solver, the system can also automatically differentiate the difference scheme for eg.~optimisation. This automatic differentiation should take place at the script level instead of at the source-code level to retain of the general view.

The input, specifying the difference scheme, is contained in a script, which is basically a sequence of assignments. However, automatic differentiation of assignments with indexed expressions leads to the difficult problem of symbolically contracting tensors containing Kronecker deltas with non-trivial index expressions. To circumvent this problem, the script are required to be index-free. Stencil operators are provided to enable the expression of difference schemes in index-free scripts. The notion of repeating a certain action is enclosed in a special stencil operator called the iterator.

Scripts are implemented in the computer algebra system Reduce as a so-called rtype. For the differentiation of these scripts, extensive use is made of Reduce transformation rules. Except the ordinary forward mode of differentiation, also the sometimes favourable reverse method is implemented. Furthermore some possibilities for optimising scripts are developed. Finally, scripts can be translated in the programming language Fortran 90 and subsequently executed.

The use of this implementation is illustrated with some examples, which also serve as tests. It appears that the resulting code is correct, but a factor five slower than hand-written code. The main reason for this is the overhead caused by consecutive Fortran 90 array operators. This can be solved inside the compiler; another possibility is to synthesise the array operators. Finally, the reverse method of differentiation is considerably faster than the forward mode in optimisation problems, in good accordance with the theory.