Title  Object Oriented Numerics  
Participant  Gerhard Zumbusch  
Key words  Object Oriented Design, Problem Solving Environments, Software Engineering  
Description  The goal for the development of our finite difference and sparse grid
codes is to be able to test and to verify different types of discretizations
on sparse grids and to tackle different types of partial differential equations.
Hence a flexible and modular design is a must. Techniques such as abstract
data types and object oriented programming provide such a flexibility.
However, they often lead to slow inefficient code due to an overuse of
design features.
For example, overloading the arithmetic operators `+' and `*' for vectors
in C++ usually is less efficient than proving directly a saxpy
operation for expressions of av + w
type. Performing tree traversal for the operations above is even slower.
Hence, splitting a large code into many small functions and loops may lead
to inefficiencies, which cannot be resolved by an optimizing compiler.
numerical vector
We have based our code on several fundamental abstractions, which are well separated both in functionality and in implementation. This guarantees that we do not loose efficiency in a substantial way due to this separation. We have identified the following building blocks.
gridgeometric description of an adaptively refined sparse grid and provides i/o, refinement and addressing, or e.g. a full grid for debugging purposesvectora large container for real numbers, including BLAS level 1data: Fortran compatible linear storage
class Vec { protected: real *r; int n; ... }; methods: Blas level 1 (with compiler inlining)
void Vec:: add(const Vec &a, const Vec &b) { assert((a.n==n)&&(b.n==n)); for (int i=0; i<n; i++) r[i] = a.r[i] + b.r[i]; } including bit (flag) vectors and short vectors for coordinates etc. fielda (solution) function on a grid. It provides a mapping between a grid and a vector and interprets the data as (collocated) scalar or vector fieldoperatorthe finite difference operators and operates on gridssolverdifferent iterative (Krylov) solvers, uses a (differential) operator: iterative solvers for linear problems,linear solver
void ConjGrad:: solve(const Vec &b, Vec &x) { assert(b.dim()==x.dim()); int n = x.dim(); Vec r(n), p(n), Ap(n); iter = 0; real beta, alpha, rtr, rtrold; op>apply(x, Ap); p.sub(b, Ap); r.copy(p); rtr = r.prod(r); while (rtr>tol) {
for eigenvalue problems,
and for nonlinear problems
mainputting the components together leads to a simple main program, which may look like this:calling sequence main
uchar dim = 2; SVec x0(dim), x1(dim); x0.set(1); x1.set(1); SpGrid grid(dim, x0, x1);
//create sparse grid
uint n = grid.nodes();
Bicgstab j;
cout<<j<<endl;
For the implementation of such finite difference methods, we have discussed
some software concepts. This included an object oriented layout of the
basic ingredients of such a code for a powerfull, highly flexible and modular
and still efficient code development.


Bibliography 


Related projects 


In cooperation with 
