Skip to main content
main-content

Über dieses Buch

13. 2 Abstract Saddle Point Problems . 282 13. 3 Preconditioned Iterative Methods . 283 13. 4 Examples of Saddle Point Problems 286 13. 5 Discretizations of Saddle Point Problems. 290 13. 6 Numerical Results . . . . . . . . . . . . . 295 III GEOMETRIC MODELLING 299 14 Surface Modelling from Scattered Geological Data 301 N. P. Fremming, @. Hjelle, C. Tarrou 14. 1 Introduction. . . . . . . . . . . 301 14. 2 Description of Geological Data 302 14. 3 Triangulations . . . . . . . . 304 14. 4 Regular Grid Models . . . . . 306 14. 5 A Composite Surface Model. 307 14. 6 Examples . . . . . . 312 14. 7 Concluding Remarks. . . . . 314 15 Varioscale Surfaces in Geographic Information Systems 317 G. Misund 15. 1 Introduction. . . . . . . . . . . . . . . 317 15. 2 Surfaces of Variable Resolution . . . . 318 15. 3 Surface Varioscaling by Normalization 320 15. 4 Examples . . . 323 15. 5 Final Remarks . . . . . . . . . . . . . 327 16 Surface Modelling from Biomedical Data 329 J. G. Bjaalie, M. Dtllhlen, T. V. Stensby 16. 1 Boundary Polygons. . . . . . . . . . . 332 16. 2 Curve Approximation . . . . . . . . . 333 16. 3 Reducing Twist in the Closed Surface 336 16. 4 Surface Approximation. 337 16. 5 Open Surfaces. . . . 339 16. 6 Examples . . . . . . 340 16. 7 Concluding Remarks 344 17 Data Reduction of Piecewise Linear Curves 347 E. Arge, M. Dtllhlen 17. 1 Introduction. . . . . . . . . . . 347 17. 2 Preliminaries . . . . . . . . . . 349 17. 3 The Intersecting Cones Method 351 17. 4 The Improved Douglas Method 353 17. 5 Numerical Examples . . . . . . 360 17. 6 Resolution Sorting . . . . . . . . . . . . . . . . . . 361 18 Aspects of Algorithms for Manifold Intersection 365 T. Dokken 18. 1 Introduction . . . . . . . . . . . . . . . 365 18. 2 Basic Concepts Used . . . . . . . . . .

Inhaltsverzeichnis

Frontmatter

Numerical Software Tools

Frontmatter

1. Object-Oriented Numerics

Abstract
This chapter is concerned with the use of object-oriented programming techniques for numerical applications, especially in terms of the computer language C++. Through a series of examples we expose some of the strengths and possibilities of object-oriented numerics.
Erlend Arge, Are Magnus Bruaset, Hans Petter Langtangen

2. Basic Tools for Linear Algebra

Abstract
In this chapter we discuss how object-oriented techniques can be applied in the design and implementation of a software library for linear algebra computations.
Are Magnus Bruaset, Hans Petter Langtangen

3. Software Tools for Modelling Scattered Data

Abstract
This chapter concerns itself with the problem of designing numerical software for the approximation of scattered data. By utilizing object oriented techniques in the C++ programming language we show how to construct flexible interfaces to the user’s data and generic interfaces to surface approximation methods. We exemplify by using the scattered data modelling tool Siscat.
Erlend Arge, Øyvind Hjelle

4. A Comprehensive Set of Tools for Solving Partial Differential Equations; Diffpack

Abstract
This chapter presents an overview of the functionality in Diffpack, which is a software environment for the numerical solution of partial differential equations. Examples on how object-oriented programming techniques are applied for software design and implementation are provided. In addition, we present a collection of sample Diffpack applications.
Are Magnus Bruaset, Hans Petter Langtangen

5. On the Numerical Efficiency of C++ in Scientific Computing

Abstract
We investigate the relative efficiency of C++ and C code versus FORTRAN 77 code through numerical experiments conducted on a range of computer platforms. The problem areas cover basic linear algebra and finite element solution of porous media fluid flow and species transport problems. The C++ codes are short and make extensive use of Diffpack, a generic library based on object-oriented programming techniques, while the FORTRAN and C programs are either based on vendor supplied numerical libraries or written and tuned particularly for the test problem. Challenges encountered in optimizing C++ codes and the efficiency of dynamic memory handling in C++ are also addressed.
Differences in computational efficiency observed for the problem areas studied were small, and tended to be problem dependent. Based on our experience with optimizing C++ code, we conclude that the use of object-oriented techniques should be confined to high-level administrative tasks, while CPU intensive numerics should be implemented using low-level C code and carefully constructed for-loops.
Erlend Arge, Are Magnus Bruaset, Phillip B. Calvin, Joseph F. Kanney, Hans Petter Langtangen, Cass T. Miller

Partial Differential Equations

Frontmatter

6. Basic Equations in Eulerian Continuum Mechanics

Abstract
We present a general framework applicable to several mathematical models in continuum mechanics. Particularly, we demonstrate that mass, momentum and energy balancing along with appropriate constitutive laws, form the basis of a broad class of boundary value problems for macroscopic motion of a solid, fluid, gas and mixture of several media. We also point out the similarities in the final governing equations and the resulting advantage of this when constructing numerical solution methods.
Finally, we derive closed mathematical models that cover the following fields: heat transfer, solute transport, potential fluid flow (including water surface waves), turbulence, elastic and viscoplastic deformations and multiphase porous media flow.
We believe that a unified view like the one presented here enhances the fundamental understanding and supports the development of generic solution methods and software for continuum mechanical problems.
Einar Haug, Hans Petter Langtangen

7. A Mathematical Model of Macrosegregation Formation in Binary Alloy Solidification

Abstract
The purpose of this chapter is to introduce a mathematical model of binary alloy solidification. A binary alloy solidifies over a temperature range, giving rise to a mushy zone in which liquid and solid coexist. The modelling of the liquid and solid zones are straightforward using well known continuum mechanical models. In order to model the mushy zone volume averaging techniques are applied. The volume averaged liquid and solid equations are combined to give a mixture formulation of the differential equations. In addition, suitable constitutive relations are introduced to give a closed model.
Einar Haug, Torgeir Rusten, Håvard J. Thevik

8. Computation of Macrosegregation due to Solidification Shrinkage

Abstract
A system of partial differential equations and a set of constitutive relation modelling macro segregation development during solidification of a binary alloy is presented. The development of a finite element simulator for the numerical solution of these equations using Diffpack is discussed. In particular we consider the solution of systems of PDEs using object oriented programming techniques.
Asbjørn Mo, Torgeir Rusten, Håvard J. Thevik

9. A Mathematical Model for the Melt Spinning of Polymer Fibers

Abstract
We derive a quasi one-dimensional mathematical model for the free surface flow of thin polymer fibers undergoing phase changes. The model is based on averaging the mass and momentum balance equations, while the energy equation is kept in the standard form. Various constitutive laws are introduced for crystallization kinetics, temperature and strain-rate dependent viscosity, air friction and heat transfer coefficients in cooling laws. Emphasis is put on the many approximations in the model. The resulting system of algebraic equations, partial differential equations and ordinary differential equations is solved numerically. We show how the numerical simulations can be used for fitting parameters in an empirical crystallization model.
Erik Andreassen, Elisabeth Gundersen, Einar L. Hinrichsen, Hans Petter Langtangen

10. Finite Element Methods for Two-Phase Flow in Heterogeneous Porous Media

Abstract
A mathematical model for the simultaneous flow of oil and water in porous rock formations is considered. The elliptic pressure equation and the hyperbolic saturation equation are discretized by various finite element methods of streamline diffusion type in space, and by finite differences in time. The main purpose of the chapter is to examine different solution strategies in four flow cases involving porous formations with different type of heterogeneities in absolute and relative permeability as well as in porosity. Fully implicit methods represent the most robust and reliable solution approach in challenging flow cases. Simpler solution strategies may, however, be satisfactorily robust and more efficient in problems with less severe heterogeneities.
Elisabeth Gundersen, Hans Petter Langtangen

11. Splines and Ocean Wave Modelling

Abstract
The chapter introduces spline functions as approximants in the approximate solution of differential equations. These solutions are continuous and accurate such that results can be evaluated anywhere within the solution domain. The details of this method for solving differential equations are worked out for an example of great practical importance: The fully nonlinear equations of water waves.
Even Mehlum

12. Krylov Subspace Iterations for Sparse Linear Systems

Abstract
This chapter is concerned with efficient methods for iterative solution of large sparse systems of linear equations, typically derived from the discretization of an elliptic boundary value problem. In particular, attention is given to the family of Krylov subspace methods, as well as to several preconditioning strategies that are suitable for improving the convergence rates of such iterations.
Are Magnus Bruaset

13. Preconditioning Linear Saddle Point Problems

Abstract
In this paper we discuss how certain saddle point problems, arising from discretizations of partial differential equations, should be preconditioned in order to obtain iterative methods which converge with a rate independent of the discretization parameters. The results for the discrete systems are motivated from corresponding results for the continuous systems. Our general approach is illustrated by studying Stokes’ problem, a mixed formulation of second order elliptic equations and a variational problem motivated from scattered data approximation.
Torgeir Rusten, Ragnar Winther

Geometric Modelling

Frontmatter

14. Surface Modelling from Scattered Geological Data

Abstract
We present a surface representation format that is well suited for modelling geological horizons containing faults. The composite grid model is a blend of regular grid and triangulation based surface models. Finally, we show the improvement when using this composite grid compared to the use of a regular grid model when both are applied to the same real data set.
Nils P. Fremming, Øyvind Hjelle, Christian Tarrou

15. Varioscale Surfaces in Geographic Information Systems

Abstract
This chapter focuses on the problem of approximating spatial objects to obtain optimal fidelity. In geographic information systems (GIS), the scale problem is far more encompassing and complicated than in traditional cartography. The concept of varioscale surfaces is introduced by considering approximated surfaces with spatially varying tolerances. The motivation for varioscaling is briefly discussed, and a general strategy for applying the concept on TIN surfaces is presented. A key element of the strategy is to simplify the problem by using the tolerance surface to normalize the TIN surface. Two examples are presented: a feature based approximation, and a viewpoint dependent approximation.
Gunnar Misund

16. Surface Modelling from Biomedical Data

Abstract
In the present chapter, we present a method for modelling smooth surfaces on the basis of stacks of boundaries taken from serial sections. We also present a method for automatically defining the outer closed boundary of tight clusters of points; the defined boundaries are in turn used for a surface modelling. We exemplify the use of our methods with material of physical sections from the field of experimental brain research. The surfaces modelled represent the exterior of the brain, internal regions, and zones containing specifically labelled tissue elements coded as point clusters.
Jan G. Bjaalie, Morten Dæhlen, Trond Vidar Stensby

17. Data Reduction of Piecewise Linear Curves

Abstract
We present and study two new algorithms for data reduction or simplification of piecewise linear plane curves. Given a curve P and a tolerance ε ≥ 0, both methods determine a new curve Q, with few vertices, which is at most e in Hausdorff distance from P. The methods differ from most existing methods in that they do not require a vertex in Q to be a vertex in P. Several examples are given where we show that the methods presented here compare favorably to other methods found in the literature. We also show how the vertices of a curve can be reordered so that the first, say n, vertices of the reordered sequence form an approximation to the curve itself.
Erlend Arge, Morten Dæhlen

18. Aspects of Algorithms for Manifold Intersection

Abstract
The implementation of intersection algorithms is in most cases tailored to the use of specific methods for geometry representation and to the specific needs in a given application. As the computers grow more and more powerful, the ability to solve complex intersection problems are improved. Thus better understanding of intersection algorithms independent of the dimension of the objects being intersected and the dimension of the space in which the objects lie, will simplify the development of new intersection algorithms. To contribute to this we will in this chapter address some topics that are central when new intersection algorithms are to be developed. The first of these is a generic structure for intersection algorithms, then the handling of intersection tolerances is addressed followed by strategies for identifying intersections. The final topic addressed is conditions that ensure that no internal loops exist in the intersection of smooth manifolds.
Tor Dokken

19. Surface Editing

Abstract
Various surface interrogation tools provide useful information about the quality of surfaces. However, when these tools reveal a problem in a surface, the need for modification of the surface arises. We present a method for surface editing using a certain class of smoothing techniques.
Even Mehlum, Vibeke Skytt

Backmatter

Weitere Informationen