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

World Wide Web: or

Today's editor:  Craig Douglas (

Volume 11, Number 3 (approximately March 31, 2001)

Today's topics:

     Pieter Wesseling Multigrid Book Project Finished
     ETH Domain Decomposition Workshop Announcement
     Copper Mountain Virtual Proceedings
        A Robust and Parallel Multigrid Method for Convection Diffusion
        Multiscale Scientific Computation: Review 2000
        A Two-Level Preconditioner for Anisotropic Mixed Finite Elements
        Achieving Textbook Multigrid Efficiency (2 papers)
        Comparisons of Unstructured Multigrid
        A Hierarchical Domain Decomposition Method
        A Multigrid Approach for Fast Geodesic Active Contours
        Toward the Optimal Preconditioned Eigensolver
        Considerations for Parallel CFD Enhancements
        A Multilevel Preconditioner for Field-Circuit Coupled Problems 
        An Optimal Iterative Method for the Time-Dependent Stokes Problem
     SIAM/EMS Conference Berlin, Sept. 2-6, 2001
     2nd Announcement Meshfree Methods


Date: Sun, 25 Mar 2001 10:15:12 -0500 (EST)
From: Craig Douglas 
Subject: Pieter Wesseling Multigrid Book Project Finished

The book scanning is complete.  Please reference the book through the web page


Date: Sat, 17 Mar 2001 07:35:44 +0100 (MET)
From: Luca Pavarino 
Subject: ETH Domain Decomposition Workshop Announcement

                    Two-day workshop on 


                      June 7-8, 2001
                ETH Zurich, Switzerland. 

Department of Mathematics, University of Milan (
Seminar for Applied Mathematics, ETH Zurich (

  L. Pavarino, University of Milan 
  Ch. Schwab, ETH Zurich 
  A. Toselli, ETH Zurich 
  O. Widlund, Courant Institute 

The following speakers have confirmed their participation:
  Y. Achdou (Paris VII) 
  A. Alonso (University of Milan) 
  Ch. Bernardi (Université Pierre et Marie Curie, Paris) 
  A. Buffa (Istituto di Analisi Numerica, Pavia) 
  M. Dryja (Warsaw University) 
  V. Heuveline (University of Heidelberg) 
  R. Hoppe (University of Augsburg) 
  A. Klawonn (GMD, St. Augustine) 
  C. Lasser (Technical University of Munchen) 
  Y. Maday (Université Pierre et Marie Curie, Paris) 
  F. Nataf (Ecole Polythecnique, Paris) 
  A. Patra (SUNY, Buffalo) 
  L. Pavarino (University of Milan) 
  A. Quarteroni (EPFL and Politecnico di Milano) 
  F. Rapetti (Laboratoires ASCI, Paris) 
  A. Valli (University of Trento) 
  O. Widlund (Courant Institute, New York) 
  B. Wohlmuth (University of Augsburg) 

The main purpose of this workshop is to give an overview of some of the most
recent developments in the field of Domain Decomposition.  We understand
Domain Decomposition in a broad sense as relating to the construction of
preconditioners for the large algebraic systems of equations which often arise
in applications, by solving smaller instances of the same problem.  We also,
most certainly, wish to include studies of methods built from different
discretizations in different subdomains such as in multi-physics models,
mortar finite elements, etc.  The workshop will also allow the participants to
meet informally and give opportunities for people to make new acquaintances.
If you are interested in participating please contact the organizers.

For further information, such as program, hotel, and travel information,
please see


Date: Sat, 31 Mar 2001 23:32:55 -0500 (EST)
From: Craig Douglas 
Subject: Copper Mountain Virtual Proceedings

In this issue are the first set of contributions to the Virtual Proceedings:

There are more that will be in the April newsletter (it is already online and
still growing), which will be mailed April 30th or so.

Participants are still welcome and encouraged to contribute to the virtual
proceedings.  There are no size (other than my disk drive) or page constraints
on the contributions.  Achi's is 96 pages.  Anyone for 100+?


Date: Wed, 28 Mar 2001 11:00:49 +0200
From: Michael Bader 
Subject: Paper on A Robust and Parallel Multigrid Method for Convection Diffusion

A Robust and Parallel Multigrid Method for Convection Diffusion Equations

Michael Bader and Christoph Zenger,
Lehrstuhl fuer Informatik V der TU Muenchen,
80290 Muenchen, Germany


We present a multigrid method for the solution of convection diffusion
equations that is based on the combination of recursive substructuring
techniques and the discretization on hierarchical bases and generating
systems.  Robustness of the resulting method, at least for a variety of
benchmark problems, is achieved by a partial elimination between certain
"coarse grid unknowns."

The choice of these coarse grid unknowns is motivated by the physical
properties of the convection diffusion equation, but is independent of the
actual discretized operator.  The resulting algorithm has a memory requirement
that grows linearly with the number of unknowns.  This also holds for the
computational cost of the setup and the individual relaxation cycles.  We
present numerical examples that indicate that the number of iterations needed
to solve a convection diffusion equation is widely independent of the number
of unknowns and of the type and strength of the convection field.

    Editor's Note: See


Date: Thu, 22 Mar 2001 14:39:01 +0200
From: sarah fliegelmann 
Subject: Paper on Multiscale Scientific Computation: Review 2000

Multiscale Scientific Computation: Review 2000

Achi Brandt
The Weizmann Institute of Science
Rehovot 76100, Israel


Most of the fundamental problems in physics, chemistryand engineering involve
computation too hard even for future supercomputers, if conventional
mathematical approaches are used.  The reason is always a product of several
complexity factors associated with the wide range of space and time scales
characteristic to such problems.  Each of these complexity factors can in
principle be removed by various multiscale algorithms, i.e., employing
separate processing at each scale of the problem, combined with interscale
iterative interactions.  A wide range of multiscale computational methods is
described, emphasizing main ideas and interrelations between various fields.
The reported areas include:  top-efflciency multigrid methods in fluid
dynamics; inverse PDE problems and data assimilation; feedback optimal
control; PDE solvers on unbounded domains and on adaptable grids; wave/ray
methods for highly indefinite equations; rigorous quantitative analysis of
multigrid; many-eigenfunction problems and ab-initio quantum chemistry; fast
evaluation of integral transforms on adaptive grids; multigrid Dirac solvers;
fast inverse-matrix and determinant calculations and updates; multiscale
Monte-Carlo methods in statistical physics, including the renormalization
multigrid (RMG) methods; molecular mechanics (including fast force summation,
fast macromolecular energy minimization, and Monte-Carlo methods at
equilibrium, both for macromolecules and for large ensembles of small
molecules); combination of small-scale equilibrium with large-scale dynamics;
image processing (edge detection and picture segmentation); tomography
(medical imaging and radar reconstruction); efflcient, general and highly
accurate algebraic multigrid (AMG) schemes; fast practical graph algorithms;
data clustering; and multiscale approaches to global optimization.

Research supported by AFOSR and the Materials and Manufacturing Directorate,
AFRL, Wright-Patterson Base, contract No. F33615-97-D-5405, by the European
Offlce of Aerospace Research and Development (EOARD) of the US Air Force,
Contract F61775-00-WE067, by Israel Ministry of Science, Cultureand Sport grant
9680, by Israel Absorption Ministry, Project No. 6682, by Israel Science
Foundation grant No. 696/97, and by the Carl F. Gauss Minerva Center for
Scientific Computation at the Weizmann Institute of Science.

    Editor's Note: See


Date: Mon, 19 Mar 2001 11:01:30 -0600 (CST)
From: Chisup Kim 
Subject: Paper on A Two-Level Preconditioner for Anisotropic Mixed Finite Elements

A Two-Level Preconditioner for an Anisotropic Mixed Finite Element Problem

Chisup Kim
Texas A&M
Department of Methematics
College Station, TX


We study a multilevel preconditioner for the linear system arising from a
mixed finite element approximation of a second order anisotropic elliptic
problem on uniform rectangular and triangular meshes.  This preconditioner
involves smoothing on the mixed problem and the preconditioning of an
auxiliary problem, namely the corresponding finite element problem on the same

    Editor's Note: See


Date: Fri, 30 Mar 2001 18:36:43 -0500
From: Boris Diskin 
Subject: Papers on Achieving Textbook Multigrid Efficiency

General Framework for Achieving Textbook Multigrid Efficiency:
One-dimensional Euler Example

James L. Thomas
Computational Modeling and Simulation Branch
Mail Stop 128
NASA Langley Research Center
Hampton, Virginia 23681

Boris Diskin
Institute for Computer Applications in Science and Engineering
Mail Stop 132C
NASA Langley Research Center
Hampton, Virginia 23681

Achi Brandt
The Weizmann Institute of Science
Rehovot 76100, Israel

Jerry C. South, Jr.
Williamsburg, Virginia 23185


A general multigrid framework is discussed for obtaining textbook efficiency
to solutions of the compressible Euler and Navier-Stokes equations in
conservation law form.  The general methodology relies on a distributed
relaxation procedure to reduce errors in regular (smoothly varying) flow
regions; separate and distinct treatments for each of the factors (elliptic
and/or hyperbolic) are used to attain optimal reductions of errors.  Near
boundaries and discontinuities (shocks), additional local relaxations of the
conservative equations are necessary .  Example calculations are made for the
quasi-one-dimensional Euler equations; the calculations illustrate the general

Key words.  textbook multigrid efficiency, distributed relaxation, Euler

Subject classification.  Applied and Numerical Mathematics

                                  * * * * *

Textbook Multigrid Efficiency for the Incompressible Navier-Stokes Equations:
High Reynolds Number Wakes and Boundary Layers

James L. Thomas
Computational Modeling and Simulation Branch
Mail Stop 128
NASA Langley Research Center
Hampton, Virginia 23681

Boris Diskin
Institute for Computer Applications in Science and Engineering
Mail Stop 132C
NASA Langley Research Center
Hampton, Virginia 23681

Achi Brandt
The Weizmann Institute of Science
Rehovot 76100, Israel


Textbook multigrid efficiencies for high Reynolds number simulations based on
the incompressible Navier-Stokes equations are atained for a model problem of
flow past a finiter rate plate.  Elements of the Full Approximation Scheme
multigrid algorithm, including distributed relaxation, defect correction, and
boundary treatment, are presented for the three main physical aspects
encountered:  entering flow, wake flow, and boundary layer flow.  Textbook
efficiencies, i.e., reduction of algebraic errors below discetization errors
in one full multigrid cycle, are attained for second order accurate
simulations at a laminar Reynods number of 10,000.

Keywords.  incompressible Navier-Stokes equations, textbook multigrid
efficiency, distributiverelaxation, defect-correction iteration

Subject classification.  Applied and Numerical Mathematics

    Editor's Note: See


Date: Mon, 02 Apr 2001 13:31:48 -0400
From: Dimitri Mavriplis 
Subject: Slides on Comparisons of Unstructured Multigrid

Comparisons of Unstructured Multigrid as a Non-linear Solver,
a Linear Solver, or a Pre-Conditioner

Dimitri Mavriplis
NASA Langley Research Center
Hampton, VA 23681


The relative efficiency of an unstructured multigrid algorithm used as a
non-linear solver (FAS) is compared with the efficiency of the equivalent
multigrid algorithm used as a linear solver on a Newton linearization of the
non-linear problem, and with the efficiency obtained using either approach as
a preconditioner for a non-linear GMRES method.  Two types of problems are
examined, the solution of a transient radiation diffusion problem, and the
solution of the Navier-Stokes equations.  In the first case, the
discretization employs a nearest neighbor stencil and the linearized scheme
operates on an exact Newton linearization.  In the second case, the
discretization is based on a second-order form which involves neighbors of
neighbors while the linearization employed is based on a first-order accurate
nearest-neighbor stencil.  For the radiation diffusion case, the linear
multigrid approach is more efficient than the FAS approach, mainly due to the
expense involved in the more frequent computation of the highly non-linear
residuals required in the non-linear multigrid case.  When the linear system
is solved to sufficient tolerance, quadratic convergence of the non-linear
problem is observed.  For the Navier-Stokes equations, quadratic convergence
of the non-linear problem is not possible, since an inexact linearization is
employed.  While a linear multigrid iteration is shown to be substantially
cheaper than the corresponding non-linear multigrid iteration, the relative
performance of both methods depends largely on the tolerance to which the
linear system is solved, and the achievable non-linear convergence rate.
Using either method as a preconditioner rather than as a solver is also shown
to provide additional convergence acceleration.  Other issues such as memory
requirements and robustness of the various schemes will also be discussed.

    Editor's Note: See


Date: Thu, 29 Mar 2001 08:06:09 +0200 (IST)
From: Elena Braverman 
Subject: Paper on A Hierarchical Domain Decomposition Method

A Hierarchical Domain Decomposition Method for the
Solution of Helmholtz and Biharmonic Equations

Moshe Israeli and Elena Braverman
Technion, Computer Science Department, Haifa 32000,

Amir Averbuch
School of Mathematical Sciences,
Tel Aviv University, Tel Aviv 69978, Israel


Implicit discretization of time dependent problems in computational physics,
semiconductor device simulation, electromigration and fluid dynamics often
gives rise to elliptic equations.  Helmholtz type equations usually appear in
acoustics or electromagnetics and also as a result of time discretization of
the Navier-Stokes equations.  Biharmonic problems appear in elasticity and
viscous flows.

We solve the Helmholtz and the biharmonic equation by the Domain Decomposition
(DD) methods.  Previously [1] we adopted a DD method where the equation was
solved in each subdomain with assumed boundary conditions, resulting in jumps
in function or derivative on subdomain boundaries.  These jumps were removed
by the introduction of singularity layers.  In order to account for the global
effect of the layers we computed first the influence of each layer on each
subdomain boundary, taking into account the decay or smoothing out of the
influence as a function of the distance from the layer.  To reduce the
communication load, compression in a multiwavelet basis was applied.
Nevertheless, this part of the procedure can become expensive as the number of
subdomains grows considerably.  An algorithm for a fast solution of the
Poisson equation by decomposition of the domain into square domains and the
subsequent matching of these solutions by the fast multipole method was
developed in [2].

The algorithm developed in [1] incorporates the following steps:

1.  In each subdomain a particular solution of the non-homogeneous equation
with arbitrary Neumann (Dirichlet) boundary conditions is found.

2.  The collection of particular solutions usually has discontinuities (or
discontinuities in the derivatives) on the boundaries of the subdomains.  We
introduce double (single) layers on the boundaries to match the solutions from
different domains to have continuous global solution.  The effect of these
layers on other boundaries is calculated.

3.  The solutions obtained at the first step are patched by adding the
solutions of the Laplace equation with the boundary conditions that were
computed in the previous step.

4.  An additional solution of the corresponding homogeneous equation is added
to satisfy the global boundary conditions.

Considerable improvement in the efficiency of the interface jump removal step
can be achieved if at each step only adjacent boxes are matched.  This is the
basis of the hierarchical approach which was proposed in [4].  The "elementary
step" of the hierarchical algorithm is the following.

1.  First, for each two adjacent subdomains some boundary conditions are
defined.  These conditions should not contradict the given right hand side at
the junctions (see [4]).  The Poisson equation is solved with these boundary
conditions by a fast spectral algorithm [3].

2.  The solutions have a discontinuity in the first derivative.  We match the
subdomains by adding certain discontinuous functions.  In fact we only
evaluate these functions at the boundaries of two adjacent subdomains and then
solve the homogeneous equation in each subdomain with the cumulative boundary

3.  The global homogeneous equation is solved in such a way that it satisfies
the assumed conditions at the ``global boundaries" of the merged subdomains.
The solution of the non-homogeneous equation is expensive if compared to the
homogeneous equation where efficient algorithms are available [3].

This step is repeated hierarchically.  For example, first the smallest
adjacent domains are matched:  box 1 with box 2, box 3 with box 4, then the
merged box 1,2 is matched with 3,4, afterwards the box which is a union of
boxes 1,2,3,4 is patched with the adjacent merged box etc.

Here we extend the results of [1,4] in the following directions.

1.  In addition to the Poisson equation, we solve the Helmholtz or modified
Helmholtz equation.  One of the problems that arise is resonance and
non-resonance situations for Dirichlet and Neumann boundary conditions.  This
can be avoided by introducing "transparent" boundary conditions which are
approximations to the Sommerfeld radiation boundary condition.  This means
that the scattered wave behaves asymptotically like a diverging spherical
wave.  Some modifications of the non-reflecting conditions were considered in

2.  We solve the biharmonic equation with either a free boundary as in [2] or
boundary conditions of one type only (Dirichlet or Neumann).  The biharmonic
equation is split into a coupled system of the Poisson equations.  The unknown
function satisfies the Poisson equation with a certain right hand side which
will be called a vorticity function.  The solution is also performed by DD.
Here the matching algorithm which was developed in [1,4] is applied to find
the smooth vorticity function which matches the given right hand side.  Then
we obtain a solution of the biharmonic equation.  The global boundary
conditions of either Dirichlet or Neumann type can be satisfied by the
addition of an appropriate harmonic function, as was done for the solution of
the Poisson equation.


1.  A. Averbuch, E. Braverman and M. Israeli, Parallel adaptive solution of a
Poisson equation with multiwavelets, SIAM J. Sci. Comput. 22 (2000), 1053-1086.

2.  L. Greengard and J.-Y. Lee, A direct adaptive Poisson solver of arbitrary
order accuracy, J. Comput. Phys. 125 (1996), 415-424.

3.  A. Averbuch, M. Israeli, L. Vozovoi, A fast Poisson solver of arbitrary
order accuracy in rectangular regions, SIAM J. of Sci. Comput. 19 (1998),

4.  M. Israeli, E. Braverman and A. Averbuch, A Hierarchical domain
decomposition method with low communication overhead, submitted to Proceedings
of the 13th Domain Decomposition Conference, Lyon, 2000.

5.  A. Bamberger, P. Joly and J.E.  Roberts, Second-order absorbing boundary
conditions for the wave equation:  a solution for the corner, SIAM J. Numer.
Anal. 27 (1990), 323-352.

    Editor's Note: See


Date: Wed, 14 Mar 2001 12:03:38 +0200 (IST)
From: Avraham Kenigsberg 
Subject: Paper on A Multigrid Approach for Fast Geodesic Active Contours

A Multigrid Approach for Fast Geodesic Active Contours

Avraham Kenigsberg
Department of Computer Science
Technion, Haifa 32000, Israel


Image segmentation is a basic and important problem in the field of computer
vision.  A recent geometric approach for image segmentation is the geodesic
active contour based on the level-set method.  One drawback of the method, is
the extended numerical support that makes its solution time consuming.  We
propose to solve an implicit system of the geodesic active contour model using
the computationally efflcient multigrid method.

Key words. Level set, geodesic active contour, multigrid, segmentation.

    Editor's Note: See


Date: Thu, 29 Mar 2001 12:48:50 -0700
From: Andrew Knyazev 
Subject: Paper on Toward the Optimal Preconditioned Eigensolver

Toward the Optimal Preconditioned Eigensolver: Locally
Optimal Block Preconditioned Conjugate Gradient Method

Andrew V. Knyazev
Departmentof Mathematics
University of Colorado at Denver
P .O. Box 173364, CampusBox 170
Denver, CO 80217-3364


We describe new algorithms of the Locally Optimal Block Preconditioned
Conjugate Gradient (LOBPCG) Method for symmetric eigenvalueproblems, based on
a local optimization of a three-term recurrence, and suggest several other new
methods.  To be able to compare numerically different methods in the class,
with different preconditioners, we propose a common system of model tests,
using random preconditioners and initial guesses.  As the "ideal" control
algorithm, we advocate the standard preconditioned conjugate gradient method
for finding an eigenvector as an element of the nullspace of the corresponding
homogeneous system of linear equations under the assumption that the
eigenvalue is known.  We recommend that every new preconditioned eigensolver
be compared with this "ideal" algorithm on our model test problems in terms of
the speed of convergence, costs of every iterations and memory requirements.
We provide such comparison for our LOBPCG method.  Numerical results establish
that our algorithm is practically as efficient as the "ideal" algorithm when
the same preconditioner is used in both methods.  We also show numerically
that the LOBPCG method provides approximations to first eigenpairs of about
the same quality as those by the much more expensive global optimization
method on the same generalized block Krylov subspace.  We propose a new
version of block Davidson's method as a generalization of the LOBPCG method.
Finally , direct numerical comparisons with the Jacobi-Davidson method show
that our method is more robust and converges almost two times faster.

Key words.  symmetric eigenvalueproblems, preconditioning, conjugate gradient
methods, the Lanczos method

AMS(MOS) subject classifications.  65F15, 65N25

    Editor's Note: See


Date: Tue, 13 Mar 2001 10:45:23 -0800
From: Mark Kremenetsky 
Subject: Paper on Considerations for Parallel CFD Enhancements

Considerations for Parallel CFD Enhancements
on SGI ccNUMA and Cluster Architectures

Mark Kremenetsky, PhD, Principal Scientist, CFD Applications
SGI Mountain View, CA,, 650.933.2304

Tom Tysinger, PhD, Principal Engineer
Fluent Inc, Lebanon, NH,, 603.643.2600

Stan Posey, HPC Applications Market Development
SGI Mountain View, CA,, 650.933.1689


The maturity of Computational Fluid Dynamics (CFD) methods and the increasing
computational power of contemporary computers has enabled industry to
incorporate CFD technology in several stages of design processes.  As the
application of the CFD technology grows from component level analysis to
system level, the complexity and the size of models increase continuously.
Successful simulation requires synergy between CAD, grid generation and

The requirement for shorter design cycles has put severe limitations on the
turnaround time of the numerical simulations.  The time required for (1) mesh
generation for computational domains of complex geometry and (2) obtaining
numerical solutions for flows with complex physics has traditionally been the
pacing item for CFD applications.  Unstructured grid generation techniques and
parallel algorithms have been instrumental in making such calculations
affordable.  Availability of these algorithms in commercial packages has grown
in the last few years and parallel performance has become a very important
factor in the selection of such methods for production work.

Although extensive research has been devoted in determining the optimum
parallel paradigm, in practice the best parallel performance can be obtained
only when algorithm and paradigms take into consideration the architectural
design of the target computer system they are intended for.  This paper
addresses the issues related to efficient performance of the commercial CFD
software FLUENT on a cache coherent Non Uniform Memory (ccNUMA) Architecture.
Also presented are results from implementation of FLUENT on cluster systems of
workstation for both the Linux and SGI IRIX operating systems.  Issues related
to performance of the message passing system and memory-processor affinity are
investigated for efficient scalability of FLUENT when applied to a variety of
industrial problems.

    Editor's Note: See


Date: Fri, 30 Mar 2001 13:47:33 +0200 (MET DST)
From: Domenico Lahaye 
Subject: Paper on A Multilevel Preconditioner for Field-Circuit Coupled Problems 

A Multilevel Preconditioner for Field-Circuit Coupled Problems 

Domenico Lahaye
Dept. of Computer Science, Celestijnenlaan 200A, B-3001 Heverlee Belgium


In simulating time-varrying magnetic fields in electromagnetic devices like
motors and transformers, it is often necessary to couple the partial
differential equation for the magnetic field with a model for the external
electrical circuit connections.  The electrical circuit is a system of linear
equations relating the unknown currents and voltages of the electrical
conductors present in the device to known voltage and current sources.
Time-varrying sources give rise to magnetically induced currents and voltages
in the conductors.  The partial differential equation and the circuit are
coupled by these magnetically induces quantities.

In low-frequent time-harmonic Maxwell formulations in two dimensions, the
partial differential governing the magnetic vector potential is the Helmholtz
equation with a complex shift.  The finite element discretization of this
equation results in sparse, complex symmetric system matrices.  Discretized
field-circuit coupled problems yield two by two block structured matrices
whose diagonal is formed by the discretized partial differential equation and
the electrical circuit matrix.  The size of the second diagonal block is
typically several orders of magnitude smaller than that of the first.  The
coupling is performed in such a way that no fill-in occurs in the discritized
differential equation matrix and that the two by two block matrices are again
complex symmetric.

Solving the linear system is the computational bottleneck in simulating
technically relevant engineering problems.  Motivated by previous experience
[1,2], we want to alleviate this bottleneck by the application of algebraic
multigrid (AMG) techniques.  The straightforward application of AMG is
hampered by the presence of the electrical circuit.  We develloped a multigrid
cycle that takes the circuit into account.

Our multigrid technique is a generalization of a method by Hackbush for
solving an elliptic problem augmented by an algebraic equation.  We base the
AMG setup on the differential equation block of the matrix.  The electrical
circuit is taking into account in the cycling phase.  The resulting algorithm
is a black-box solver for general field-circuit coupled problems.

For the implementation of our multigrid technique, we develloped an interface
between the GMD-AMG-code by Stueben and PETSc.  This interace allows to call
the AMG setup on the differential equation block of the system matrix.  After
the setup, the AMG coarser grid and interpolation operators are available as
PETSc matrices.  The multigrid cycling is done by PETSc's multigrid components
that we extended to be able to treat the electrical circuit.

Our algorithm has been tested on a variety of engineering problems.  It has
proven to be stable and to deliver a speedup by a factor between five and ten
compared to previously existing solvers.


1. R. Mertens, H. De Gersem, R. Belmans, K. Hameyer, D. Lahaye, 
S. Vandewalle and D. Roose, "An Algebraic Multigrid Method for Solving Very 
Large Electromagnetic Systems", IEEE Trans. on Magn., Vol 34 (5), 3327-3330

2. D. Lahaye, H. De Gersem, S. Vandewalle and K. Hameyer, "Algebraic 
Multigrid for Complex Symmetric Systems", IEEE Trans. on Magn., Vol 36 (4), 
1535-1538 (2000). 

    Editor's Note: See


Date: Thu, 22 Mar 2001 10:47:40 +0100
From: Kent-Andre Mardal 
Subject: Paper on An Optimal Iterative Method for the Time-Dependent Stokes Problem

An Optimal Iterative Method for the Time-Dependent Stokes Problem

K. A. Mardal, R. Winther, and H. P. Langtangen

Department of Informatics
University of Oslo
P.O. Box 1080 Blindern
0316 Oslo, Norway,, and


In this paper we consider an optimal multigrid/domain decomposition
preconditioner for the time-dependent Stokes problem.  Preconditioners for
this problem arise when using fully implicit time stepping schemes for the
Navier-Stokes equations.  However, as the time stepping parameter decreases
towards 0, the problem to be solved at each time step changes from the Stokes
problem to the mixed formulation of the Poisson equation.  The same
preconditioning techniques do not work in both cases, even the finite elements
typically used for Stokes are not considered stable for the mixed Poisson
equation.  We will show that some typical Stokes elements are in fact stable
also for the Poisson equation in another norm, this leads us to a proper
preconditioner working uniformly in the time stepping parameter.  The
efficiency of this preconditioner will be demonstrated by numerical
experiments done in with Diffpack, a C++ toolbox for finite element
simulations.  It is established that the preconditioner works well for the
Mini element.  Numerical experiments indicate that this preconditioner also
works for the Q2-Q1 and P2-P1

    Editor's Note: See


Date: Wed, 14 Mar 2001 13:33:12 +0100
From: Kees Oosterlee 
Subject: Paper on

On Multigrid for Linear Complementarity Problems
with Application to American-style Options

C. W. Oosterlee
GMD, Institute for Algorithms and Scientific Computing
D-53754 Sankt Augustin, Germany


We discuss a nonlinear multigrid methodfor a linear complementarity problem.
The convergence is improved by a recombination of iterants.  The problem under
consideration deals with option pricing from mathematical finance.  Linear
complementarity problems arise from so-called American-style options.  A 2D
convection-diffusion type operator is discretized with the help of second
order upwind discretizations.  The properties of smoothers are analyzed with
Fourier two-grid analysis.  Numerical solutions obtained for the option
pricing problem are compared with reference results.

Key words.  linear complementarity problems, American-style options, nonlinear
multigrid, projected Gauss-Seidel, iterant recombination, second-order upwind
discretization, Fourier analysis

AMS subject classifications.  65M55, 65F99, 90A09

    Editor's Note: See


Date: Thu, 8 Mar 2001 09:37:42 +0100
From: Peter Deuflhard 
Subject: SIAM/EMS Conference Berlin, Sept. 2-6, 2001

The Society for Industrial and Applied Mathematics (SIAM) and the European
Mathematics Society (EMS) are jointly organizing the

                        First SIAM/EMS Conference

to be held in Berlin, Sept. 2 - 6, 2001, on the attractive Dahlem campus,
where also ZIB is situated.


1. Medicine: Alfio Quarteroni (I)
2. Biotechnology: Michael Waterman (USA)
3. Materials Science: Jon Chapman (UK)
4. Environmental Science: Andrew Majda (USA)
5. Nanoscale Technology: Michael Griebel (D)
6. Communication: Martin Groetschel (D)
7. Traffic: Kai Nagel (CH)
8. Market and Finance: Benoit Mandelbrot (USA)
9. Speech and Image Recognition: Pietro Perona (USA)
10.Engineering Design: Thomas Y. Hou (USA)

For more information please check

The International Program Committee is now encouraging the organization of
MINISYMPOSIA within the frame of the 10 main topics above.


The scheme of the minisymposia follows the tradition of the ones within SIAM
meetings.  Typically a minisymposium is organized by two organizers and
consists of four invited talks of half an hour each.  The organizers and the
speakers should be spread internationally.  Two of the talks may well be given
by the two organizers.  I am sorry to say that neither registration fees will
be waived nor will travel or local costs be covered for organizers or invited
speakers of minisymposia.  Organizers may, of course, try to raise funds from
any other sources.  We might help with material about the conference, if

our website.


The official deadline for submission of minisymposia is

                        April 15, 2001.

But I urge anyone interested to make up their mind as soon as possible.  Take
into account that Berlin is also an attractive tourist city!

      Peter Deuflhard
      Chair of Program Committee


  First SIAM/EMS Conference
  to be held in Berlin, Sept. 2-6, 2001.


Date: Tue, 13 Mar 2001 06:55:54 -0400
From: "Laurence T. Yang" 

The 3rd Workshop on High Performance Scientific and Engineering 
Computing with Applications (HPSECA-01) 

Valencia, Spain, September 3-7, 2001

in conjunction with

Scope and Interests:

Parallel and distributed scientific and engineering computing has become a key
technology which will play an important part in determining, or at least
shaping, future research and development activities in many academic and
industrial branches.  This special workshop is to bring together computer
scientists, applied mathematicians and researchers to present, discuss and
exchange idea, results, work in progress and experience of research in the
area of parallel and distributed computing for problems in science and
engineering applications.

Among the main topics (but not limited to) are:

* development of advanced parallel and distributed methods,
* parallel and distributed computing techniques and codes,
* practical experiences using various supercomputers with software 
  such as MPI, PVM, and High Performance Fortran, OpenMP, etc.
* applications to numerical fluid mechanics and material sciences,
* applications to signal and image processing, dynamic systems, 
  semiconductor technology, and electronic circuits and system 
  design etc.

Submission Information:

Authors should send one copy of paper in either PS or PDF format at most 15
pages to the workshop organizers ( or ) via
electronic mail or three copies via postal mail.  Contributions will be
reviewed by at least three reviewers from both Program Committee and external
reviewers for relevance and technical contents on basis of papers.  Accepted
papers with at most 8 pages will be published by IEEE Computer Society Press
as proceedings of the ICPP 2001 workshops.  A special issue of International
Journal of Supercomputer Applications and High Performance Computing is

Further information about the conference proceedings and registration fee can
be found by web sites:

Important Deadlines:
Paper submission Due         (April 1, 2001!!)
Notification of Acceptance   May 1, 2001
Final camera-ready paper     June 1, 2001

Workshop Organizers:

Prof. Laurence T. Yang (chair) 
Department of Computer Science
PO Box 5000, St. Francis Xavier University
Antigonish, B2G 2W5, Nova Scotia, Canada

Prof. Yi Pan (Co-Chair)
Department of Computer Science, 
Georgia State University, Atlanta, GA 30303, USA


Date: Mon, 26 Mar 2001 17:16:50 +0200
From: Gerhard Zumbusch 
Subject: 2nd Announcement Meshfree Methods


                         International Workshop
             Meshfree Methods for Partial Differential Equations

                             Bonn, Germany

                         September 11 - 14, 2001



  Ivo Babuska (University of Texas, Austin, USA)
  Michael Griebel (Universitaet Bonn, Germany)
  Wing Kam Liu (Northwestern University, USA)
  Helmut Neunzert (Fraunhofer-Institut ITWM, Germany)
  Harry Yserentant (Universitaet Tuebingen, Germany)

Invited Speakers:

  Satya Atluri (University of California, Los Angeles, USA)
  Ted Belytschko (Northwestern University, USA)
  Jiun-Shyan Chen (University of Iowa, USA)
  Gary Dilts (Los Alamos National Laboratory, USA)
  Weimin Han (University of Iowa, USA)
  Michael Junk (Universitaet Kaiserslautern, Germany)
  Petros Koumoutsakos (ETH Zuerich, Switzerland)
  Joe Monaghan (Monash University, Australia)
  Koji Morinishi (Kyoto Institute of Technology, Japan)
  Joseph Morris (Lawrence Livermore National Laboratory, USA)
  Bernard Nayroles (INSA Rouen, France)
  Jens Struckmeier (Universitaet Hamburg, Germany)
  Jean Paul Vila (Universite Paul Sabatier, Toulouse III, France)
  Jinchao Xu (Penn State University, USA)

Important Dates and Deadlines:

  May 1, 2001 Early Registration and Abstract submission
  August 1, 2001 Confirmation and Program


Meshfree methods for the solution of partial differential equations gained
much attention in recent years, not only in the engineering but also in the
mathematics community.  One of the reasons for this development is the fact
that meshfree discretizations and particle models are often better suited to
cope with geometric changes of the domain of interest, e.g.  free surfaces and
large deformations, than classical discretization techniques such as finite
differences, finite elements or finite volumes.  Another obvious advantage of
meshfree discretizations is of course their independence of a mesh.  Mesh
generation is still the most time consuming part of any mesh based numerical
simulation.  Since meshfree discretization techniques are based only on a set
of independent points these costs of mesh generation are eliminated.  Finally,
the coupling of particle models to continuous models gained enormous interest
in recent years from a theoretical as well as from a practical point of view.

Among the most prominent meshfree discretization techniques are:

     stochastic particle models,
     smoothed particle hydrodynamics,
     reproducing kernel particle methods,
     partition of unity methods,
     element free Galerkin methods,
     radial basis functions,
     vortex methods.

The aim of the workshop is to bring together european and american researchers
from different fields-inside and outside mathematics-not only to strengthen
the mathematical understanding and analysis of meshfree discretizations but
also to promote the exchange of ideas on their implementation and application.

Topics of interest in the workshop are:

     analysis of meshfree methods,
     implementational issues of meshfree methods,
     coupling of particle models to continuous models,
     industrial applications of meshfree methods.

The four day workshop program will consist of invited lectures, contributed
papers and poster sessions.

If you are interested in contributing to this workshop, please submit an

abstract of about 300 words by e-mail to the contact address by May 1, 2001.

International Workshop
Meshfree Methods for Partial Differential Equations
Rheinische Friedrich Wilhelms Universitaet Bonn
Institut fuer Angewandte Mathematik
Abteilung Wissenschaftliches Rechnen und Numerische Simulation

Wegelerstrasse 6
D-53115 Bonn

fax: +49 228 737527


End of MGNet Digest