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 5 (approximately May 31, 2003)

Today's topics:

     Important date
     Program to add to resources
     Domain Decomposition Sites
     11th Copper Mountain Multigrid Virtual Proceedings Contributions


Date: Fri, 30 May 2003 10:22:21 -0400
From: Craig Douglas 
Subject: Important date

June 30     11th GAMM-Workshop on Multigrid and Hierarchic Solution Techniques
            Abstracts + registration due: see


Date: Thu, 8 May 2003 20:31:42 +0100 (BST)
From: Sandra Barsky (
Subject: Program to add to resources

I have attached to this email a code written in C which solves non-linear
time-dependent 2-D eqns.  In particular, the equation should have the form:

    (d/dt)u= (\nabla^2) u + g(x,y,u) + f(x,y)

with periodic boundary conditions.  The function g is easily tunable.  The
code is written as a primarily instructional code for a student who might have
some familiarity with linear multigrid, and would want a slightly more general
approach, or a student who can solve a linear boundary equation, but is now
looking to include time.  I haven't provided overly detailed explanations of
what restriction or prolongation do, but I've been more detailed in how the
linearization occurs, and what happens as a function of time.

I would be most pleased if you could include this with your selection of codes
available for the public.

I am the primary author of the code, and may be contacted at the current 
address: or

Thank you,
Sandra Barsky

    Editor's Note: see (not
    -------------  quite installed yet... sorry)


Date: Sat, 17 May 2003 22:54:05 -0700
Subject: Domain Decomposition Sites

I am an undergrad at the University of British Columbia.  I am doing a summer
research project on domain decomposition.  I did a yahoo search on the topic
but I didn't find any "undergrad-friendly" sites.  Do you know of any
electronic resources that would be accessible to undergrads?



Date: Fri, 30 May 2003 10:22:21 -0400
From: Craig Douglas 
Subject: 11th Copper Mountain Multigrid Virtual Proceedings Contributions

You can see the virtual proceedings for the 11th Copper Mountain Multigrid
Conference grow at  Participants are
urged to make a contribution.

                             * * * * * * * * * *

Algebraic Multigrid Methods for Constrained Systems of Linear Equations

Mark Adams 

Sandia National Laboratories
PO Box 969.
Livermore CA 94551-9217


Constrained systems of linear equations (KKT systems) arise in many
applications from contact in solid mechanics and incompressible flow, to
problems in mathematical optimization for PDE systems.   Several
approaches have been developed for solving these systems, given a solver
for the primal part of the system: 1) constraint reduction, 2)
projection methods, and 3) Uzawa/augmented Lagrange.   All of these
methods have advantages and disadvantages.   Uzawa methods are robust
and scalable though they require several approximate solves, as they
iterate on the Shur complement.   Constraint reduction is effective for
certain types of constraints, but is limited in its applicability.  
Projection methods are attractive as they handle general constraints and
are simple to use with an existing solver or preconditioner, but they
are generally not scalable nor are they robust when used with powerful
preconditioners, such as multigrid.

Algebraic multigrid is a popular method for solving the equations that
arise from discretized PDEs, the primal part of KKT systems, but the
application of multigrid to the entire KKT system has not been
investigated to a great degree.   V.H. Schulz has recently applied
structured geometric multigrid to optimization problems, S.P. Vanka has
developed structured geometric multigrid techniques for incompressible
flow problems, and a commercial product (TaskFlow) has developed an
algebraic (aggregation) multigrid method for unstructured incompressible
flow problems.   Multigrid methods are attractive for constrained
systems as they have the potential to be both highly optimal like
constraint reduction and general like projection methods by maintaining
tight coupling of the constraints in the preconditioning process while
not requiring that the primal part of the system be augmented by
regularization as in Uzawa methods or a Shur complement as in constraint

This talk discusses the application of algebraic multigrid techniques to
discretized PDEs with constraints.   We describe a framework for
developing algebraic multigrid methods for KKT systems and discuss
coarsening techniques for the constraint equations.   We cover several
approaches to constructing multigrid smoothers and present examples of
application of some of these ideas to contact problems in solid mechanics.

    Editor's Note: see
                             * * * * * * * * * *

On Generalizing the AMG Framework

Robert D. Falgout 
Panayot S. Vassilevski

Lawrence Livermore National Laboratory
P.O. Box 808, L-561
Livermore, CA 94551


In recent years, much work has been done to increase the robustness of
Algebraic Multigrid (AMG) methods. The classical AMG method of Ruge and
Stüben [5] used heuristics based on properties of M-matrices. Although
this algorithm works remarkably well for a wide variety of problems [3],
the M-matrix assumption still limits its applicability. To address this,
a new class of algorithms was developed based on multigrid theory: AMGe
[1], element-free AMGe [4], and spectral AMGe [2]. All of these
algorithms assume a basic framework in their construction. Namely, they
assume that relaxation is a simple pointwise method, then they build the
coarse-grid correction step to eliminate the so-called algebraically
smooth error left over by the relaxation process. In the AMGe methods
above, this is done with the help of a measure (or weak-approximation
property) that defines the approximation property that interpolation
must satisfy in order to achieve uniform convergence assuming a
pointwise relaxation.

In this talk, we introduce a new measure for constructing algebraic
multigrid methods. The purpose of this new measure is to generalize the
AMG framework to include problems such as Maxwell's Equations, which has
a particularly large null-space when discretized using the common
Nédélec finite elements. In the old framework, it is necessary to take
all O(N) of these null-space components to the coarse grid, which
results in a non-optimal method. This problem can be overcome by using
something other than pointwise relaxation to damp a subspace of these
near-null-space components on the fine grid. Examples include
overlapping block relaxation or the so-called Hiptmair smoother
(Brandt's distributive relaxation). The measure proposed here takes into
account the smoothing process and changes the AMGe heuristic in a subtle
but important way. The hope is that this new measure will allow us to
develop AMG methods that can handle difficult problems such as Maxwell's
equations or Helmholtz.

[1] M. Brezina, A. J. Cleary, R. D. Falgout, V. E. Henson, J. E. Jones,
T. A. Manteuffel, S. F. McCormick, and J. W. Ruge, Algebraic multigrid
based on element interpolation (AMGe), SIAM J. Sci. Comput., 22 (2000),
pp. 1570 -1592.
[2] T. Chartier, R. D. Falgout, V. E. Henson, J. E. Jones, T. A.
Manteuffel, S. F. McCormick, J. W. Ruge, and P. S. Vassilevski, Spectral
AMGe, SIAM J. Sci. Comput. To appear.
[3] A. J. Cleary, R. D. Falgout, V. E. Henson, J. E. Jones, T. A.
Manteuffel, S. F. McCormick, G. N. Miranda, and J. W. Ruge, Robustness
and scalability of algebraic multigrid, SIAM J. Sci. Comput., 21 (2000),
pp. 1886-1908.
[4] V. E. Henson and P. S. Vassilevski, Element-free AMGe: general
algorithms for computing interpolation weights in AMG, SIAM J. Sci.
Comput., 23 (2001), pp. 629-650.
[5] J. W. Ruge and K. Stüben, Algebraic multigrid (AMG), in Multigrid
Methods, S. F. McCormick, ed., vol. 3 of Frontiers in Applied
Mathematics, SIAM, Philadelphia, PA, 1987, pp. 73-130.

    Editor's Note: see
                             * * * * * * * * * *

Algebraic construction of mortar finite element spaces with application
to parallel AMGe

Tzanio V. Kolev , Joseph E. Pasciak

Department of Mathematics
Texas A&M University
College Station, TX 77843-3368

and Panayot S. Vassilevski 

Center for Applied Scientific Computing
UC Lawrence Livermore National Laboratory
P. O. Box 808, L-560
Livermore, CA 94551


Finite element problems posed on large unstructured grids arise
naturally in simulations, where only a very fine discretization of the
domain is available. In order to achieve performance comparable with
multilevel methods for the geometrically refined case, one can use an
algebraic solver based on sequence of coarsened meshes.

In this talk we present a possible parallelization of one such algorithm
- the agglomeration based algebraic multigrid for finite element
problems (AMGe). The method starts with a partitioning of the original
domain into subdomains with a generally unstructured finite element mesh
on each subdomain. The agglomeration based AMGe is then applied
independently in each subdomain. It needs access to the local stiffness
matrices which are (variationally) constructed after coarsening. Note
that even if one starts with a conforming fine grid, independent
coarsening generally leads to non-matching grids on the coarser levels.
We use an element-based dual basis mortar finite element method in order
to set up global problems on each level. Since the considered AMGe
produces abstract elements and faces defined as lists of nodes, the
mortar multiplier spaces are also constructed in a purely algebraic way.
This construction requires inversion of the local mass matrices on each
interface boundary shared between two subdomains, which is possible
because of the way AMGe agglomerates the faces. Finally, a
multigrid-preconditioned solver is applied to the resulting sequence of
(non-nested) spaces. The talk will conclude with set of numerical
results illustrating the computational behavior of this new algebraic
multigrid algorithm.

    Editor's Note: see
                             * * * * * * * * * *

Algebraic multilevel preconditioner with projectors

Konstantin Lipnikov 

T-7, MS-B284, Los Alamos, NM 87545

Yuri Kuznetsov

Department of Mathematics, University of Houston, TX 77204


The two-level algebraic preconditioner with projectors has been proposed
in [1] for symmetric positive definite stiffness matrices. The
underlying grid is partitioned into non-overlapping substructures of
arbitrary shapes (grid subdomains, superelements or simply original grid
cells). A projector to the kernel of a subdomain stiffness matrix is
build for each subdomain. A coarse grid matrix is an approximation to
the original stiffness matrix in the space of images of the projectors.
If the original stiffness matrix is a finite element approximation of an
elliptic operator, the coarse grid matrix describes connections between
integral averages a discrete function over subdomains.

In the talk we shall prove the convergence of the two-level scheme for
the case of elliptic operators. We shall show that the convergence rate
is independent of jumps in coefficients between subdomains. A multilevel
preconditioner based on the two-level scheme will be studied numerically
for the case of highly distorted meshes and strongly varying
coefficients. In comparison with a few other multilevel preconditioners,
it demostrates robust behavior over a much bigger class of problems [2].

[1] Yu.Kuznetsov, Two-level preconditioners with projectors for
unstructured grids. Russian J. Numer. Anal. Math. Modelling, (2000),
v.15, pp.247-256.

[2] Yu.Kuznetsov, K.Lipnikov, Parallel numerical methods for the
diffusion and Maxwell equations in heterogeneous media on strongly
distorted meshes, Technical Report, University of Houston, May, 2002.

    Editor's Note: see
                             * * * * * * * * * *

AMG Wave-Ray Solver for Helmholtz Eigenvalue Problem: Preliminary Results

Irene Livshits 

Department of Mathematics, Univsersity of Central Arkansas,  Conway, AR


Numerical solvers for indefinite Helmholtz equations have to deal with a
range of erroneous components which have a slow convergence by standard
relaxation procedures. Brandt and Livshits suggested wave-ray approach
that allows to overcome such slowness by introducing ray representations
and ray treatment of problematic components. This approach, however,
does not have a straightforward extension for Helmholtz operators with
variable coefficients, since it requires a knowledge of analytical
solutions of homogeneous Helmholtz operator (principal components).

In this talk I will discuss the ways of modifying the wave-ray approach
for solving eigenvalue problems for Helmholtz operators with variable
coefficients. The presented algorithm employs Galerkin based algebraic
multigrid, and modified wave-ray approach, which employs the best
current approximation to the solution instead of principal components.
The algorithm and the results of the numerical experiments will be
discussed on the example of one-dimensional Helmholtz operator with
periodic boundary conditions. Joint work with A.Brandt.

    Editor's Note: see
                             * * * * * * * * * *

AMG for Higher-Order Discretizations of Second-Order Elliptic Problems

John W. Ruge 

1005 Gillaspie Dr., Boulder CO 80305


Algebraic Multigrid (AMG) has been shown to be a very effective solver
for standard finite-difference and finite-element discretizations of a
wide range of second-order elliptic PDEs. This talk covers some of the
issues related to the use of AMG on discretizations using higher-order
finite elements.  These include: problems encountered when no special
handling is used; variations of the AMG algorithm better suited for such
problems; the effect of the choices of basis functions; and measures of
accuracy versus work for various orders of approximation. Numerical
results are reported.

    Editor's Note: see


End of MGNet Digest