SAGA - Scientific Computing with Algebraic and Generative Abstractions
Coordinate-Free Numerics
Coordinate-free numerics is the use of coordinate-free mathematical abstractions
in the numerical solution of problems, typically partial differential equations.
It turns out that the coordinate-free formulations are much
better software artefacts than the standard approaches in numerical and applied mathematics.
Coordinate-free software is more modular and more adaptable
to changes in problem requirements.
The approach has been shown to be robust
(meaning only small, contained parts of the code needs to be modified)
for
changes in coordinate system (obviously),
changes in numerical methods (FDM and FVM),
changes in the partial differential equations themselves (e.g., from elastic to poro-elastic wave equation), and
parallelisation of code.
The Sophus software library
Sophus is a software library
carefully designed to mimic the abstract structure of the
mathematics of partial differential equations, as used in the discription of many natural and industrial phenomena. Its apparatus supports coordinate free numerics
in the formulation and development of solvers to problems.
By requiring strict adherence to specified interfaces, we
have been able to achieve that different implementations of the same mathematical
concepts are basically interchangeable.
The Sophus library components can be
presented through different layers of abstractions.
- Application layer: solvers for PDEs such as a seismic simulator,
SeisMod,
or a coating problem.
- Tensor layer: handles coordinate systems, matrices and vectors and
general differentiation operators.
- Scalar field layer: numerical discretisations such as finite
differences and finite elements with partial derivatives.
- Mesh layer: implements grids for sequential and parallel HPC
machines.
The interchangeability of modules within a layer allows software
developers to experiment with different solution strategies and HPC
architectures without the need for extensive reprogramming. For
example, the change from a sequential to a parallel version of a seismic
simulator does not involve any reprogramming of the rest of the solver
application.
Currently the Sophus library is implemented using C++.
Experience using SAGA methodologies compared to
traditional methodologies
The main industrial relevance of SAGA is the investigation and promotion of
more effective development techniques for problem specific modelling. The
increase in modelling productivity is expected to come from improved
program structure, which should result in smaller source code and more
self-contained sections of the code, thus significantly reducing the size of
the code that has to be modified when a (slightly)
different model is needed. Software costs typically
increase much more than linearly in code size due to longer development times
and higher maintenance costs.
To exemplify the differences between SAGA software methodologies and
traditional software methodologies we will briefly present a computational fluid dynamics
case study. This involved developing a solver for a coating problem in
axio-symmetric form, with the use of the finite element method (FEM) as
numerical discretisation technique.
The case study revealed a cultural gap between the traditional thinking,
where everything is made explicit when approaching a computational
modelling problem, and the thinking needed for a more algebraic approach,
where the focus is on the abstract mathematical level. This mathematical
level is directly supported by the Sophus library
abstractions.
Traditional development of solver
Traditionally development of a computational model starts by looking
at the main ideas of the
mathematical solution of the problem, glossing over details that
are technically involved but contribute little to the understanding of the
problem.
For simplicity, a Cartesian coordinate system is used for
this part.
Then the development focuses on the discretisation technique,
in this case the FEM, and makes a simplified overview of the underlying
mathematics of the technique.
Further development
of the solver is now closely linked to its realisation using the FEM
technique.
Technical details are then added at the discrete level, but
still within the framework of the Cartesian coordinate system. As the
study approaches the end, it is expanded with various material such as
the use of axio-symmetric coordinate system, which has a marked influence
on the way the operators are defined, or semi-implicit time stepping
to increase stability and convergence.
These pieces are studied independently of each other, where
important details, such as how to do the integration of the scalar fields,
are not looked upon in depth.
The implementor of the solver now has to redo
the development, tracing the added features through the discretised
presentation, finally ending with a concrete level algorithm that takes all
the presented information into account.
This development strategy can be summarised in the figure below, where we
see that parallelisation of the code involves further modification of the
whole system.
The upper level represents reasoning at the coordinate free, continuous
mathematics level. This level is abandoned as soon as the solver strategy
has been formulated. The mental gap occurs when taking into account coordinate
systems and discretisations.
All further refinement now takes place on the concrete level, using
machine oriented primitives directly.
SAGA oriented development of solver
Using the SAGA methodologies the development of the solver is taken as far
as possible on the abstract level.
This means that integration schemes for variational formulations have to
be discussed quite early, and modifications of the strategy due to
semi-implicit time-stepping will be handled at a coordinate free level.
Choice of coordinate systems involves selection of the appropriate tensor
module from the library. If an axio-symmetric version is not present it will have to be developed. This development is
independent of the rest of the solver, and a new tensor module typically
involves 1000-5000 lines of code.
The introduction of discretisation technique is again an orthogonal issue.
If an FEM implementation is not part of the library, an independent
development of such a module has to take place. A new discretisation
technique typically involves a library module containing 1000-5000 lines of code.
This development strategy can be summarised in the figure below, where we
see that parallelisation of the solver is also a matter of choice of library
modules.
Here the development at the abstract level also includes writing the program
code. This is possible since we match the mathematical
concepts with software abstractions from the Sophus library. The library
modules then bridge the gap down to the machine
level. If a desired module is missing from
the library, it is developed and coded independently of the rest of the solver
application.
Comparing the development methodologies
Comparing traditional numerical software development
with the SAGA software methodology we
see that the former requires us to be involved in the whole code for the
system. This may be as much as 20000 lines, representing a large
intellectual effort in itself. Developers knowledgeable in the area will
normally have access to library routines, but often these will have to
revisited when a new solver application is developed.
The SAGA approach focuses on the abstract mathematical development, and a
solver at this level typically remains at 2000 lines of code, even when all
technical details are exposed.
We may summarise this difference in the following diagram.
The lines of code have been added to indicate the size of the code one
needs to worry about at different key stages. We have also included the
cost of writing a missing library module in the transition to a working
program on the right.
We see here that the amount of code one needs to be concerned with during a
development process may decrease to about a tenth of the traditional code
size when using algebraic software methodologies. This represents a
tremendous saving in software development costs, and a dramatic increase
in flexibility to test out new solver schemes.
Crucial to this improvement is the use of a library of interchangeable
software modules carefully tuned to match the abstract mathematical
concepts. The abstractions also allow switching between sequential and
parallel HPC versions of the solver without the need for reanalysing or
rewriting the software.
These pages last updated June 2005
©2005 Magne Haveraaen, University of Bergen, Norway.
SAGA contact address.
Main SAGA WWW page.