An Object-oriented Approach to Construct

PDE Solvers

Krister Åhlander1
Department of Scientific Computing
Uppsala University
Uppsala, Sweden
krister@tdb.uu.se

1996 05 10

Abstract.
An object-oriented analysis and design is presented, for a framework in
which PDE solvers (programs that numerically solves partial
differential equations) may be composed from existing components.
The motivation for this work is that object-oriented technology is more
robust to changes than traditional techniques are. The PDE solving
system has been implemented in a one-dimensional pilot
implementation, which shows that the framework is expressive,
flexible and extendible. Through an interface to an object-oriented
database on top of the classes, it is shown that PDE solvers can be
constructed and changed interactively.

Keywords: scientific computing, object-oriented, PDE

1. This work was supported by a grant from TFR, the Swedish Research Council for
Engineering Sciences.
2
 Contents

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
The Cogito Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Motivation for the Object-oriented Approach . . . . . . . . . . . . 7

The Problem of Change . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Advantages with Object-oriented Techniques . . . . . . . . . . 8

The Object-oriented PDE Solving System . . . . . . . . . . . . . . . 10

Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Key Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Discussion about Alternative Solutions . . . . . . . . . . . . . . . 17
Comments on the Different OMT Models . . . . . . . . . . . . . 20
System Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Refining the Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Evolution of the Pilot Implementation . . . . . . . . . . . . . . . . 25
Example: Main Program . . . . . . . . . . . . . . . . . . . . . . . . . . 28
CogitoWorkBench . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Is the System Robust? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Conclusions and Future Research . . . . . . . . . . . . . . . . . . . . . . 36

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Appendix A Brief Introduction to Scientific Computing . . . 42

Appendix B Brief Introduction to Objects . . . . . . . . . . . . . . . 46

Appendix C Brief Summary of OMT . . . . . . . . . . . . . . . . . . . 48

3
4
1 Introduction
Time-dependent partial differential equations, PDE:s, model many important
processes in different fields of science and engineering. In order to solve
these equations on a computer, we need to develop a program that efficiently
performs the necessary calculations. In this report, we present an object-ori-
ented (OO) approach to the construction of PDE solvers. In particular, we
stress the program’s ability to adapt to changes, i.e. the ease with which the
program can be modified. All interesting programs will have to evolve, and it
is important that necessary modifications can be made easily. Because we re-
gard these aspects as essential, we have followed an object-oriented method-
ology1 in order to develop the design. Compared with traditional design
methodologies, OO methodologies yield programs that are easier to change.
The major result of this work is an OO analysis and design for a frame-
work where a PDE solver can easily be constructed in a flexible way. We
have put special effort into making the framework extendible, which means
that it is not limited to certain PDE problems or special numerical methods.
In order to demonstrate its usefulness we use this design to implement a
framework for PDE solvers which solve problems in one dimension (even if
the design is intended for more complex problems). A number of compo-
nents are included in the framework, such as different problems and different
solution methods, and we can within this pilot implementation very easily
construct and in particular modify a PDE solver, issues that are normally dif-
ficult when the program is constructed with traditional methodologies.
Furthermore, it is possible to equip the framework with an OO database,
which makes it possible to build and experiment with a PDE solver interac-
tively.
The conclusions are that the OO approach yields a flexible and extendible
system, in which it is possible to construct PDE solvers with little coding.
This system would be beneficial both to users who basically want nothing
but to solve a PDE by means of existing methods, and to users more interest-
ed in developing new numerical methods rapidly. We would also like to point
out that even if our design is intended for and implemented as a framework,
it is also relevant when a specific PDE solver (solving a specific problem
with a specific method) is to be constructed, since we would have the same
advantages with respect to future changes.
The layout of this report is as follows. Below, we present the Cogito
project, which this work is a part of. We also compare with related research.
In Chapter 2, we motivate our work by showing an example where the tradi-
tional approach fails to yield a program that is flexible. The most important
part of this report comes in Chapter 3, where the whole process of develop-

1. We have basically followed OMT, object modelling technique [25].

5
 ing the OO PDE solving framework is sketched. The results are assembled in
Chapter 4. The process as well as the results are discussed in Chapter 5, and
Chapter 6 concludes the thesis.

1.1 The Cogito Project

The Cogito project’s overall goal is to develop tools which make it easier to
develop programs on high-performance computers [33]. The focus is on pro-
grams that numerically solve time-dependent partial differential equations,
since this is an important subfield that requires powerful computers. The
project is divided into three layers, which have different levels of abstraction.
The layer which is described in this thesis, Cogito/Solver, has the highest
level of abstraction. The central theme, which will be further developed, is
how to find suitable, reusable and changeable software components for appli-
cations in the subfield of interest.
The Cogito/Grid layer is concerned with the efficient implementation of
some important concepts within this field, Grids and Grid Functions (ex-
plained in Appendix A). Portability and efficiency issues are in focus, and
programs that use these tools may be run on either a serial computer or a par-
allel computer with competitive performance [21]. Programs that use the
Cogito/Grid layer use an SPMD style of programming.
In order to be portable and efficient, the Cogito/Grid layer uses the Cogito/
Parallel layer, which is the layer on the lowest abstraction level. An example
of a concept found on this level is the Message, which is responsible for the
messages sent between processors. Programs that use this layer are written
with explicit message passing. The routines found here are portable over a
wide range of parallel computer architectures [18].
At the present stage, the Cogito/Solver layer is not yet using routines from
the other layers. This is an issue that we discuss in “Conclusions and Future
Research” on page 36.

1.2 Related Work

In the scientific computing community there exists several projects where
OO techniques are used, for instance Overture [13], Pooma [22], POET [4],
PETSc [9], and Diffpack [17]. The work with most similarities to Cogito is
Overture, since many of the classes that have been developed represent the
same abstractions. Common for these projects is that they provide many use-
ful classes in a framework or library.
What distinguishes our work from the above is that we focus on how to use
OO techniques in order to separate different parts of the algorithm, while the
other projects focus on the OO approach’s ability to express data abstrac-
tions.

6
 There also exist many projects in computer science that have similar goals
as ours with regard to flexibility and extendibility, particularly with respect to
different parallel architectures. Some projects of this kind include Correlate
[15] and CYES+ [20]. Here, C++ is extended in order to address OO issues
on parallel architectures. In our project, we instead want to explore tools that
already exist, and therefore we choose to use a well-known methodology,
OMT [25], (during the project influenced by other techniques, mainly Booch
[5] and Jacobsson [14]) and we implement the resulting design in an already
existing language, C++, without new language constructs.

2 Motivation for the Object-oriented Approach

In this chapter, we motivate the OO approach that we use.
In the first section, we give an example of a traditionally designed program
where small changes of the requirements may lead to a large amount of
changes in the code.
In the second section, we very briefly discuss some concepts of OO tech-
nology. In many respects, OO programming languages yield programs that
have better properties than traditionally designed programs, for instance with
respect to code reuse and understandability. However, to use an OO program-
ming language does not guarantee an object-oriented program. Therefore, we
will also introduce OO methodologies.

2.1 The Problem of Change

Everything evolves, and a PDE solver is no exception. In this section, we
state some common reasons for this, and we strive to understand why this
implies a problem for traditionally constructed PDE solvers.
The system we aim at shall be able to solve a PDE problem. We want to
describe the problem in such a way that a computer can solve it (approxi-
mately, since exact mathematical solutions may not be obtained) and present
the solution. We want this system to be flexible, especially with regard to the
following features:
• Change of the PDE problem we solve.
Change of the problem may be motivated by a new geometry, other math-
ematical models of the same physical problem, or maybe a completely
new problem etc.
• Change of the numerical method we use.
We may have several different reasons for wanting to change the numeri-
cal method. Maybe, the numerical method yields wrong answers for the
particular problem. This includes unstable solutions, solutions that are
mathematically correct but physically incorrect, or solutions that are not
accurate enough. Another reason for changing the method is efficiency.

7
 Moreover, we require that the system shall be easily extended. It is not
enough if we can solve a predefined set of problems with a predefined set of
numerical methods. A user shall be able to describe new problems, or new
solution methods, and add these to the system. This is particularly useful if,
for instance, the user develops a new numerical method and wants to com-
pare this method against other methods.
To summarize, we have several motivations why a PDE solver shall be de-
signed in such a way that it is easy to modify. We proceed with an examina-
tion on why this issue is difficult, when traditional programming
methodologies are used.
Strongly simplified, a typical PDE problem may be solved with the algo-
rithm below. (For readers unfamiliar with the subject of scientific computing,
we have summarized some concepts of PDE problems and how to solve them
numerically in Appendix A.)

Initiate u(0) according to initial conditions

Loop from time t=0 to T step dt
1) Calculate the space derivatives
2) Calculate u(t+dt) in the interior
3) Calculate u(t+dt) at the boundaries
end loop

Here, u(t) denotes the numerical solution at time t. Step 1) depends on the
chosen numerical method for approximating space derivatives. Step 2) de-
pends on the result from step 1) and the chosen numerical method for ap-
proximating time derivatives as well as the PDE problem coefficients (which
may be space, time, and solution dependent). Step 3) depends on the bounda-
ry conditions from the PDE problem, and from the numerical approximation
of them.
So far, the dependencies are quite simple, but the situation is in fact more
complicated. For instance, if we have periodical boundary conditions along
some dimension, this will influence not only step 3) but also step 1) and step
2). If we want to solve the problem more accurately, we can use a higher-or-
der method for approximating the space derivatives. This may influence the
algorithm for calculating the solution u at the boundaries.
The conclusion is therefore that programs whose design has focused on the
algorithm, as traditional design techniques does, tend to be difficult to modi-
fy.

2.2 Advantages with Object-oriented Techniques

In what way may OO techniques lead to programs that are more easy to
change? And what are OO techniques? We will very briefly comment on
these questions in this section. For readers unfamiliar with the subject, a

8
somewhat more thourough discussion on OO is found in Appendix B, and
the OO methodology OMT is summarized in Appendix C.
The main difference between OO software construction and traditional
techniques is that an OO solution is centred around the important data of the
problem whereas traditional techniques focus on the algorithms. Meyer
points out that the top-down design used in traditional software construction
is very vulnerable, since the correct algorithm may be difficult to know be-
fore the data abstractions are known [19].
Since software is inherently complex, we need to decompose the system in
a comprehensible way. According to Booch, OO decomposition fills this de-
mand better than traditional algorithmic approaches, and it also enhances
code reuse [5]. Other benefits of OO software construction is summarized in
[31] and include higher quality, easier maintenance, better information struc-
tures and better adaptability.
Then, what is OO software? The most important concept is the object,
which represents a relevant data abstraction either from the real world or
from the implementation domain. The conceptual similarity between objects
in the software model and real-world objects is a key to explain the success
of OO software construction. This is enhanced by program constructs which
model relationships between objects, for instance that one object is an aggre-
gate of several other objects.
An object has three features: behaviour, data and identity. Encapsulation
of data and behaviour promotes reuse. Objects that share the same behavior
are grouped together in the same class. In other words, an object is an in-
stance of a class.
The aspect of object-orientation which gives it its special flavour is inherit-
ance. This mechanism also resembles a real-world abstraction, namely when
we say that there are different kinds of some entity. With inheritance, we can
derive classes (inheritors) from other classes (ancestors) so that objects of de-
rived classes have the behaviour specified in the derived class and the ances-
tor class. Therefore, inheritance supports code reuse, but even more
important is that inheritance can be used to build models that are conceptual-
ly clear.
Objects, classes, aggregates and inheritance are thus some important fea-
tures of object-orientation. In order to use the full strength of object-orienta-
tion, many authors claim that it is not enough to use an OO programming
language, but it is equally or even more important to use an OO methodology
[31]. A methodology consists of a notation and a process to carry out the
software development from the specification to the implementation. (Booch
adds tools to be included in the definition of a methodology.)
Several methodologies have been suggested, and among the more well-
known are OMT [25] by Rumbaugh et. al., Booch [5] and Objectory/OOSE
[14] by Jacobsson et. al. This project started off with the intention to follow

9
 OMT, which is described in more detail in Appendix C, but it has been influ-
enced from other methodologies too. In fact, the differences between the
models are minor, and the three key authors now work together on the Uni-
fied Method [6].

3 The Object-oriented PDE Solving System

The previous chapter has motivated our choice to apply an OO methodology
to the domain of scientific computing. In this chapter, we apply the method
to the application domain in order to construct a flexible and extendible PDE
solving system, as one part of the Cogito software project.
The intention of the chapter is to convey the results of the analysis and de-
sign, and to motivate various analysis and design decisions. Therefore, we do
not stress the different OMT documents and the chronological order in which
they were developed. Since OO methods are more iterative than linear, the
logical-historical aspects of the analysis and design become less important
anyway.

3.1 Requirements
Even if the requirements have been discussed earlier, we state them explicitly
in this section. The overall goal of the software project is to supply a soft-
ware system with the following features:
• It shall be easy to construct a program that solves PDE:s numerically.
• The system shall be flexible. Components shall be changeable.
• It shall be easy to extend the system with new components.
Furthermore, we expect the system to fit within the general framework of
Cogito. This implies that we do not need to concentrate on issues from the
other Cogito layers, such as concurrency.

3.2 Key Classes

By examining the application domain (which is described in Appendix A),
we identify some of the key classes of our system.
To begin with, we realize that we need a PDE Problem class for the repre-
sentation of our actual problem that is to be solved. The PDE Problem
knows the governing equations, the boundary conditions and the initial con-
dition (since the problems we are interested in are initial boundary value
problems).
Since conservative and non-conservative PDE problems are represented in
different ways, the inheritors Conservative Problem and Non Conservative
Problem are introduced. Concrete problems will be heirs to either of these
classes. This implies that the system will be extendible with respect to the
problems that can be handled.

10
 The PDE Problem class is shown in Figure 1, where classes that represent
the initial condition and the boundary conditions also are shown. (The nota-
tion is explained in Appendix C.) We also have an association to the Grid,
representing the domain. We could have included the Grid as a part of the
PDE Problem aggregate, but we chose not to do so, emphasizing that the
Grid belongs to a lower level of abstraction. (Introducing a class represent-
ing the domain on the same level of abstraction was discarded, because it is
difficult to represent complex geometries otherwise than through a corre-
sponding Grid.)

Grid

Initial Condition PDE Problem n BC Description

Conservative Non Conservative

PDE Problem PDE Problem

Figure 1. The PDE Problem aggregate

Next, we focus on the numerical method. Since we aim at a flexible frame-

work, the notion of separating the handling of space and time derivatives is
appropriate. Thus, we identify the classes Space Handler and Time Han-
dler, respectively. Exploring the handling of space derivatives in more detail,
we find that in the context of FD, it is not uncommon to use different approx-
imations to the space derivatives in different regions of the grid. Therefore,
we introduce the class Space Discretization, responsible for carrying out a
certain space derivative approximation in a specific domain. Since concrete
PDE problem objects may be either of the type Conservative Problem or
Non Conservative Problem, we need the corresponding inheritance hierar-
chy for the Space Discretization. Hence, the classes Conservative Space
Discretization and Non Conservative Space Discretization are introduced.
Concrete classes that approximate derivatives will inherit from either of
these classes. This will lead to an extendible design with respect to the ap-
proximation of space derivatives.

11
 Applying boundary conditions is a task in a PDE solver that is very prone
to changes, and the class BC Handler will encapsulate this process. In Fig-
ure 2, the Space Handler aggregate is shown.

Space Space Handler n BC Handler

Discretization n

Conservative Non Conservative

Space Space
Discretization Discretization

Figure 2. The Space Handler aggregate

We continue with the Time Handler, which is analogous to the Space

Handler aggregate. We add the Time Discretization class, responsible for
the approximation of time derivatives in a certain region. Concrete classes
would inherit from this class, again yielding a design which is extendible.
Time Time Handler
Discretization n

Concrete
Time ...
Discretization

Figure 3. The Time Handler aggregate

3.3 Scenarios
Having found some immediate key classes from the problem domain, we
look through some scenarios in order to find more classes and to validate the
object model. We consider the following scenarios (compare with [34]):
1. Solve a predefined problem with a predefined method
2. Change the boundary conditions for a given problem and then solve it
3. Solve a new kind of problem with a predefined method
(Solving a predefined problem with a new method is completely analogous
to the third scenario. Therefore, we do not discuss it here.)

12
3.3.1 Solve a predefined problem with a predefined method
The first scenario shows the interplay between the components of the sys-
tem. In order to solve a specific problem with a specific method we basically
follow the algorithm sketched in Section 2.1, but the important difference is
the separation of concerns between different parts of the process. Here, we
examine one iteration of the loop.
1. The Time Handler orders the Space Handler to calculate the right hand
side of the equation ut = right-hand-side .
2. The Space Handler accomplishes this task by delegating it to the Space
Discretization objects. They, in turn, need to cooperate with the specific
PDE Problem we are about to solve.
3. The Time Handler calculates the Grid Function on the next level, with
the aid of its Time Discretization objects.
4. Finally, the Time Handler calls the Space Handler for applying the
boundary conditions. This is carried out by the BC Handlers in coopera-
tion with the BC Descriptions.

When studying this scenario, we conclude that the separation of concerns

and the classes found so far seem adequate. We notice however that it is im-
portant that the different classes are properly connected. A Conservative
Problem shall not be connected with a Non Conservative Space Discreti-
zation, for example. When we extend the scenario to involve several itera-
tions, we realize that a control class for connecting the objects involved in
this scenario will make their use easier. This class, Numerical Experiment,
will also be responsible for storing intermediate results. The Numerical Ex-
periment is shown in Figure 4, together with its associations to its parts. We
choose to model the association as an aggregate, since we regard the Numer-
ical Experiment as one entity.

13
 Numerical
Experiment

Time Handler Space Handler PDE Problem Grid

Figure 4. The key classes in cooperation

We observe that a Grid Function is mentioned. As explained in Section

Appendix A, this is an important concept of the problem domain. However,
as with the Grid, for the purpose of this report we regard the Grid Function
as belonging to a lower level of abstraction.
Operations that are discovered through this scenario include
Time Handler::advance()
Advances the solution one time step. (The whole scenario.)
Space Handler::calcRHS()
Calculates the right hand side.
Space Discretization::calcRHS()
Calculates the right hand side in a specific region.
PDE Problem:: “apply governing equations”
Applies the governing equations. This issue depends on which
kind of PDE Problem we have, and we refer the details until the
discussion of the third scenario.
Time Discretization::advance()
Advances the solution one time step in a specific region
Space Handler::applyBC()
Apply the boundary conditions.

14
3.3.2 Change the boundary conditions for a given problem
The second scenario concentrates on how to set up a particular Numerical
Experiment and the difficulties with changing the boundary conditions. We
want to be able to do as follows:
1. Choose an existing PDE Problem
2. Switch BC Descriptions
3. Add to a Numerical Experiment the PDE Problem, a Space Handler, a
Time Handler, and a Grid
4. Solve the Numerical Experiment

Here, we immediately recognize some operations that are needed in order

to switch boundary conditions and set up the experiment, such as Numerical
Experiment::use(PDE Problem) etcetera. Since these methods are implicitly
contained in Figure 4, we do not state them explicitly. Instead, we notice that
the Numerical Experiment has the dynamic behaviour which is expressed by
the state diagram in Figure 9.
The operation Numerical Experiment::solve() is in practice already de-
scribed by the previous scenario. But we must refine the treatment of the
boundary conditions to achieve the desired change smoothly. First, by look-
ing into the problem domain in more depth we distinguish several kinds of
boundary conditions. Two of the most important ones are
• Dirichlet boundary condition, u = g ( t )
• Mixed Neumann and Dirichlet condition, u x = ug1 ( t ) + g2 ( t )
(Actually, there exist many more kinds of boundary conditions, but in this
context it is enough to consider these two. For a more thorough discussion,
see [1].) The Dirichlet condition is straight forward to implement, but the
mixed condition demands some approximation of the space derivative. We
have already presented the BC Description and the BC Handler classes,
which were introduced because we want to separate concerns regarding the
description of the PDE Problem and the numerical method used to solve it.
The different kinds of boundary conditions motivate the inheritance hierar-
chy of BC Description in Figure 5a, with the corresponding inheritance hi-
erarchy of BC Handler shown in Figure 5b.
When we connect a Space Handler to a PDE Problem, we have to check
that the Space Handler has Space Discretizations of the correct kind, for
instance a Conservative Problem needs to be matched with Conservative
Space Discretizations. Furthermore, we have to make sure that the Space
Handler has BC Handlers that can deal with the actual BC Descriptions
the PDE Problem contains. If this control is successful, we can continue and
solve the problem. We conclude that the proposed object model can handle
the scenario above.

15
 BC BC
a) Description b) Handler

Dirichlet Neumann Dirichlet Neumann

BC BC BC BC
Description Description Handler Handler

Figure 5. Hierarchies of a) BC Description and b) BC Handler

3.3.3 Solve a new kind of problem

The focus of the third scenario is on the extendibility requirement. This sce-
nario is not a traditional scenario in the sense that the user only interacts with
the compiled run-time system1. Instead, the user interacts with the system by
extending it in the following way:
1. A new kind of problem with new governing equations is constructed.
2. The new problem is added to the system and solved with predefined meth-
ods.

To see what steps that are needed in order to realize this scenario, we have
to detail the previous model especially with respect to the interplay between
the PDE Problem and the Space Discretization.
As we already have pointed out, a new problem will be a heir to either a
Conservative Problem or a Non Conservative Problem.
By the definition in Section Appendix A, a conservative problem is ex-
pressed by the equation ut = f ( u ) x . Therefore, concrete conservative prob-
lems need to specify the flux, f ( u ) . Detailing the signature of the operation,
we find that it shall take as inparameters a Grid Function and the region of
the Grid where the flux is to be calculated. This operation will be called
upon by Conservative Space Discretization objects, who then have the re-
quired information for calculating the right hand side of the equation in their
respective parts of the Grid. To summarize, a new conservative PDE prob-

1. The difference between this use case and traditional ones is that the user extends
the run-time system by implementing a small amount of code and then compiles
it. However, with a more advanced interface the interface could generate and
compile code, making this a traditional use case. See “Conclusions and Future
Research” on page 36.

16
lem is constructed by deriving from the class Conservative PDE Problem
and implementing the pure virtual operation flux().
A Non Conservative Problem is somewhat more complicated since the
number of terms may vary:

u t = F + A 0 u + A 1 u x + ...

The order of a differential equation corresponds to the term with the high-
est derivative. We recognize this as an important attribute of Non Conserva-
tive Problems. For our purposes, we have found that the following
operations manage to represent an n:th order non conservative PDE:
Non Conservative Problem::addForce(u, region)
Add the force F to the Grid Function u in the specified region.
Non Conservative Problem::addTerm(N,u,v,region)
Add the N:th term of the PDE to the Grid Function u. The argu-
ment v symbolizes the N:th derivative of u.

Thus, a new non conservative problem would inherit from the class Non
Conservative Problem, and the operation addTerm would have to be imple-
mented. (The operation addForce is not abstract, it adds by default no force.)
A Non Conservative Space Discretization would subsequently approxi-
mate the needed derivatives and then call for the adding of the appropriate
term.
Summing up the third scenario, we find that it is fairly easy to construct a
new problem. After successful compilation of the new code, we add proper
initial conditions and boundary conditions to the problem and then we pro-
ceed as before by connecting objects with the aid of a Numerical Experi-
ment. Our analysis of the scenario also shows how the cooperation between
Space Discretizations and PDE Problems may be done.

3.4 Discussion about Alternative Solutions

In this section, we consider some alternative solutions that were investigated
during the process. Since these alternatives were discarded, a reader only
concerned with the final product may skip this section. However, we think
that these discarded models are worth some attention. First, they motivate
some of the analysis and design choices we make. Secondly, they might still
be used when the project evolves.

17
 3.4.1 The Numerical Method class
It is possible to introduce a class which is responsible for the complete nu-
merical method, both the approximation of space derivatives and time deriv-
atives. Since some numerical methods treat both approximations
simultaneously, this class would provide means for including these types of
numerical methods, too. See Figure 6

Numerical
Experiment

Numerical PDE Problem Grid

Method

Concrete Method MOL method

Time Handler Space Handler

Figure 6. Discarded design for the Numerical Method

Even if this model may be conceptually correct, we discard it because it

seems to be more complicated than needed in our work. We simply make the
restriction not to support this kind of numerical methods.
Moreover, even numerical methods that do not explicitly separate space
and time can be expressed in this framework. Consider, for example, the
Lax-Friedrichs scheme for the first order PDE ut = au x :

new 1
v = --- ( v j + 1 + v j – 1 ) + kaD 0 v
2

(Here, v is the discretization of u and D0 is a numerical approximation to

the derivative.)

18
 This algorithm may be accomplished by an ordinary Space Discretization
that calculates the right-hand-side aD0 v , together with a Time Discretization
that calculates the time derivative according to the formulae above.
By combining objects with the desired behaviour it is thus easy to con-
struct a Numerical Experiment which solves a first order PDE with the
Lax-Friedrichs scheme. Even though we do not explicitly have a Numerical
Method object for Lax Friedrichs scheme, we can create a Numerical Ex-
periment that uses the scheme. Furthermore, if the objects are stored in an
OO database we can easily reuse this scheme on other problems. Hence, the
second reason for discarding a special Numerical Method class is that the
functionality it provides can already be found in the system.

3.4.2 PDE Equation in domain

Studying the analogy between the Space Handler and the Time Handler,
the symmetry might suggest that the PDE Problem would be modelled in a
similar manner, as seen in Figure 7. The responsibility for describing the
governing equations would be moved from PDE Problem to PDE Equa-
tion, and the equation would be valid only in a certain domain.

PDE Equation PDE Problem

n

Conservative Non Conservative

Equation Equation

Figure 7. Discarded model of PDE Problem

This model would make it possible to treat different equations in different

subdomains, which is relevant in some applications. However, at present, we
choose the simpler solution, because we think it is adequate enough to dem-
onstrate the viablity of our approach. Still, if it turns out to be an important
issue as the system evolves, it seems to be rather easy to refine the model in
this respect.

3.4.3 Treating the governing equations in a general fashion

Techniques for expressing general equations in C++ exist, see for instance
[23]. Is it feasible to introduce techniques such as these in order to express

19
 the equations? The advantages would be a coherent way of treating conserv-
ative as well as non-conservative governing equations.
We believe that even if this approach is tempting because the idea is rather
elegant, it would lead to object models that are more difficult to understand
and maintain. Moreover, we are afraid to loose some of the information that
the inheritance hierarchies provide. A conservative problem, for instance, ex-
press the fact that the problem has the physical property that something is
conserved. This information is useful to the user who shall choose a proper
numerical method to solve the problem.
The bottom line is that in order to keep the system easier and to keep the
existing information structures, we do not attempt to handle equations in a
completely general way. Also, we believe that the previously presented mod-
el can more easily be made efficient. Finally, the chosen subclasses of PDE
Problem, Conservative Problem and Non Conservative Problem, cover a
broad spectrum of relevant application problems.

3.5 Comments on the Different OMT Models

In this section we comment on the different OMT models, before we contin-
ue the analysis and design work by defining an architecture (system design)
and refining the existing model (object design).
According to Rumbaugh, the functional model is the most important mod-
el in applications such as PDE solvers, which traditionally are implemented
as batch systems.
But from our perspective, where the flexibility with which to use the sys-
tem is considered a more important goal than the actual low-level algorithms
(since the algorithms are considered to be known), we think that the other
models are of more importance. This reflects the fact that we do not design a
“traditional” PDE solver.
As for the dynamic model, this model is important especially when we
take into account the possibilities of combining the different objects in struc-
tured ways. One example is the state diagram of Numerical Experiment
shown in Figure 9
But since the separation of concerns together with the system’s extendibil-
ity are such important goals, we have found that the object model is the most
important one. (This is reflected in this report, where we concentrate on the
object model, comment on the dynamic model, and omit the functional mod-
el.)

3.6 System Design

An important design choice is the choice of implementation language. In
practise, it was decided early in the project to use C++. Since the analysis
uses inheritance and polymorphism intensively, we want an OO language,

20
and when efficiency issues are considered, C++ seems to be the most promis-
ing alternative.
The organization of the system into subsystems is shown in Figure 8. We
have already touched upon the organization of Cogito (Section 1.1). The
three layers Cogito/Solver, Cogito/Grid, and Cogito/Parallel, form a closed
architecture, which means that each layer is only allowed to use operations
from the layer immediately below. The advantage with a closed architecture
is that maintenance becomes easier; since one layer’s interface affects only
the next layer. In an open architecture, each layer can use features from any
lower layer. This enhances efficiency, and we therefore use an open architec-
ture within the Cogito/Solver layer. In particular, Grid and Grid Function
objects are usable from within any layer. Also, for some applications it may
be desirable to bypass the Numerical Experiment layer. But even if we, due
to efficiency reasons, choose an open architecture, we strive to keep depend-
encies as local as possible. As an example, we do not want the Time Han-
dler to be dependent on the PDE Problem.

Numerical Experiment

Time Handler Package

Space Handler Package

PDE Problem Package

Grid & Grid Function

Figure 8. The organization of the system into layers. Within Cogito/Solver the sub-
layers form an open architecture, indicated by the dotted lines. The layers Cogito/Solv-
er and Cogito/Grid have a closed architecture.

Concurrency aspects are not discussed in this report. We think that a data-
parallel approach to concurrency is possible, simply by using a Grid Func-
tion class that may be serial or parallel. As mentioned, such a class exists in
Cogito/Grid.
Data storage is always important for a PDE solver, especially regarding
Grids and Grid Functions, since they are likely candidates for pre- or post-
processing. For this project, it is more interesting to study the novel aspects
of storing the states (including links) of the other objects, since we want to
reuse not only individual objects but rather several objects in an interesting

21
 combination. To this end, an OO database management system is appropri-
ate. See Section 4.3

3.7 Refining the Model

The object design is mainly a refinement of the analysis. In this section, we
discuss some particular design choices.

3.7.1 The handling of time

Since we want to be able to treat problems where the coefficients may de-
pend on the time, and the information on which time level we have reached
resides with the Time Handler, we have to design the communication be-
tween the Time Handler layer and the PDE Problem layer.
Several possibilities exist:
1. Let the actual time be a parameter to the call of SpaceHandler::calcRHS
which also is sent to the PDE Problem. (Compare with the scenario in
Section 3.3)
Against this solution speaks the fact that not all problems have time depend-
ent coefficients, and it seems unattractive to always send an extra parameter
even if it is not needed.
2. Let the PDE Problem have a pointer to the Time Handler, so it can ask
what time it is, if it needs to know.
This would not fit into the proposed architecture. Even if it is possible to do it
like this, circular dependencies between layers or classes shall be avoided.
As a compromise, we suggest the following solution:
3. Introduce a new class which keeps track of the time. When the Numerical
Experiment is set up, the PDE Problem gets an association to the time
object. The time object is updated only by the Time Handler, though.
This solution seem to be a disciplined yet flexible way of dealing with the
time, without introducing circular dependencies.
Another idea that might be taken into consideration in future work is to
mark each Grid Function with a time stamp. This would perhaps be a more
elegant solution.

3.7.2 The space regions

We have already stated that a Space Discretization for instance shall be re-
sponsible for the approximation of the space derivatives in a certain region.
We have to be careful when we set up a Space Handler, so that each point in
the Grid actually is covered once and only once by a Space Discretization
or, when boundaries are included, a Boundary Handler. Also, by the nature
of FD, each Space Discretization object will use some values outside the re-
gion in which it act. This implies that some Space Discretizations may not
be placed at the boundaries.

22
 Thus, we equip each Space Discretization with an active region where it
is allowed to act in order to calculate the right-hand-side needed by the Time
Handler. Similarly, each Boundary Handler has an active point.
When the Numerical Experiment is set up, the PDE Problem and the
Space Handler have to cooperate in order to set the active regions of the par-
ticipating objects properly. It is possible to construct automatic algorithms
for this, but for more complicated situations, we allow the user to decide in-
teraction regions.
Note that a Non Conservative Space Discretization that solves a second
order PDE Problem is responsible for treating both the first-order derivative
and the second-order derivative in the same region.
For the Time Handling and the Time Discretization objects, the situation
is similar.

3.7.3 State diagrams

When we study the order in which we shall combine the components, it is
appropriate to use the dynamic model.
We conclude that it is quite user-hostile if we demand that components
shall be connected in a specific order. The important thing is whether the spe-
cific combination of objects can solve a numerical experiment or not. Figure
9 shows the state diagram for the Numerical Experiment.

Not connected Connected

Figure 9. State diagram for Numerical Experiment

The Numerical Experiment starts in the state Not connected. The transi-
tion from the state Not connected to the state Connected occurs when enough
parts have been added, that is a PDE Problem, a Space Handler, and a
Time Handler. Further, the Space Handler must be appropriate for the
problem at hand. For example, if it is a second order Non Conservative PDE
Problem, the Space Handler must have a Space Discretization able to han-
dle problems of that kind.
Subsequent changes of the Numerical Experiment’s components may or
may not change the state to Not connected.

23
 Calling the Numerical Experiment’s solve method is only allowed when
the state is Connected.
Identical state diagrams may be derived for the other key classes, for in-
stance the PDE Problem, as shown in Figure 10 The initial state is Not con-
nected, and the transition occurs when the Numerical Experiment which
the PDE Problem is a part of changes state.

Not connected Connected

Figure 10. Possible state diagram for PDE Problem?

This model will only work, though, if a PDE Problem object belongs to
only one Numerical Experiment at a time. Since the object model does not
impose such restrictions, and since we do not find any new information in the
PDE Problem state diagram beyond what we already have in the Numerical
Experiment state diagram, we do not push the components’ dynamic behav-
iour further. Instead we rely on the Numerical Experiment to ensure the
correct usage of the other components.

4 Results
Besides the OO analysis and design presented in the previous chapter, which
we think is a result in itself, we will in this chapter focus on some results ob-
tained through the pilot implementation.
In Section 4.1, we describe the evolution of the pilot implementation. The
purpose is to validate the design.
In Section 4.2, we demonstrate how a main program creates and combines
classes into a system which is able to solve the chosen problem.
In Section 4.3 we show that by equipping the classes we discuss in this re-
port with an OO database management system, we get a tool with which we
interactively may construct PDE solvers, and also remember the links be-
tween executions.
Finally, in Section 4.4, we show an example of the system’s robustness.
We consider a kind of method which was not considered in the original de-

24
sign, and propose a solution which does not affect the overall design. This in-
dicates that the model is sound.

4.1 Evolution of the Pilot Implementation

When developing the pilot implementation, we want to show that the design
model works for a wide variety of PDE problems and methods. In this sec-
tion, we will cover the evolution from the design to the implementation. We
develop the system in very much the same way as Booch uses executable re-
leases, so that every class developed in each stage will be a true subset of the
final system.
Since the purpose of the current pilot implementation is to validate and ex-
amine the object model, we relax the complexity constraints somewhat. First,
we restrict ourselves to one dimension. Furthermore, we write our code only
in C++, so the code may be developed without complications of mixing pro-
gramming languages and without being dependent on the Cogito/Grid layer.
Still, we emphasize that the object model is not limited to one dimension or
to non parallel Grid Functions.

4.1.1 PDE Problems

In this subsection, we describe the problems that we develop. They are model
problems, with known solutions. See [10].
Table 1 summarize the problems and their properties. Non-linear problems
with coefficients depending on space and time are not completely trivial,
even if they are in one dimension. We also develop both conservative and
non-conservative equations.
The problems also have boundary conditions of both Dirichlet type and
Neumann type.

Table 1: Implemented problems and their characteristics

Number
Order of
Problem Type of Type of BC
derivatives
unknowns

Engquist 1a Non conserva- 1 1 Dirichlet

tive, Hyperbolic
Engquist 4 Non conserva- 2 1 Dirichlet
tive, Hyperbolic
Engquist 7 Non conserva- 1 2 Dirichlet,
tive, Parabolic Neumann

25
 Table 1: Implemented problems and their characteristics

Number
Order of
Problem Type of Type of BC
derivatives
unknowns

Engquist 15 Conservative, 1 1 Dirichlet

Hyperbolic
Engquist 22 Non conserva- 2 1 Dirichlet
tive, Hyperbolic
a. The problems have the same numbers as in [10].

The last problem’s equations are given below. They resemble the equations
for shallow water.
u t + uu x + v x + 5 u u = – sin ( x – t ) cos ( x – t )

v t + vu x + uv x = 5 cos ( x – t ) + sin ( x – t ) ( 2 cos ( x – t ) – 1 )

4.1.2 Space Discretizations and BC Handlers

To deal with the above problems, we need to develop BC Handlers dealing
with boundary conditions of both kinds and several different Space Discreti-
zation objects. We begin with Non Conservative Space Discretizations:
1. InteriorSD
The InteriorSD object uses a three-point wide stencil, both for calculat-
ing the first derivative and the second derivative. The first-order derivative
1
in the i:th point is approximated with u x ≈ D 0 v i = ------ ( v i + 1 – v i – 1 ) and the sec-
2h
1
ond order derivative with u xx ≈ D + D - v i = ----2- ( v i + 1 – 2v i + v i – 1 ) . (Here, v is the
h
discretized approximation of u and h is the mesh size. Since the stencil is
as wide as it is, it can only be applied in the interior, and we thus call this
class InteriorSD.
2. LeftSD
At a left boundary, we use a one-sided stencil. LeftSD implements the fol-
1
lowing approximation: u x ≈ D + v i = --- ( v i + 1 – v i ) .
h
3. RightSD
RightSD may be used at a right boundary, and implements the following
1
approximation: u x ≈ D - v i = --- ( v i – v i – 1 ) .
h

26
We also need to develop a Conservative Space Discretization. A numerical
method for conservative problems that may be used is an upwind method,
implemented in the class Upwind.
Remark: For the problems at hand, it is enough to treat one derivative at
the boundaries and two in the interior. It would not be difficult to extend the
system with Space Discretizations that treat derivatives of higher order. Nei-
ther would it be difficult to implement more accurate, high-order, stencils,
nor conservative methods that have better properties.

4.1.3 Time Discretizations

The next category of classes we need to develop treat the time derivatives.
Note that we need not bother about which kind of problem it is, if it is con-
servative or non conservative, thanks to the separation of concerns.
The following Time Discretization classes have been implemented.
1. Forward Euler
This is the simplest explicit time stepping method.
2. Classical Runge-Kutta
This is the well-known classical 4:th order Runge-Kutta method.
3. Leap-Frog
This is a so-called linear multistep method, which uses values from both
the current time level and the previous to obtain values on the next time
level. In the very first step we use Forward Euler.

As with the Space Discretizations, we can easily add more time stepping
methods to the system. For explicit methods, this is straightforward. Implicit
methods also fit into the framework, but rely on more expressive tools on
lower layers.

4.1.4 Evolution summary

In addition to the already mentioned classes, we also have to develop the oth-
er classes of our framework, Numerical Experiment, Space Handler, Time
Handlers, Grid and Grid Functions, Initial Conditions and so on. The im-
plementation of all of these classes is straightforward. Since we use an OO
language when we implement the design model, the difference between the
models is small.
However, we point out one technical obstacle which leads to some difficul-
ties. To be specific, we have to deal with how to ensure that a conservative
Space Discretization is only connected to a Conservative PDE Problem.
(The same discussion applies to BC Handlers and BC Descriptions.) The
difficulty is that when we add a PDE Problem heir to the Space Handler,
the Space Handler has to check its actual type and act accordingly. But

27
 since Conservative and Non Conservative PDE Problems have different
interfaces, we have to do some trick in order to be able to actually compile
the code. (Remember that C++ is a strongly typed language.) The following
solutions may be considered:
1. Find out the actual type and perform a dynamic cast. We can find out
which type it is by introducing an attribute which is different for different
subtypes. (The latest C++ standard specifies run-time type checking, but it
is not yet available.)
2. Find out which type it is in the same way, but by moving the interface of
the subtypes to the PDE Problem class itself, there is no need for
dynamic casts.

Neither of these solutions is quite satisfactory, because it introduces depend-

encies in the inheritance hierarchies. To add a new kind of PDE Problem
subtype, we have to make changes in the PDE Problem class itself, especial-
ly if the second strategy is used. Because we strive for simple solutions, we
discard the first alternative and choose the second anyway. This is the main
difference between the implementation model and analysis/design model.

4.2 Example: Main Program

We illustrate how a typical main program is coded in this framework, in or-
der to solve a concrete problem. We choose to solve the shallow water like
equations (see Section 4.1.1) using the Non Conservative Space Discretiza-
tions described in Section 4.1.2 and classical Runge-Kutta in time(see Sec-
tion 4.1.3).

int main()
{
// The main objects.
NumExp myExp;

NonConsProblem *problem = new ShallowWater;

// An heir to NonConsProblem

SpaceHandler *spacehandler = new SpaceHandler;

TimeHandler *timehandler = new TimeHandler;

const int N = 100; // Grid point indices from 0 to N

Grid *grid = new Grid(0.0 , 1.0, 0,N);1

// Prepare problem
// "ShallowWater_*" is functions declared in "user.h", used to
// initate initial conditions and boundary conditions.

1. Note that this simple Grid is only used in the pilot implementation, but the design
is intended for more complicated grids such as composite grids.

28
 FcnInitCond ic( ShallowWater_IC);
BCDirichlet bcleft(left,1,ShallowWater_BC); //Same BC function
BCDirichlet bcright(right,1,ShallowWater_BC);//at both boundaries

problem->use( &ic);
problem->add( &bcleft);
problem->add( &bcright);

// Set up the spacehandling.

SpaceDisc *interiorSD = new InteriorSD;

SpaceDisc *boundarySD1 = new LeftSD;
SpaceDisc *boundarySD2 = new RightSD;
DirichletHandler *bchd = new DirichletHandler;
NeumannHandler *bchn = new NeumannHandler;

theSH.add( interiorSD );
theSH.add( boundarySD1 );
theSH.add( boundarySD2 );
theSH.add( bchd );
theSH.add( bchn );

// Set up the timehandling.

double dt = 0.4/N ; // time step
TimeDisc *timedisc = new RungeKutta(dt);
timehandler.add( timedisc );

// Prepare the experiment

myExp.use( grid);
myExp.use( problem);
myExp.use( theSH);
myExp.use( timehandler);

// Run and store solution on file!

myExp.solveUntil(1.0,"exShallow.m");

return 1;
}

We note that the program consists of three parts:

1. Create objects
2. Combine objects
3. Solve

This style of programming differs remarkably from programs developed

with traditional methodologies. Once again, we stress that since the algo-
rithm is decomposed into subalgorithms which different objects are responsi-
ble for, it is very easy to change parts of the algorithm. For instance, if we
change the one line where the problem is created to:
NonConsProblem *problem = new Wave;

29
 instead, we would solve a different problem!
It is as easy to change the numerical method.

4.3 CogitoWorkBench
In the previous section, we noticed that the main program consisted of three
parts, the creation phase, the composition phase, and the solving phase. It is
not completely satisfying if we want to make small changes to the program
and then have to recompile it every time. Moreover, a specific PDE problem
consists of other components as well, and what we would like is to compose
a specific problem once and for all, and then be able to reuse the problem ag-
gregate over and over again.
The solution is to equip the classes with an ODBMS (object-oriented data-
base management system). In an ODBMS, the whole state of an object, in-
cluding links, can be stored between executions of the system.
The resulting system called Cogito WorkBench (CWB) was implemented
by Strandberg [30]. It uses TPS (Texas Persistent Store) [29] to obtain per-
sistency, and has a menu-driven interface to interact with the Cogito/Solver
classes.
With this system, the complete main program from the previous section
may be created in run-time, just by choosing menu alternatives.
With CWB, it is possible to create new objects of the classes from the
Cogito/Solver layer, and then they may be combined interactively. Finally, a
Numerical Experiment object can get the task to solve its problem.

4.4 Is the System Robust?

The real test for the system is when we attack issues that were not considered
from the beginning. One such issue is the need of numerical methods with
artificial dissipation. In this chapter we will discuss different ways of incor-
porating artificial dissipation into the design. The proposed solution seems to
handle the new issue with minor changes, and within the current setting.
The motivation for artificial dissipation is that it moderates fluctuations
and makes the solution more smooth. The basic idea is to add a high-order
derivative to the problem equation times a small constant. For instance, the
equation

ut = u x

30
 may numerically be solved with

v t = ( D + εD 2 )v

where ε is a small number, v is the approximation of u and D and D 2 are

the approximations of the first and second order derivatives, respectively.
How would we treat artificial dissipation in our framework? A naive but
simple solution is to derive a problem where the artificial dissipation term is
added, and solve this problem instead. The advantage is that it would fit di-
rectly into the current framework. However, the disadvantage is that it is in
conceptual conflict with the framework. The artificial dissipation is a feature
of the numerical method, and not a part of the problem. It would be awkward
if we had to derive new problems every time we want to use a numerical
method which uses artificial dissipation.
A better alternative would be to let the Space Discretizations be responsi-
ble for adding the artificial dissipation term. However, some numerical meth-
ods do not calculate the artificial term as often as the other terms of the
problem. For example, a 4-stage Runge-Kutta method could calculate the ar-
tificial term once per step and not in every stage, in order to increase efficien-
cy. It seems as if the Time Handler shall be responsible for when artificial
dissipation shall be calculated and the Space Handler for how. This is actu-
ally the same division of responsibilities that we use for the handling of
boundary conditions [1]! Therefore, we think that this solution is sound.
It can be accomplished in several ways. One way is to derive a class Time
Discretization with Dissipation. An object of this class would have associa-
tions to two objects, which perform the calculations with and without artifi-
cial dissipation, respectively. This solution has the advantage that it does not
change anything in the other key classes and the abstract base classes that
other classes inherits. In Figure 11, this solution is showed in an instance di-
agram.

31
 (Time Discreti- (Space Handler)
zation with
Dissipation)

(Space
(Space Discretization)
Handler)

(Dissipation
Discretization)

Figure 11. A Time Discretization with Dissipation uses two Space Handlers, one with
Dissipation Discretization (which is a concrete heir to Space Discretization)

The conclusion is therefore, that we can handle artificial dissipation within

the current framework.

5 Discussion
When software is constructed, there is always a trade-off between different
desirable but often incompatible goals. Jacobsson [14] divides quality as-
pects into two main categories: suitability and maintainability. The suitabili-
ty category includes for instance reliability and efficiency, while the
maintainability category includes understandability and modifiability. In
general, OO methods concentrate first on the latter category. As we have
pointed out, (Section 3.1), this is the case also for this project. We believe
that this is more sound, because it should be easier to make a maintainable
program suitable than the other way around.

32
 However, generally it seems as if there is a price you have to pay when you
raise the abstraction level of the program. The abstraction penalty is intro-
duced in [24] and defined as:

execution time of high level program

abstraction penalty = -----------------------------------------------------------------------------------------
execution time of low level program

This measure can be used for instance to compare a FORTRAN imple-

mentation with an assembler coded version of the same operation, or the cost
for using C++ compared to C. Even if it is an interesting measure, it does not
say anything about the human effort required to implement the low level ver-
sion compared with the higher level. In [11], Golub and Ortega say that the
major considerations when developing scientific computing software are ac-
curacy and efficiency–both human and computer. The insight that human ef-
ficiency also matters is important for this work. And human efficiency in this
field will get a more important consideration as the performance of comput-
ers keep improving. Therefore, we believe that maintainability issues in gen-
eral are more important than suitability issues. Thus, even if the framework
which is presented here is not yet very fast, it can still be of interest to use in
a number of applications where the efficiency requirements are not too high.
Examples include educational versions, the solving of problems with moder-
ate demands, and also research which develops new methods and needs a
testbench.
Even if we are willing to pay an abstraction penalty price, the abstraction
penalty should of course be as low as possible. Some researchers report of an
abstraction penalty of ten when migrating from F77 to C++, and some rea-
sons for this are discussed in [36]. Such a high abstraction penalty is of
course not tolerable. Here an interesting technique of using templates is de-
scribed for avoiding unnecessary temporary variables and thereby increasing
performance. Another source of the abstraction penalty is compilers that
generate inefficient code, but in this area progress is reported [24].
The general discussion so far applies specifically to the framework devel-
oped in this project. We will continue by examine some key reasons for de-
graded performance in this system. Since we plan to extend the classes to
problems in several space dimensions, we have not tuned the current pilot
implementation with respect to performance. Still, we have studied some dif-
ferent degradation sources and we propose solutions that should improve the
efficiency.
• The Grid Function class is inefficient
This is probably the most important factor to the abstraction penalty. Lit-
tle care is taken about avoiding temporary variables, for instance. It was

33
 early decided not to put too much effort into this class, since it was devel-
oped only for the pilot implementation in one dimension. When changing
implementation to a multi-dimensional grid function class, much more
care shall be taken to make this class efficient. A parallel grid function
class as found in Cogito/Grid would be able to use parallel high perform-
ance computers, which would increase performance. The implementation
can be made more efficient also in other ways, for instance by using
counted references as described in [8] and implemented in Overture.
• The Space Discretization and the PDE Problem communicate too much
The process of calculating the right hand side of the equation is the most
time critical part of the program. When we take this into account, it can be
concluded that the number of messages between the Space Discretization
and the PDE Problem should be minimized. The algorithm presented in
Section 3.3.3 addresses the flexibility issue, but not the issue of minimiz-
ing the number of calls. However, by precalculating all necessary deriva-
tives at once, we can decrease the number of calls. (In Overture, a similar
technique has been implemented.)
• Dynamic binding takes time
In [5], it is said that experiments suggest that calls to virtual functions
may take as long as 2.5 times longer than procedural calls. If this is done
in a very time critical part of the algorithm, it may affect the performance
negatively, but if the routine itself has not too low granularity or is not
called too many times, it does not matter that much. Further, we believe
that the price of dynamic binding is rather cheap and it is a price that one
has to pay, if the flexibility and extendibility issues are concerns.

To summarize the discussion on efficiency, we propose some different ways

of improving efficiency that still does not affect the overall object model. Be-
sides, we argue that when both human and computer efficiency are consid-
ered, a price in computer efficiency may be paid if the human efficiency is
improved. Therefore, we continue by discussing expressiveness.
By the identification of different concepts from the application domain
(Section 3.2), we have arrived at a system which is natural for the application
domain. The proposed aggregationships and inheritance hierarchies express
relations among objects and classes, that also are conceptually correct. For
instance that a Concrete Problem is a PDE Problem and a PDE Problem
has a BC Description. These facts are a consequence of the OO technique
and they all help to make the system more understandable, maintainable and
expressive.
The example presented in Section 4.2 is almost trivial on the topmost lev-
el, and even if we calculate the number of methods that need to be imple-
mented in order to derive the necessary concrete classes, the coding effort is

34
small. Moreover, once a class has been successfully implemented, it can be
reused.
With an OO database on top of the classes, reuse can be enhanced, as dem-
onstrated in Section 4.3 We believe that this approach is very promising.
Still, even if we claim that the system in general is expressive, we realize
that there exist several ways to improve the system, also with respect to ex-
pressiveness. Once again, the Grid Function class could be better. For in-
stance, the add-method needs parameters for knowing which part of the grid
function it shall be applied on. This signature should be simplified, by repre-
senting the part of the grid function by some utility class. Further, it could be
possible to define an active part of the Grid Function, where all subsequent
calls would be applied. This solution would make it possible to use operator
overloading for arithmetic functions, which significantly would raise the ab-
straction level. This problem is addressed also in Cogito/Grid and Overture,
and the solutions are similar.
Finally then, what are the lessons learned? Regarding the process and the
methodology, we can draw at least one conclusion. The usage of proper tools
can not be underestimated. As mentioned in Section 2.2, Booch explicitly
states that tools are a part of the methodology, as important as the notation
and the process. Tools that would have been beneficial to our work are of
course CASE-tools such as Rose [37], so that diagrams and implementation
always can be kept up to date. But other tools that one should use more ex-
tensively are what Jacobsson calls components, classes that are developed
specially for reuse, such as lists etc. In the specific subfield of scientific com-
puting addressed by this work, a Grid Function is a strong candidate for be-
ing a component, since it represents such an important application concept.
This is recognized both in Cogito/Grid and Overture, and the success of ob-
ject-orientation for this and other fields will depend heavily on the proper de-
velopment and usage of components.
Another lesson is regarding the design of the interface of Cogito Work-
Bench. The menus are mirroring the key classes and their inheritance hierar-
chies. This is one way of easily find different classes. However, the
aggregationship relations could be used to find which objects a typical Nu-
merical Experiment consists of, and we believe that for an interface such as
this, both the inheritance hierarchy and the aggregation hierarchy should be
supported in order to get a more user-friendly system. This reflects the differ-
ence between the compile-time structure of the program and its run-time
structure.
The discussion so far has motivated the need for human efficiency, which
implies that it is sound to focus on expressibility before computer efficiency.
OO methodologies have this philosophy, and that is why we use an OO ap-
proach in our work. The results of this work are encouraging, even if we have
pointed on several weaknesses in our pilot implementation, actually both

35
 with respect to efficiency and expressibility. Still, we claim that the proposed
object model is sound. Making computer programs is more than only writing
code. We think that the analysis and design which lies behind the implemen-
tation are the most important contributions of this work, especially because
of the novelty of the approach.

6 Conclusions and Future Research

In this report, we present an OO analysis, design and implementation of a
PDE solving system, which can be used for solving initial boundary-value
problems. The problems as well as the numerical methods for solving them
are represented as objects, which allows for a very flexible application
framework. This framework is extendible, since the communication between
objects are prescribed by interfaces of relevant abstract base classes. Through
the OO inheritance concept, new concrete problems or numerical methods
may be expressed with a small amount of coding.
In Chapter 4, we demonstrate that the pilot implementation meets the re-
quirements: The framework is flexible, easily extendible, and it allows the
user to construct PDE solvers readily. This system would naturally be benefi-
cial for users that want to solve PDE problems, since they would not need to
develop the numerical methods, only the PDE Problems (if they not already
exist). The system would likewise be useful to users that want to develop and
investigate a new numerical method.
The current pilot implementation is not optimal with respect to computer
efficiency. But, as the discussion in Chapter 5 states, with respect to expres-
siveness and human efficiency the OO approach is very promising. Moreo-
ver, efficiency will improve by using more efficient low-level classes, still
within the presented OO design.
The whole construction process is sketched in Chapter 3, from analysis to
implementation. We want to stress that even if the pilot implementation is
one-dimensional, the analysis and design are more general, and intended for
multi-dimensional applications on more complicated grids. In addition the
high-level object model in Figure 4 can be used not only for finite differenc-
es, but also for other common numerical methods such as finite elements.
Future work may proceed in many directions. The previously mentioned
idea to investigate and explore the similarities between finite differences and
finite elements is one of the most interesting. However, the most important
issue is to extend the system so that multi-dimensional problems may be han-
dled. This would be a major step towards real-world problems. Furthermore,
we want to improve efficiency, for instance by using a parallel Grid Func-
tion class. Finally, but not least important, we would like to employ the sys-
tem with a more user-friendly and a more advanced interface.

36
 Today, it is possible via menus in Cogito WorkBench to interactively cre-
ate and compose objects into an executable PDE solver. The vision for to-
morrow is a graphical user interface (GUI) on top of classes that may be
executed in parallel. Furthermore, the GUI shall be capable not only of creat-
ing and composing objects, but also of creating new subclasses.

Acknowledgments
Michael Thuné, for invaluable guidance. Jarmo Rantakokko and Peter Ols-
son, for valuable support, and Lotta Olsson for appreciated contributions. I
thank you, and all other friends that continue to motivate me. Especially Åsa.

37
 References
[1] K. Åhlander, Objects for easy construction and modification of PDE
solvers, presented at POOMA’96, Santa Fe, New Mexico, February
28 - March 1, 1996.

[2] J. Ambrosiano et. al., Data archetypes for the fusion of parallel simu-
lation codes in climate modeling and other applications, presented at
POOMA’96, Santa Fe, New Mexico, February 28 - March 1, 1996.

[3] E. Anderson et. al. Lapack users’ guide, SIAM, 1992.

[4] R. Armstrong, An illustrative example of frameworks for parallel

computing, presented at POOMA’96, Santa Fe, New Mexico, Febru-
ary 28 - March 1, 1996.

[5] G. Booch Object-oriented analysis and design with applications, Ben-

jamin/Cummings, Redwood City, 1994.

[6] G. Booch, J. Rumbaugh, Unified Method for object-oriented develop-

ment Documentation set, Version 0.8, Rational Software Corporation,
1995.

[7] D. L. Brown, G. Chesshire, W. Henshaw, Getting started with CMP-

GRD: Introductory user’s guide and reference manual, Los Alamos
Unclassified Report LA-UR-89-1294.

[8] J O. Coplien Advanced C++ programming styles and idioms, Addi-

son–Wesley, Reading, 1994.

[9] L. Curfman McInnes et. al., PETSc: Meeting the challenge of large-
scale applications, presented at POOMA’96, Santa Fe, New Mexico,
February 28 - March 1, 1996.

[10]B. Engquist, A sample of time dependent partial differential equa-

tions, Internal report 85-02, Dept of Scientific Computing, Uppsala
University, Uppsala, 1985.

[11]G. H. Golub, J. M. Ortega, Scientific computing and differential equa-

tions, Academic Press, Boston, 1992.

[12]B. Gustafsson, H-O Kreiss, J. Oliger, Time dependent problems and

38
 difference methods, John Wiley & Sons, New York, 1995.

[13]W. Henshaw et. al. Private communication.

[14]I. Jacobsson et. al. Object-oriented software engineering – A use case

driven approach, Addison–Wesley, Wokingham, 1994.

[15]W Joosen et. al., Concurrent programs in CORRELATE: Scientific

simulations with varying granularity, presented at POOMA’96, Santa
Fe, New Mexico, February 28 - March 1, 1996.

[16]T. Korson, J. D. McGregor, Understanding object-oriented: A unify-

ing paradigm, Communications of the ACM, September, 33 (1990),
pp. 40 -60.

[17]H. P. Langtangen: Diffpack: Software for partial differential equa-

tions, OON-SKI 94, Proceedings of the Second Annual Object-ori-
ented Numerics Conference, Sunriver, Oregon, 1994.

[18]P. Olsson and J. Rantakokko, M. Thuné, Software tools for parallel

CFD on composite grids, in Parallel Computational Fluid Dynamics–
Implementation and Results using Parallel Computers (A Ecer et.al.,
Eds.), Elsevier Science B. V., Amsterdam, 1996

[19]B. Meyer, Object-oriented software construction, Prentice Hall, New

York, 1988.

[20]R Pandey, J. C. Browne, Support for extensibility and re-usability in

CYES+, presented at POOMA’96, Santa Fe, New Mexico, February
28 - March 1, 1996.

[21]J. Rantakokko Object-oriented software tools for composite-grid

methods on parallel computers, Report 165, Dept. of Scientific Com-
puting, Uppsala University, Uppsala, 1995.

[22]J. V. Reynders et. al., POOMA: a framework for scientific simulation

on parallel architectures.
Avaliable on Internet, http://www.acl.lanl.gov/PoomaFramework/

[23]A. Reverchon and M. Ducamp, Mathematical software tools in C++,

Wiley and Sons, Chichester, 1993.

[24]A. D. Robison, The abstraction penalty for small objects in C++, pre-
sented at POOMA’96, Santa Fe, New Mexico, February 28 - March 1,

39
 1996.

[25]J. Rumbaugh et. al. Object-oriented modeling and design, Prentice

Hall, Englewood Cliffs, 1991.

[26]J. Rumbaugh, OMT : The object model, Journal of object-oriented

programming, January, 7 (1995) pp. 21-27.

[27]J. Rumbaugh, OMT : The dynamic model, Journal of object-oriented

programming, February, 7 (1995) pp. 6-12.

[28]J. Rumbaugh, OMT : The functional model, Journal of object-ori-

ented programming, March/April 7 (1995) 10-19.

[29]V. Singhal, S. Kakkad, P. R. Wilson, Texas: An efficient, portable per-

sistent store. In Persistent Object Systems: Proceedings of the Fifth
International Workshop on Persistent Object Systems, pp. 11-33, San
Miniato, Italy, september 1992.

[30]O. Strandberg, Persistent objects in Cogito. Internal Report No. 95-

11, Dept. of Scientific Computing, Uppsala University, Uppsala,
1995.

[31]D. Taylor Object-oriented tecnology: A managers guide, Addison-

Wesley, Reading, 1993.

[32]M. Thuné A partitioning algorithm for composite grids, Parallel

Algorithms and Applications, 1 (1993), 69-81.

[33]M. Thuné, Object-oriented software tools for parallel PDE solvers.

Invited paper at the International Conference on Parallel Algorithms
(ICPA ‘95), Wuhan University, October 16-19, 1995.

[34]M. Thuné, K. Åhlander, Towards an expressive language for PDE

solvers, In Programming Languages and Systems–ESOP’96 (H. Niel-
son Ed.), pp.373-386, Springer, Berlin

[35]L. Trefethen, The definition of Numerical Analysis, SIAM News, Nov.

1992, reprinted in Bulletin of the Institute of Mathematics and its
Applications, March/April, 1993.

[36]T. Veldhuizen, K. Ponnambalam, Rapid linear algebra in C++, Dept

of Systems Design Engineering, University of Waterloo, To appear in

40
 Dr. Dobb’s Journal.

[37]I. White, Using the Booch method A rational approach, Benjamin/

Cummings, Redwood, 1994.

[38]R. D. Williams, DIME++: A language for parallel PDE solvers.

Report CCSF-29-92, CCSF, Caltech, Pasadena, 1993.

41
 Appendix A Brief Introduction to Scientific Computing
The intention of this appendix is to survey the application domain. Since the
report is interdisciplinary, some readers may be unfamiliar with scientific
computing. Therefore, we will very briefly explain some concepts that a nu-
merical analyst deals with in order to construct numerical software that
solves a PDE. We will touch upon PDE:s stated on conservative or non-con-
servative form, grids, composite grids, space derivative approximation by fi-
nite differences and time derivative approximation by explicit or implicit
methods. More details can be found in any textbook of scientific computing,
for instance [11].

A.1 What is Scientific Computing?

Golub and Ortega [11] offer the following definition to scientific computing:
“Scientific computing is the collection of tools, techniques, and theories re-
quired to solve on a computer mathematical models of science and engineer-
ing.” In summary, scientific computing is the inter-disciplinary field which
connects mathematics, physics and computing science. A subfield of scien-
tific computing is numerical analysis, defined by L. Trefethen as “the study
of algorithms for the problems of continuous mathematics” [35].
Evidently, we need mathematical formulations of problems from science
and engineering, and we need algorithms for solving the problems. These are
the concepts of our application domain, and they are discussed in the next
sections. Furthermore, we need programs that carry out the algorithms on
computers. As we already have pointed out, the design of these programs is
the focus of this thesis.

A.2 Problems from science and engineering

Computers may be used to solve a variety of problems from science and en-
gineering, but those we are interested in are problems where the mathemati-
cal model is a system of time-dependent partial differential equations, that is
equations expressing that the unknown quantities are depending on their time
and space derivatives. Examples include dispersion of pollution in oceans,
equations for weather predictions, Maxwells equations of the electronic field,
and laws from aerodynamics.
We distinguish between PDE:s written in conservative and non-conserva-
tive form. A PDE in conservative form may be derived from a physical con-
servation law and may be written as ut + f ( u ) x = 0 . Special numerical methods
exist for conservative problems, since they have special physical properties.

42
 A PDE in non-conservative form has the following general form:

u t = F + A 0 u + A 1 u x + ...

Note that a conservative problem may be written in non-conservative form,

but the opposite is not always true.
Besides the problem equations, we need to specify initial conditions and
boundary conditions. It is important that this is done in a consistent and prop-
er way. Otherwise, the problem may be ill-posed, leading to erroneous solu-
tions. See for instance [12] for a thorough treatment on well-posed initial-
boundary-value-problems.

A.3 Grids, Composite grids and Grid Functions

We discretize space in order to solve a continuous problem numerically. The
continous domain is discretized into points that constitute a grid. A grid may
be structured or non-structured. The advantage with non-structured grids is
that they are easy to construct on irregular geometries. However, the disad-
vantage is that the numerical methods that exist for non-structured grids are
slower, since the common operation to find the neighbours of a certain node
is difficult to make efficient. Moreover, in the context of parallel computing,
it is more difficult to partition unstructured grids, even though many efforts
in the finite element or finite volume research address these issues, for in-
stance [38]. The research of the Cogito group focuses on structured grids and
FD (finite difference) methods. FD methods are based on the definition of the
derivative and approximates derivatives at one point with values from neigh-
bouring points. Thus, FD methods can use the structure of the grid in order to
rapidly find the neighbours, and for parallel architectures accurate partition
algorithms can be derived that yield even load balance [32]. In order to deal
with difficult geometries, it is common to use overlapping grids, as seen in
Figure 12. Software that constructs overlapping grids exists, for instance [7]
The grid represents the nodes of the discretization, but an abstraction
which represents the physical entities actually represented in the problem is
also needed. The grid function serves as such an abstraction, which holds one
or more values in every point of the grid. (Sometimes, this concept is called a
field [22,2].)

43
 Grids and grid functions are closely related, and they are important con-
cepts of the application domain.

Figure 12. Example of an overlapping grid.

A.4 Time Stepping

The grids are used to discretize in space. The normal way to discretize in
time is by viewing the grid functions as representing the physical entities on
certain discrete time levels. The overall purpose of our program will be to
calculate the grid function on the next time level, given the grid function on
the current time level and maybe some previous levels. Compare with the
sketched algorithm in Section 2.1
With the time discretized in this way, it is natural to calculate approxima-
tions to the space derivatives first, and thereafter the time derivatives. This
technique–called method of lines (MOL)– is often useful, because it sepa-
rates the algorithm into two parts, thus making it possible to improve the nu-
merical method in the part of the algorithm where it is needed the most. Also,
from the perspective of the time derivative approximation, we may view the
time discretization as an ODE (ordinary differential equation) instead of a
PDE, and theory from this field of scientific computing may be used.
Some numerical methods for solving PDE:s address the time and space de-
rivatives simultaneously for subsequently advancing the solution. In Section
3.7, methods of this kind are considered.
When advancing the solution in time, explicit or implicit time stepping
may be used. Explicit time stepping expresses the solution on the new time
level uniquely as a function of data from previous time levels, and is there-
fore straightforward to implement. The disadvantage is that in order to get

44
stable solutions, very small time steps need to be used. Implicit methods on
the other hand express the solution on the new time level as depending on it-
self as well as on previous time levels. This leads to a linear system of equa-
tions, which has to be solved in each step. Thus more work is required in
each step, but on the other hand longer time steps are allowed. (This far, the
Cogito group has concentrated on explicit methods, but research on tools for
implicit methods has been initiated.)

45
 Appendix B Brief Introduction to Objects
Since this report is interdisciplinary, we devote this Appendix to a brief intro-
duction on objects and OO methodologies, which some readers might be un-
familiar with. For a more thorough explanation of the subject we refer to any
book on object-orientation, for instance [5,14,25,31].

B.1 Object-oriented Concepts

In recent years, OO methodologies have become dominating on the software
arena. As mentioned in Section 2.2, the main difference between OO soft-
ware construction and traditional techniques is that an OO solution is centred
around the important data of the problem whereas the traditional techniques
focus on the algorithms. Adantages include a more conceptual model of the
real world, and it allows the designer to focus on the important aspect of data
before algorithm.
Then, what is OO software? The most important concept is the object,
which represents a relevant data abstraction either from the real world or
from the implementation domain. The conceptual similarities between ob-
jects in the software model and real-world objects is a key to explain the suc-
cess of OO software construction. This is enhanced by program constructs
which model relationships between objects. As we can speak of an aeroplane
as being composed of wings, body, engines, etc., we may relate objects in ag-
gregationships, a part-of relation.
An object has three features: behaviour, data and identity. An essential fea-
ture is that behaviour and data are encapsulated in the same concept, since it
promotes reuse. Furthermore, it makes information hiding possible, which
means that you hide the object’s internal representation (the data) and always
refer to the object via the external interface (the behaviour). This implies that
the representation can change without affecting other parts of the program.
Since all aeroplanes of the same type (Boeing 747, for instance) share the
same behaviour, we group them together in the same class. A unique Boeing
747 is said to be an instance of that class.
The aspect of objects which gives them their special flavour is inheritance.
This mechanism also resembles a real-world abstraction, namely when we
say that there are different kinds of some entity. For instance, we can say that
there exist different kinds of planes, DC-8, Concorde, etc. In an OO model,
we can group together all features that are similar for all types of planes into
one class AeroPlane. We let different kinds of planes inherit from this class,
which gives a model that not only supports code reuse, but also is conceptu-
ally clearer.
Finally, we will comment on polymorphism. Polymorphism allows differ-
ent subclasses to implement their behaviour in appropriate ways depending

46
on their class. For instance, in our aeroplane model we can assume that all
planes share the behaviour to reflect RADAR waves. We introduce an opera-
tion reflect that captures this abstraction. But for a so-called Stealth plane,
the reflection is negligible, and for this subclass we reimplement the opera-
tion yielding no reflection. In our model, we can visualize that the control
tower invokes the operation reflect for all aeroplanes in the air, but due to
polymorphism different methods will be called depending on the actual class
the planes belong to.

B.2 Object-oriented methodologies

Many authors claim that it is not enough to use an OO programming lan-
guage in order to take benefit of the OO technique. It is equally or even more
important to use an OO methodology [31].
A methodology consists of a notation and a process to carry out the soft-
ware development from the specification to the implementation. (Booch adds
tools to be included in the definition of a methodology.)
Several methodologies have been suggested, and among the more well-
known are OMT [25] by Rumbaugh et. al., Booch [5] and Objectory/OOSE
[14] by Jacobsson et. al. This project started off with the intention to follow
OMT, which is described in more detail in the following Appendix, but it has
been influenced from other methodologies too. In fact, the differences be-
tween the models are minor, and the three key authors now work together on
the Unified Method [6]. See below. Still, differences exist and we will briefly
comment some here.
What distinguishes OMT from the other models is the functional model.
Booch for instance, captures algorithmic aspects in the dynamic model.
Jacobsson’s methodology is use case driven, which essentially leads to
systems where the dynamic model plays the most important role throughout
the process, from identifying the objects to the testing of the system.
Booch has the most extensive notation, since six different models are sup-
ported. This includes models for the physical as well as the logical aspects of
the system.
In the Unified Method, Booch and Rumbaugh have come together in an ef-
fort which really has the possibilities of leading to a standard notation. State
of the arts seems to be that the Unified Method does not include notation for
OMT’s functional model, and instead explores Jacobsson’s use case model in
more detail [6]. Notation for programming in the large have also been im-
proved.

47
 Appendix C Brief Summary of OMT
OMT, object-modelling technique, is described in [25]. (The second genera-
tion OMT is described in [26,27,28].) In this Appendix, we give a quick in-
troduction to the models that constitute the methodology and the process for
yielding the models (Section C.1). In Section C.2, we summarize the nota-
tion used in this report.

C.1 OMT models and process

The OMT process addresses mainly the tasks between requirement analysis
and implementation, that is the OO analysis and design. The final product is
an implementation independent design.
In order to decompose the solution process into activities that focus on dif-
ferent parts of the solution, OMT introduces different models:
• The object-model is the most important model and it concentrates on what
data we shall centre our solution around. Also, we seek to structure the
data in a conceptually clear way.
• The dynamic model shall capture the dynamic aspects of the problem,
when things shall happen.
• The functional model shall focus on how the necessary algorithms shall be
carried out.
Since the most important model is the object model, the process usually
starts by making an analysis object model. The prescribed steps include find-
ing classes and objects, finding relations, finding key attributes (data), find-
ing key operations (behaviour). The result is object diagrams.
Continuing with the dynamic models, the steps for defining this are to
identify scenarios, which are refined in event trace diagrams. Relevant class-
es shall be described as state machines in order to capture their dynamic be-
haviour. The output is event trace diagrams and state machine diagrams.
The steps of deriving the third model, the functional model, includes the
identification of input and output, the construction of dataflow diagrams and
the specification of relevant algorithms. These specifications together with
the dataflow diagrams consist the output of the functional analysis.
In the process of deriving all of the three models, entries to a data diction-
ary shall be collected, which describes the relevant abstractions of the prob-
lem.
Characteristic for OO methodologies as opposed to traditional methodolo-
gies is the iterative nature of the process. As we refine each of the above
models, we can add details to the other models, and thus we iterate several
times between the models until we arrive at a final analysis model.
When shifting from analysis to design, it is important that we still are able
to use the same notation. Compared with traditional methods, this is an ad-

48
vantage because it does not introduce a semantic gap [16]. The difference be-
tween analysis and design is, according to Rumbaugh, basically which point
of view you take. In the analysis, you seek for classes that correctly abstract
the problem domain, the real world. In the design, on the other hand, you
study the system from the implementation perspective, and add for instance
classes that implement data structures such as lists.
OMT specifies two phases of design. The first phase, system design, re-
sembles the traditional system design stage, where you take into account the
physical aspects of how the software shall be split, concurrency issues, which
type of control to use (parallel, event driven or procedure driven), persistency
aspects etc.
In the second phase, the object design, you further refine the three models
that the analysis yielded. Implementation classes are added, associations are
detailed, operation interfaces are prescribed. The final product shall be a re-
fined object model, dynamic model and functional model, with emphasise on
how the object model is detailed to be consistent with the other models.

C.2 Notation
Below, we present a short summary of the notation used in this report. For
the purposes of this report, we have only used basic concepts from the object
model and the dynamic model. even if we during the process have used more
details.
Figure 13 shows the object diagram notation. The edge of the triangle
points at the (possibly) abstract ancestor A, which the concrete descendant B
inherits from. The ellipsis notation indicates that more subclasses may be
added. Further, C is an aggregate, which has several objects of class A. (In
OMT, the correct symbol for many is a solid ball. To simplify, and to avoid
confusing readers familiar with Booch notation, we use the letter n to illus-
trate many.) Finally, a relation is shown between C and D.

A C
n

B
...
Figure 13. Object diagram constructs

49
 An instance diagram shows relations between objects, which sometimes il-
lustrate something more clearly. In Figure 14, an instance of class C has a
link to an instance of class D.

(C) (D)

Figure 14. Instance diagram

A state diagram is shown in Figure 15 In this report , we have only used the
simplest constructs illustrating initial state (solid ball), states (ellipses) and
events.

Initial State State 2

Figure 15. Simple state diagram

50