Send mail to:             for the digests or bakeoff
         for comments or help
Anonymous ftp repository: (
Current editor:  Craig Douglas

WWW Sites: or

Today's editor:  Craig Douglas (

Volume 13, Number 8 (approximately August 31, 2003)

Today's topics:

     Adding Preprint/Code Reference to MGNet
     New Book "Matrix-Based Multigrid" (Kluwer)
     New Book at SIAM on Parallel Elliptic PDE Solving
     Workshop in Graz
     Workshop on Adaptive Parallel Computing
     Postdoctoral Position at University of Kentucky


Date: Thu, 21 Aug 2003 15:46:33 -0500
From: Scott Hawley 
Subject: Adding Preprint/Code Reference to MGNet

I am writing to inform you of a paper written by myself and a colleague.

    Title: Tips for implementing multigrid methods on domains containing holes
    Authors: Scott H. Hawley,  Richard A. Matzner
    Comments: 18 pages, 11 figures, LaTeX

Abstract:  As part of our development of a computer code to perform 3D
"constrained evolution" of Einstein's equations in 3+1 form, we discuss issues
regarding the efficient solution of elliptic equations on domains containing
holes (i.e., excised regions), via the multigrid method.  We consider as a
test case the Poisson equation with a nonlinear term added, as a means of
illustrating the principles involved, and move to a 3-dimensional problem
similar to the Hamiltonian constraint that arises in black hole data setting.
Using our vertex-centered multigrid code, we demonstrate that it is possible
to obtain globally second-order accurate solutions of elliptic equations over
domains containing holes, in two and three spatial dimensions.  Keys to the
success of this method are the choice of the restriction operator near the
holes and definition of the location of the inner boundary.  In some cases
(e.g.  two holes in two dimensions), more and more smoothing may be required
as the mesh spacing decreases to zero; however for the resolutions currently
of interest to many numerical relativists, it is feasible to maintain
second-order convergence by concentrating smoothing (spatially) where it is
needed most.  This paper, and our publicly available source code, are intended
to serve as semi-pedagogical guides for those who may wish to implement
similar schemes.

    Other formats:

I also have a publicly available, fairly simple and fairly well documented
Fortran code which illustrates the principles involved.  This is available at

You are welcome to link to this under "Free Software" if you like, however I
have no preference as to whether you do this or not.  If you do, I suppose it
should be called Robin3D, and there should be a description like "A simple
3D multigrid code (for scalar equations), which handles domains with holes.
For those interested in how to implement such a scheme.  It also implements
Robin outer boundary conditions; hence the name.  Based on a 2D FAS solver by
Matthew Choptuik."

Dr. Scott H. Hawley,  Office RLM 9.206,
Center for Relativity, Dept of Physics              Tel: +1-512-471-5426
Univ. of Texas at Austin, Austin TX 78712 USA       Fax:+1-512-471-0890


Date: Fri, 22 Aug 2003 00:57:04 +0300 (IDT)
From: Yair Shapira 
Subject: New Book "Matrix-Based Multigrid" (Kluwer)

Matrix-Based Multigrid 
Theory and Applications 

by Yair Shapira 
Computer Science Dept., Technion, Haifa, Israel


This book is an introduction and analysis of the multigrid approach for the
numerical solution of large sparse linear systems arising from the 
discretization of elliptic partial differential equations. It gives special
attention to the powerful matrix-based-multigrid approach, which is 
particularly useful for problems with variable coefficients and nonsymmetric
and indefinite problems. The approach used here applies not only to model 
problems on rectangular grids but also to more realistic applications with 
complicated grids and domains and discontinuous coefficients. The discussion
draws connections between multigrid and other iterative methods such as 
domain decomposition. The theoretical background provides insight about the
nature of multigrid algorithms and how and why they work. The theory is 
written in simple algebraic terms, and therefore, requires preliminary 
knowledge only in basic linear algebra and calculus. 

Audience: Researchers, engineers, students, and others who are interested 
in the numerical solution of partial differential equations.

Kluwer Academic Publishers, Boston
Hardbound, ISBN 1-4020-7485-9 July 2003,  248 pp.
EUR 117.00 /  USD 115.00 /  GBP 74.00


Chapter 1: The Multilevel--Multiscale Approach

The Multilevel--Multiscale Concept, The Integer Number, The Division Algorithm,
The Greatest-Common-Divider Algorithm, Multilevel Refinement, Examples from
Computer Science, Self Similarity, The Wavelet Transform, Mathematical 
Induction and Recursion, The Product Algorithm, Preliminary Notations and 
Definitions, Application to Pivoting, The Fourier Transform


Chapter 2: PDEs and Discretization Methods

Standard Lemmas about Symmetric Matrices, Elliptic Partial Differential 
Equations, The Diffusion Equation, The Finite-Difference Discretization Method,
Finite Differences for the Poisson Equation, The Finite-Volume Discretization 
Method, The Finite-Element Discretization, Structured and Unstructured Grids

Chapter 3: Iterative Linear-System Solvers

Iterative Sparse-Linear-System Solvers, The Jacobi, Gauss-Seidel, and Kacmarz
Relaxation Methods, Reordering by Colors, Cache-Oriented Reordering, Symmetric
Gauss-Seidel Relaxation, The Preconditioned Conjugate Gradient (PCG) Method,
Incomplete LU Factorization (ILU), Parallelizable ILU Relaxation, 
Parallelizable Gauss-Seidel Relaxation

Chapter 4: Multigrid Algorithms

The Two-Grid Method, The Multigrid Method, Geometric Multigrid,
Matrix-Based Multigrid, Algebraic Multigrid


Chapter 5: The AutoMUG Method

Properties of the AutoMUG Method, Cyclic Reduction, The 2-D Case,
The AutoMUG Method, The AutoMUG(q) Method

Chapter 6: Applications in Image Processing

The Denoising Problem, The Denoising Algorithm for Grayscale Images,
The Denoising Algorithm for RGB Color Images, Examples

Chapter 7: The Black-Box Multigrid Method

Definition of BBMG, Application to Problems with Discontinuous Coefficients

Chapter 8: The Indefinite Helmholtz Equation

The Helmholtz Equation, Adequate Discretization of the Indefinite Helmholtz
Equation, Definition of BBMG2, Computational Two-Level Analysis,
Multiple Coarse-Grid Corrections, The Size of the Coarsest Grid,
Numerical Examples

Chapter 9: Matrix-Based Semi-Coarsening

Flow of Information in Elliptic Problems, Sequential Block-ILU Factorization,
The Domain Decomposition Solver, Reordered Block-ILU Factorization,
Matrix-Based Semi-Coarsening Multigrid Method, A Deblurring Problem


Chapter 10: Matrix-Based Multigrid for Locally Refined Meshes

Locally Refined Meshes, Multigrid and Hierarchical-Basis Linear-System Solvers,
The Two-Level Method, Matrix-Induced Inner Products and Norms,
Properties of the Two-Level Method, Isotropic Diffusion Problems,
The Multi-Level Method, Upper Bound for the Condition Number,
The V(1,1), AFAC, and AFACx Cycles, Scaling the Coefficient Matrix,
Black-Box Multigrid Version for Semi-Structured Grids, Conclusions


Chapter 11: Domain Decomposition

Advantages of the Domain Decomposition Approach,
The Domain Decomposition Multigrid Method, Upper Bound for the Condition
Number, High-Order Finite-Element and Spectral-Element Schemes

Chapter 12: Algebraic Multilevel Method

The Need for Algebraic Multilevel Methods, The Algebraic Multilevel Method,
Properties of the Two-Level Method, Properties of the Multilevel Method,
Upper Bound for the Condition Number, Adequate Discretization of Highly
Anisotropic Equations, Application to the Maxwell Equations,
The Convection-Diffusion Equation, The Approximate-Schur-Complement Method,
Towards Semi-Algebraic Multilevel Methods

Chapter 13: Conclusions

Appendix A: C++ Framework for Unstructured Grids


Date: Fri, 29 Aug 2003 10:03:21 +0200
From: Gundolf Haase 
Subject: New Book at SIAM on Parallel Elliptic PDE Solving

The following book is available now:

    Craig C. Douglas, Gundolf Haase, and Ulrich Langer:
    "A Tutorial on Elliptic PDE Solvers and Their Parallelization",
    SIAM Series Software, Environments, and Tools, 2003, ISBN 0-89871-541-5

This tutorial serves as a first introduction into the basic concepts of
solving partial differential equations using parallel numerical methods.

The ability to understand, develop, and implement parallel PDE solvers
requires not only some basic knowledge in PDEs, discretization methods, and
solution techniques, but also some knowledge about parallel computers,
parallel programming, and the run-time behaviour of parallel algorithms.

Our tutorial provides this knowledge in just 8 short chapters.  The authors
kept the examples simple so that the parallelization strategies are not
dominated by technical details.  The practical course for the tutorial can be
downloaded from the internet, see

Gundolf Haase


Date: Tue, 02 Sep 2003 10:30:30 +0200
From: Alfio Borzi 
Subject: Workshop in Graz

Dear Collegues,

We would like to inform you that the program of the Workshop
Advances in Numerical Algorithms is now ready. Please have a look
at the homepage

Alfio Borzi  and Karl Kunisch

                   Advances in Numerical Algorithms Program


8:00-9:00                   Registration  
9:00-9:30   K. Kunisch      Welcome & Opening  
9:40-10:10  S.G. Nash       Model problems for the multigrid optimization
                            of systems governed by differential equations
10:40-11:10 F. Rendl        Computational experience with large-scale
                            semidefinite programming problems
11:20-11:50 S.I. Petrova    Mesh adaptivity methods for shape optimization
12:00-12:30 B. Vexler       A posteriori error estimation for finite
                            element discretization of parameter
                            identification problems
14:30-15:00 A. Kunoth       Adaptive wavelets methods for
                            semilinear-quadratic control problems
15:10-15:40 M. Hinze        A new discretization concept in control
                            constrained pde control and its numerical
16:10-16:40 G. Stadler      Semi-smooth Newton and augmented Lagrangian
                            methods for friction and contact problems
16:50-17:20 B. Kaltenbacher Material parameter identification of
                            piezoelectricity and magnetics


9:00-9:30   C. Pflaum       Advances in the numerical simulation of lasers
9:40-10:10  M. Wabro        Coupled algebraic multigrid methods for the
                            Navier-Stokes equations
10:40-11:10 K. Mikula       Finite volume methods in image smoothing and
11:20-11:50 S. Keeling      Image registration and interpolation by
                            optical flow with maximal rigidity
12:00-12:30 I. Yavneh       Multi-level algorithms for some
                            image-processing problems
14:30-15:00 C.C. Douglas    Virtual telemetry for dynamic data-driven
                            application simulations
15:10-15:40 S. Ta'asan      Multiscale modeling of biological networks
16:10-16:40 G. Haase        A two level recursive calculation of coarse
                            matrices in AMG
16:50-17:20 U. Ruede        Adaptive PDE solvers for supercomputers


9:00-9:30   B. Basara       Turbulence modelling from the perspective of
                            the commercial CFD
9:40-10:10  A. Valli        Mixed and 'hybrid' finite element
                            approximation of eddy-current problems
10:40-11:10 W. Hackbusch    The efficient numerical treatment of the
                            matrix equation of Ljapunov and Riccati type
11:20-11:50 C. Gaspar       Fast interpolation techniques and meshless
12:00-12:30 B. Wohlmuth     Domain decomposition techniques based on
                            fictious domains
14:30-15:00 C. Schmeiser    Models for the chemosensory movement of
15:10-15:40 E. Weinmueller  Numerical solution of singular boundary value
                            problems in ODEs.
16:10-16:40 V. Schulz       Simultaneous optimization in applications
16:50-17:20 J. Schoeberl    Multigrid preconditioning for parameter
                            dependent problems


9:00-9:30   G. Wittum       tba
9:40-10:10  A. Arnold       Transparent boundary conditions for
10:40-11:10 L. Blank        Wavelet and Schur complement based
                            preconditioning with an application in state
11:20-11:50 C. Burstedde    Numerical results for a wavelet discretization
                            of a linear-quadratic elliptic control problem
12:00-12:30 F. Lenzen       Automatic detection of gravitational arcs in
                            astronomical data using anisotropic diffusion
                            and segmentation
12:40-13:00                 Closing  


Subject: Workshop on Adaptive Parallel Computing
From: Jochen Hittler 
Date: Thu, 21 Aug 2003 12:16:59 +0200

                   Workshop on Adaptive Parallel Computing
                            November 9 - 12, 2003
                         at Hohenwart Forum, Germany

GAMM Fachausschuss
Scientific Computing
Universitaet Heidelberg
Technische Simulation
STZ Technische Simulation
WiR Baden-Wuerttemberg


    R.E. Bank, San Diego
    P. Bastian, Heidelberg
    H. C. Edwards, Albuquerque
    G. Wittum, Heidelberg

Invited Speakers (tentative)

    H. C. Edwards, Albuquerque
    J. Fuhrmann, Berlin
    M. Holst, San Diego
    K. Kopps, Albuquerque
    S. Lang, Heidelberg
    Z. Mo, Beijing
    M. Parashar, Rutgers/Austin
    V. Reichenberger, Heidelberg
    J.-F. Remacle, Troy
    E. Stein, Hannover
    C. Wieners, Erlangen


    Computational Methods
    Software Tools
    Simulation of Application Problemson Adaptivity and Parallelism

Simulation in science and technology is characterized by increasing model
complexity and studies of full problem configurations.  These trends result in
high demands of computational resources.  Thus advanced computational methods
are necessary to overcome shortcomings.  This workshop focuses on simulation
tools using adaptivity and parallelism in the context of application problems
and will bring together scientists of research and industry to discuss the
state-of-the-art in area of simulation techniques and software tools.


Please find a registration form as pdf-file for download at, topic veranstaltungen.  Address of registration
office below.

Submission of abstracts

Please send your abstract (max 20 lines) by September 10, 2003.  Notice of
acceptance will be given as soon as possible.  All participants, whether
giving a talk or not, have the possibility of sending an abstract of their
work on the topic of the conference.  A collection of abstracts will be
available during the conference.


    Submission of abstracts September, 10th 2003
    Registration            September, 30th 2003
    Payment                 September, 30th 2003

Conference Fee

The conference fee for registration up to September, 30th 2003 is 350,- EUR
including lodging and full board during the conferen ce, admission to all
lectures and conference material.  Financial support is available on request.
For later registration we charge an additional fee of 100 EUR per person
Payments are to be made in EURO by bank transfer:

    STZ Technische Simulation
    reference "workshop apc"
    Deutsche Bank, Heidelberg
    Bank code 672 700 03 Account nr 0153 114

Registration Office

    IWR -Technical Simulati
    Im Neuenheimer Feld 368
    D- 69120 Heidelberg
    phone: ++49 (0) 6221 54 88 -66 or -54
    fax: ++49 (0) 6221 54 88 60
    The conference will be announced at

Conference Venue

    Hohenwart Forum Conference Center
    Schoenbornstr. 25
    75181 Pforzheim - Hohenwart
    phone ++49 (0) 7234 606 0
    fax ++49 (0) 7234 606 46

You will reach Hohenwart by car, if you take Motorway A8 to the exit Pforzheim
Ost.  Follow the signposts to Calw.  When you leave Pforzheim southbound, you
will see the restaurant Kupferhammer on the left hand side.  After hundred
meters you take the next turn left and go up the hill to Huchenfeld and
Hohenwart.  When you enter Hohenwart, turn left behind the cemetery, then left
again and you are at Hohenwart Forum.

If you arrive at one of the airports, you take the train to Pforzheim, leave
the station and walk to busstop Busbahnhof Sued (100m).  The bus connecting
Pforzheim with Hohenwart has number 742 (travel-agency Schuhmacher).  You will
recieve a timetable for the trains and busses after you have registered.  A
taxi from Pforzheim station to Hohenwart will cost 20 EUR.


Date: Sun, 31 Aub 2003 10:22:21 -0400
From: Craig Douglas 
Subject: Postdoctoral Position at University of Kentucky

I have an immediate opening for a postdoctoral fellow as part of a new NSF
funded project on dynamic data-driven application simulation (DDDAS) for
wildland fire modeling.  This is joint project with well known researchers at
the University of Colorado-Denver, National Center for Atmospheric Research,
Rochester Institute of Technology, and Texas A&M.  Funding is expected for
up to four years.

The successful candidate must have

1) a Ph.D. in a relevant field (computer science preferred)
2) sound computational science experience
3) working knowledge of Fortran and C++
4) parallel or Grid computing experience

Please send a CV (pdf or Word formats) and cover material by email to me at

with "DDDAS Postdoc Position" in the subject line.

The University of Kentucky is an equal opportunity/affirmative action
employer, and especially encourages applications from women and minorities.


End of MGNet Digest