Send mail to:  mgnet@cs.yale.edu             for the digests or bakeoff
               mgnet-requests@cs.yale.edu    for comments or help
 
Anonymous ftp repository:  www.mgnet.org (128.163.209.19)
 
Current editor:  Craig Douglas douglas-craig@cs.yale.edu
 

WWW Sites:  http://www.mgnet.org or
            http://casper.cs.yale.edu/mgnet/www/mgnet.html or
            http://www.cerfacs.fr/~douglas/mgnet.html or
            http://phase.hpcc.jp/mirrors/mgnet or
            http://www.tat.physik.uni-tuebingen.de/~mgnet

Today's editor:  Craig Douglas (douglas-craig@cs.yale.edu)

Volume 13, Number 4 (approximately April 30, 2003)

Today's topics:

     A Workshop on the DOE Advanced Computational Software Collection
     11th Copper Mountain Multigrid Virtual Proceedings Contributions

-------------------------------------------------------

Date: Tue, 30 Apr 2003 10:10:37 -0700
From: Tony Drummond 
Subject: A Workshop on the DOE Advanced Computational Software Collection

FOURTH WORKSHOP ON THE DOE ADVANCED COMPUTATIONAL SOFTWARE COLLECTION
Robust and High Performance Tools for Scientific Computing

Lawrence Berkeley National Laboratory
August 5-8, 2003

The DOE Advanced CompuTational Software Collection (ACTS Collection,
http://acts.nersc.gov) comprises a set of tools mainly developed at the
Department of Energy's (DOE) laboratories.  These software tools aim to
simplify the solution of common and important computational problems and have
substantially benefited a wide range of scientific and industrial
applications.  These benefits are accounted not only for running efficiently
in high performing computing environments but also realizing computation that
would not have been possible otherwise.  Despite these successes, there is
still a need for a greater infrastructure to reach out academia and industry
through a dissemination and instruction on the state-of-the-art tools for high
performance computing environments and simultaneously provide an umbrella for
tool developers to receive the feedback from these communities.  This workshop
is part of an approach to build such an infrastructure.

The four-day workshop will present an introduction to the ACTS Collection for
application scientists whose research demand includes either large amounts of
computation, a large volume of data manipulation, the use of robust numerical
algorithms, or combinations of these.  The workshop will include a range of
tutorials on the tools (currently available in the collection and some
deliverables from the DOE SciDAC ISICs), discussion sessions aimed to solve
specific computational needs by the participants, and hands-on practices using
the NERSC's state-of-the-art computers.  We are planning to organize parallel
sessions and group the tutorials by topics, as follows:

    Direct and Iterative Methods for the solution of linear and
        non-linear systems of equations
    PDE's and Multi-level Methods
    Numerical Optimization
    Structured and Unstructured meshes (Generation, Manipulation and
        Computation)
    Development of High Performance Computing applications
    Performance monitoring and tuning
    Grid computing

DOE will fully sponsor a limited number of graduate students and postdoctoral
fellows to participate in this event.  This support includes round-trip
transportation to and from Berkeley, local transportation, lodging, meals and
workshop materials.  Proposals from other research scientists are also
encouraged.

The deadline for applications is June 9, 2003 and they should be submitted
using the application on-line form:

    http://acts.nersc.gov/events/Workshop2003/application.html.

Students and postdoctoral fellows should submit an abstract describing the
nature of their work, future plans and/or current needs for computation.  A
letter of recommendation from the applicant's supervisor also needs to be
provided using the recommendation on-line form:

    http://acts.nersc.gov/events/Workshop2003/recommendation.html

The recommendation letter must also arrive no later than June 9, 2003.  Other
applicants must submit a letter outlining their current work and future plans
and needs for computational resources with a list of publications .  For more
information on the workshop, please contact Tony Drummond at (510) 486-7624 or
Osni Marques at (510) 486-5290.

Important Dates:

    Proposal submission deadline:   June 9, 2003
    Proposal review completed and invitations sent:  June 20, 2003
    Attendee confirmation of participation deadline:  June 30, 2003

-------------------------------------------------------

Date: Wed, 30 Apr 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 http://www.mgnet.org.cm2003.html.  Participants are
urged to make a contribution.

                             * * * * * * * * * *

A Multigrid Tutorial
Van Emden Henson

This presentation is an updated reincarnation of the tutorials Bill Briggs
gave at Copper Mountain in 1987 and 1989.  The 1987 tutorial led to the
publication of the popular book, A Multigrid Tutorial (SIAM books), which has
served as the introduction to multigrid for a good many workers in the field.
Assuming no familiarity with multigrid, the tutorial introduces multigrid from
first principles, examining basic iterative methods, coarse-grid correction,
two-level approaches, and extending to multigrid methods.

We will also take up some "complications" that arise commonly in practice, and
illustrate some of the techniques used to deal with them.  These will be
presented in simple, model-problem form.  Typical solution methods will be
outlined.  Time constraints may prohibit coverage of all topics.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#tutorial-henson

    -------------

                             * * * * * * * * * *

Cache-Based Algorithms
Craig C. Douglas and Ulrich J. Ruede

An introduction to methods for improving locality of data usage in
iterative methods will be presented.  The emphasis will be for problems
related to solving PDE's.  Separate methods for structured,
unstructured, and quasi-unstructured grids will be given.  In some
cases, but not all, bitwise identical results are achieved with respect
to standard implementations of the algorithms considered.  The methods
are applicable to almost any compiled language.  No background in
machine architectures will be assumed or needed.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#tutorial-douglas-ruede
    -------------

                             * * * * * * * * * *

Implementation of a Scalable Preconditioned Eigenvalue Solver Using Hypre
Merico E. Argentati and Andrew V. Knyazev

The goal of this project is to develop a Scalable "Preconditioned Eigenvalue
Solver" for the solution of partial eigenvalue problems for large sparse
symmetric matrices on massively parallel computers, taking advantage of
advances in the Scalable Linear Solvers project, in particular in multigrid
technology and in incomplete factorizations (ILU) developed under the HYPRE
project, at the Lawrence Livermore National Laboratory ,
Center for Applied Scientific Computing 
(LLNL-CASC).  The solver allows the utilization of HYPRE preconditioners for
symmetric eigenvalue problems.  In this talk we discuss the implementation
approach for a flexible ?matrix free?  parallel algorithm, and the
capabilities of the developed software.  We also discuss performance on a set
of test problems.

The base iterative method that has been implemented is the locally optimal
block preconditioned conjugate gradient (LOBPCG)
 method described in:  A.
V. Knyazev, Toward the Optimal Preconditioned Eigensolver:  Locally Optimal
Block Preconditioned Conjugate Gradient Method, SIAM Journal on Scientific
Computing 23 (2001), no.  2, pp.  517-541
.  The LOBPCG
solver finds one or more of the smallest eigenvalues and the corresponding
eigenvectors of a symmetric matrix.

The code is written in MPI based C-language and uses HYPRE and LAPACK
libraries.  It has been tested with HYPRE version 1.6.0.  The user interface
to the solver is implemented using HYPRE style object oriented function calls.
The matrix-vector multiply and the preconditioned solve are done through user
supplied functions.  This approach provides significant flexibility.  The
implementation illustrates that this method can successfully and efficiently
use parallel libraries.

The following HYPRE preconditioners have been tested, AMG-PCG, DS-PCG,
ParaSails-PCG, Schwarz-PCG and Euclid-PCG , in the eigenvalue solver.
Partition of processors is determined by user input consisting of an initial
array of parallel vectors.  The code has been mainly developed and tested on a
beowulf cluster at CU Denver .
This system includes 36 nodes, 2 processors per node, PIII 933MHz processors,
2GB memory per node running Linux Redhat, and a 7.2SCI Dolpin interconnect.
Lobpcg has also been tested on several LLNL clusters using Compaq and IBM
hardware, running Unix and/or Linux.


Keywords:  Eigensolvers, parallel preconditioning, sparse matrices, parallel
computing, conjugate gradients, additive Schwarz preconditioner.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Argentati
    -------------

                             * * * * * * * * * *

Partition of Unity Method for Stokes Problem
Constantin Bacuta and Jinchao Xu

We propose a finite element method for overlapping or nonmatching grids for
the Stokes Problem based on the partition of unity method.  We prove that the
discrete inf-sup condition holds with a constant independent of the
overlapping size of the subdomains.  The results are valid for multiple
subdomains and any spatial dimension.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Bacuta
    -------------

                             * * * * * * * * * *

Hierarchical Hybrid Grids:  A Framework for Efficient Multigrid on High
Performance Architectures
Ben Bergen

For many scientific and engineering applications it is often desirable to use
unstructured grids to represent complex geometries.  Unfortunately the data
structures required to represent discretizations on such grids typically
result in extremely inefficient performance on current high-performance
architectures.  Here we introduce a grid framework using patch-wise, regular
refinement that retains the flexibility of unstructured grids while achieving
performance comparable to that seen with purely structured grids.  This
approach leads to a grid hierarchy suitable for use with geometric multigrid
methods thus combining asymptotically optimal algorithms with extremely
efficient data structures to obtain a powerful technique for large scale
simulations.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Bergen
    -------------

                             * * * * * * * * * *

Adaptive Smoothed Aggregation Method and Applications
M. Brezina, T. Betlach, R. Falgout, S. MacLachlan, T. Manteuffel, S.
McCormick, and J. Ruge

Substantial effort has been focused over the last two decades on developing
multilevel iterative methods capable of solving the large linear systems
encountered in engineering practice.  These systems often arise from
discretizing partial differential equations over unstructured meshes, and the
particular parameters or geometry of the physical problem being discretized
may be unavailable to the solver.  Algebraic multilevel methods have been of
particular interest in this context because of their promises of optimal
performance without the need for explicit knowledge of the problem geometry.
These methods construct a hierarchy of coarse problems based on the linear
system itself and on certain assumptions about the low-energy components of
the error.

For smoothed aggregation methods applied to discretizations of elliptic
problems, these assumptions typically consist of knowledge of the
near-nullspace of the weak form.  We describe a recently developed extension
of the smoothed aggregation method in which good convergence properties are
achieved in situations where explicit knowledge of the near-nullspace
components may be unavailable.  This extension is accomplished by using the
method itself to determine near-nullspace components when none are provided.
The coarsening process is modified to use and improve the computed components.

Numerical experiments include test problems arising in the LANL's hydrocode
SAGE, featuring cell-centered discretization, automatic mesh refinement and
coefficient discontinuities.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Berzina
    -------------

                             * * * * * * * * * *

A Multigrid Approach to Two-Dimensional Phase Unwrapping
Gregory Dardyk and Irad Yavneh

The two-dimensional phase unwrapping problem is studied.  Using the minimum
Lp-norm approach, we apply three different nonlinear multigrid algorithms for
reconstructing surfaces from their ?wrapped?  values?two classical approaches
and a novel Multilevel Nonlinear Method (MNM).  The methods prove to be
efficient even for difficult problems with noisy and discontinuous original
images.  The new method, MNM, exhibits the fastest convergence of the three
for all the problems, given an appropriate choice of a damping parameter.
Proposed methods for choosing this parameter automatically are mentioned.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Dardyk
    -------------

                             * * * * * * * * * *

Geometric Multigrid Method for Electro- and Magnetostatic Field Simulations
Using the Conformal Finite Integration Technique
Stefan Feigh, Markus Clemens, and Thomas Weiland

A geometrical multigrid algorithm for vector based formulations for
electromagnetic field problems discretized by the Conformal Finite
Integration Technique is proposed. The transfer operators and the coarse
grid operators are constructed for a hierarchy of non-nested grids. A
validation of the presented approach is achieved for electro-static and
magneto-static test problems for which a discrete Poisson and a discrete
Curl-Curl equation have to be solved respectively. Experimental results
for the asymptotic complexity and for the convergence characteristics in
case of discontinuous material coefficients are presented.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Feigh
    -------------

                             * * * * * * * * * *

SMG on SMP Clusters: Performance Issues
Sue Goudy, Lorie Liebrock, and Steve Schaffer

The symmetric multiprocessor (SMP) appears as a unit in systems from desktop
computers to massively parallel systems.  The focus of this paper is the
performance of a particular algorithm, two-dimensional semicoarsening
multigrid, on a cluster of SMPs.  Complexity models for hybrid parallelization
of a portion of this algorithm are derived.  We examine system parameters,
such as the capability for simultaneous message-passing in a symmetric
multiprocessor, that can affect the performance of hybrid code.  Complexity
estimates are tested for a variety of decomposition strategies, line solve
methods, and problem sizes.  Results from the Intel Teraflops supercomputer
and from a Beowulf cluster of dual-processor Xeons are presented.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Goudy
    -------------

                             * * * * * * * * * *

Nonlinear AMGe with Coarsening Away from the Contact Boundary for the
Signorini's Problem
Ana H. Iontcheva and Panayot S. Vassilevski

The finite element discretization of the Signorini's problem leads to
inequality constrained minimization problem.  In this talk we present a
nonlinear element based algebraic multigrid method with special coarsening
away from the contact boundary for the solution of this problem.  As a
smoothing procedure we use the Projected Gauss-Seidel algorithm and for the
coarse grid solver - a modification of the Dostal's algorithm.  The
performance of the resulting method is illustrated by numerical experiments.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#
    -------------

                             * * * * * * * * * *

Coarsening by Compatible Relaxation
Oren E. Livne

Algebraic Multigrid (AMG) solvers of large sparse linear system of equations
are based on multigrid principles but no do explicitly use the geometry of the
grids.  The emphasis in AMG is on black on procedures for coarsening the set
of equations, relying on its algebraic relations.  Although AMG is widely
employed, e.g.  for solving second-order elliptic discretized PDEs with
disordered coefficients on unstructured grids, its scope is rather limited to
these cases.  However, AMG may be remedied, by systemtically understanding and
improving its ingredients:  relaxation, coarse levels and inter-level
transfers.  We present a novel approach for selecting the coarse variables for
AMG.  Classical AMG coarse set construction relies on the strength of local
algebraic connections between variables, that are often misleading and
inaccurate.  Alternatively, our coarse set quality measure is the rate of
convergence of compatible relaxation (CR) [Brandt, ETNA, 2000].  It also leads
to a construction algorithm of the coarse set.  We will present numerical
examples of our algorithm for simple model problems, e.g., anistropic
diffusion and the biharmonic operator, for which classical AMG often fails.
This work makes it possible to assess and construct a coarse set of variables
for a given system, prior to its actual use by an AMG solver.  Undergoing
research is focused on attaining CR rates (that play a similar role to the
smoothing rate in geometric multigrid, predicting the ideal multigrid
efficiency).  This relates to self-correcting AMG (a joint work with Prof.  A.
Brandt, Weizmann Institute) that iteratively derives its own interpolation
operators.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Livne
    -------------

                             * * * * * * * * * *

Adapting Algebraic Multigrid
Scott MacLachlan

Our ability to numerically simulate physical processes is severely constrained
by our ability to solve the complex linear systems that are often at the core
of the computation.  Multigrid methods offer an efficient solution technique
for many such problems.  However, fixed multigrid processes are based on an
overall assumption of smoothness that may not be appropriate for a given
problem.  Our aim is to develop an adaptive multigrid scheme that replaces
this predetermined sense of smoothness by one that is determined
automatically.  This paper focuses on the principal component of such a
scheme:  adaptive interpolation.  Our method is based on computing a
representative error component that is not quickly reduced by relaxation and
fitting interpolation so that it is eliminated by the coarse-grid correction
process.  Numerical results are given to support the efficiency of this
approach.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#MacLachlan
    -------------

                             * * * * * * * * * *

A Fully Implicit Parallel Algorithm for Simulating the Nonlinear Electrical
Activation of the Heart

Maria Murillo and Xiao-Chuan Cai

In this research we developed and tested a fully implicit and highly parallel
Newton-Krylov-Schwarz method for solving the bidomain equations representing
the excitation process of the heart.  Newton-Krylov-Schwarz method has been
used successfully for many nonlinear problems, but this is the first attempt
to use this method for the bidomain system which consists of time dependent
partial differential equations of mixed types.  Our experiments on parallel
computers show that the method is scalable and robust with respect to many of
the parameters in the bidomain system.

In the outer layer of the algorithm, we use a nonlinearly implicit backward
Euler method to discretize the time derivative, and the resulting systems of
large sparse nonlinear equations are solved using an inexact Newton method.
The Jacobian system required solving in each Newton iteration is solved with a
preconditioned GMRES method.  The efficiency and robustness of the overall
method depends heavily on the preconditioning step of the linear solver.  By
comparing several preconditioners, we found the restricted additive Schwarz
method offers the best performance.  Our parallel software is developed using
the PETSc package of Argonne National Laboratory, and our numerical results
were obtained on the IBM-SP of the San Diego Supercomputer Center.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Murillo
    -------------

                             * * * * * * * * * *

Least-Squares Methods for Hyperbolic Conservation Laws
Hans De Sterck, Tom Manteuffel, Steve McCormick, and Luke Olson

Least-squares finite element methods for the inviscid Burgers equation in
space-time domains are presented.  Numerical results show that convergence of
a standard least-squares approach for div(u,u2/2)=0 with bilinear elements for
u and Newton linearization is problematic, possibly due to difficulties with
the linearizability of the Burgers operator around discontinuous solutions.
Alternative H(div)-conforming formulations are proposed in terms of the flux
variables (or their De Rahm-dual) using face and edge elements.  The face
element formulation does not exhibit exact numerical conservation at the
discrete level, but it is shown that the formulation converges to a
conservative weak solution with the correct shock speed.  The dual edge
element formulation is strictly conservative at the discrete level.  The
least-squares functional naturally provides a sharp a posteriori error
estimator that is used for adaptive refinement in space-time.  Standard
algebraic multigrid methods are applied to the positive semi-definite matrices
resulting from the new least-squares formulations, and multigrid efficiency as
a function of problem size is investigated.  Extension of the new
least-squares methods to general systems of hyperbolic conservation laws in
multiple dimensions is discussed.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Olson
    -------------

                             * * * * * * * * * *

Black-Box Preconditioning for Mixed Formulation of Second-Order Elliptic
Problems
C.E. Powell

Raviart-Thomas mixed finite element approximation to scalar diffusion problems
is well understood.  The method gives rise to a symmetric and indefinite
linear system, that can be solved in a variety of ways.  For example,
transformations to associated positive definite systems are common.  However,
solving the original indefinite system using minimal residual schemes is not
problematic.  Incorporating fast solvers for Laplacian or generalised
diffusion operators into block diagonal preconditioners for the mixed system
is a simple and highly effective technique.

The existence of freely available black-box algebraic multigrid codes makes
this a feasible and unified preconditioning strategy for a wide class of
saddle-point problems.  Further, it offers the possibility to treat problems
with diverse coefficients in the same framework.  For variable and
discontinuous coefficient problems, known preconditioning strategies can lose
robustness.  The linear systems are generally ill-conditioned with repect to
both the discretisation parameter and the PDE coefficients.

We discuss a robust, black-box approach to preconditioning the mixed diffusion
problem, using freely available software.  The key tools are diagonal scaling
for a weighted mass matrix and an algebraic multigrid V-cycle applied to a
sparse approximation to a generalised diffusion operator.  Eigenvalue bounds
are derived for the preconditioned system matrix.  Numerical results are
presented to illustrate that the preconditioner is optimal with respect to the
discretisation parameter and is robust with respect to the PDE coefficients.

[1] Powell, C.E., Silvester, D., Optimal preconditioning for Raviart-Thomas
mixed formulation of second-order elliptic PDEs, submitted to SIAM J. Matrix
Anal., 2002

[2] Powell, C.E., Silvester, D., Black-box preconditioning for mixed
formulation of self-adjoint elliptic PDEs,
 Manchester Centre for
Computational Mathematics Report 415, 2002.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Powell
    -------------
                             * * * * * * * * * *

Cache Aware Multigrid on AMR Hierarchies
Danny Thorne

A cache optimized multilevel algorithm to solve variable coefficient elliptic
boundary value problems on adaptively refined structured meshes is described
here.  The algorithm is optimized to exploit the cache memory subsystem.
Numerical results are given demonstrating the efficiency of the cache
optimization.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Thorne
    -------------

                             * * * * * * * * * *

Overlapping Schwarz preconditioner for the mixed formulation of plane
elasticity
Yanqiu Wang

Recently a stable pair of finite element spaces for the mixed formulation of
the plane elasticity system has been developed by Arnold and Winther.  Here we
construct a two-level overlapping Schwarz preconditioner for the resulting
discrete system.  Essentially, this reduces to finding an efficient
preconditioner for the form

    ( . , . )+(div . ,div . ) 

in the symmetric tensor space H(div).  The main difficulty comes from the well
known complexity of building preconditioners for the div operator.  We solve
it by taking a decomposition similar to the Helmholz decomposition.  Both
additive and multiplicative preconditioners are studied, and the conditioner
numbers are shown to be uniform with respect to the mesh size.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Wang
    -------------

                             * * * * * * * * * *

Nonconforming V-cycle and F-cycle Multigrid methods for the biharmonic problem
using the Morley element

Jie Zhao

The asymptotic behavior of multigrid V-cycle and F-cycle algorithms for the
biharmonic problem using the Morley element are presented in this talk.  By
the use of an additive theory, we show that the contraction numbers of the
algorithms can be uniformly improved as the number of smoothing steps
increases, without assuming full elliptic regularity.

We describe the critical estimates required for the additive theory.
Experimental results are also presented for the algorithms on convex and
nonconvex domains.  The results are consistent with the theoretical estimates.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Zhao
    -------------

                             * * * * * * * * * *

On an Energy Minimizing Basis for Algebraic Multigrid Methods
Ludmil Zikatanov and Jinchao Xu

This paper is devoted to the study of an energy minimizing basis first
introduced by Chan, Smith and Wan in 2000 for algebraic multigrid methods.
The basis will be first obtained in an explicit and compact form in terms of
certain local and global operators.  The basis functions are then proven to be
locally homonic functions on each coarse grid ``elememt''.  Using these new
results, it is illustrated that this basis can be numerically obtained in an
optimal fashion.  In addition to the intended application for algebaric
multigrid method, the energy minimizing basis may also be applied for
numerical homogenization.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Zikatanov
    -------------

                             * * * * * * * * * *

Adaptive multigrid via subcycling on complementary grids
Tim Chartier and Edmond Chow

Considerable efforts in recent multigrid research have concentrated on
algebraic multigrid schemes.  A vital aspect of this work is uncovering
algebraically smooth error components in order to construct effective
multigrid components.  Adapative or self-correcting multigrid schemes expose
algebraically smooth error, analyze the effectiveness of the resulting
multigrid algorithm and adjust the cycling as needed in order to improve the
rate toward convergence.  This talk will discuss an adaptive multigrid method
that uses relaxation and subcycling on complementary grids as an evaluative
tool in correcting MG cycling.  The particular implementation of this idea
manages smooth error in a manner analogous to spectral AMGe.  Numerical
results will be included.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Chartier
    -------------

                             * * * * * * * * * *

Acceleration Techniques for the Spectral Element Ocean Model Methodology
Craig C. Douglas and Gundolf Haase

A mathematical model and computational results are presented for wind driven
ocean modeling based on the Spectral Ocean Element Method (SEOM).  The method
features advanced algorithms, based on h-p type finite element methods,
allowing accurate representation of complex coastline and oceanic bathymetry,
variable lateral resolution, and high order solution of the three dimensional
oceanic equations of motion.  SEOM is robust, accurate over a many year
simulation, and scales extremely well on a wide variety of parallel computers
including traditional supercomputers and clusters.  Acceleration techniques
will be defined that lead to significant speedups.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Douglas
    -------------

                             * * * * * * * * * *

FAS interpolation and smoother components: A comparative study
Miguel Dumett and Carol Woodward

We study the performance of some FAS components in a multigrid V-cycle for
nonlinear anisotropic reaction diffusion equations.  We investigate the
efficiency of using operator-dependent grid transfer operators and compare the
performance of full system and point smoothers.  Since interpolation operators
and coarse grids are solution dependent, we study the issue of when to refresh
both.  These studies utilize non-Galerkin coarse equations.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Dumett
    -------------

                             * * * * * * * * * *

Multigrid Accelleration of the Horn-Schuck Algorithm for the Optical Flow
Problem
Ulrich Ruede and El Mostafa Kalmoun

It is currently recognized that optical flow computation has many applications
in image processing, pattern recognition, data compression, and biomedical
technology.  Differential approaches, which estimate velocity vectors from the
spatial and temporal intensity derivatives are the most common visited
techniques in the literature.  The basic assumption behind that is the
intensity variations are weak and only due to a movement in the image plan.
This constant brightness assumption leads to an ill-posed problem that can
only be solved by imposing additional assumptions.  A standard technique,
which is due to to Horn and Schunck, is to require the flow field to be smooth
by means of a standard regularization approach.  This results in a system of
elliptic PDEs of reaction diffusion type.  The second order terms are induced
by the regularization and become straightforward Laplace operators.  The zero
order terms are linear (but variable) and are computed from the derivatives of
the image data.  Since the image data (and even more so its derivatives) are
usually nonsmooth, this poses some nontrivial problems.  The PDEs are usually
discretized by standard finite differences.  The Horn-Schuck algorithm is the
standard way to discretize and solve the PDEs.  In multigrid terminology, it
is simply a coupled pointwise relaxation.  As expected, it has acceptable
convergence only if the zero-order terms dominate but the performance is poor,
when the diffusion character dominates.  In this case, a multigrid strategy
can be expected to provide a significant accelleration by allowing a quick
propagation of information from non-zero flow field regions into homogeneous
or untextured image areas.  The Horn-Schunck algorithm can still be used as a
smoother for such a multigrid method.  The most difficult aspect is to deal
with the strongly discontinuous coefficients in an efficient way.  This will
be discussed in our presentation.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Kalmoun
    -------------

                             * * * * * * * * * *

Algebraic Multilevel Preconditioning Based on Element Agglomeration
Johannes K. Kraus

We consider an algebraic multilevel preconditioning method for SPD matrices
resulting from finite element discretization of elliptic PDEs.  The method is
based on element agglomeration, and, in particular, designed for non-M
matrices.  Granted that the element matrices at the fine-grid level are given,
we further assume that we have access to some algorithm that performs a
reasonable agglomeration of fine-grid elements at any given level.  The
coarse-grid element matrices are simply Schur complements computed from the
locally assembled fine-grid element matrices, i.e., agglomerate matrices.
Hence, these matrices can be assembled to a global approximate Schur
complement.  The elimination of fine-degrees of freedom in the agglomerate
matrices is done without neglecting any fill-in.  This offers the opportunity
to construct a new kind of incomplete LU factorization of the pivot matrix at
every level, which is done by means of a slightly modified assembling process.
Based on these components an algebraic multilevel preconditioner can be
defined for more general SPD matrices.  The method can also be applied to
systems of PDEs.  A numerical analysis shows its efficiency and robustness.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Kraus
    -------------

                             * * * * * * * * * *

PHAML: A Parallel Adaptive Multilevel Program for Elliptic PDEs
William F. Mitchell

A new program for the solution of elliptic partial differential equations,
PHAML, has recently been released.  PHAML stands for Parallel Hierarchical
Adaptive MultiLevel.  It is written in Fortran 90, and compiles to a library
of routines to be called by the application program.  The primary routine
solves an elliptic boundary value or eigenvalue problems using finite elements
with bisection adaptive refinement of triangles, a hierarchical multigrid
solver, and distributed memory message passing parallelism with MPI or PVM.
Examples illustrate how the program can be used to solve parabolic problems,
nonlinear problems and systems of equations.  Optional additional libraries
that PHAML can make use of include OpenGL for graphics, Zoltan for grid
partitioning, and PETSc for linear system solvers, through which PHAML
provides an environment for experimenting with different methods.  In this
talk, we will describe the design and use of the PHAML software.  PHAML can be
obtained at http://math.nist.gov/phaml.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Mitchell
    -------------

                             * * * * * * * * * *

Accurate multigrid techniques for computing singular solutions of elliptic
problems.
Ulrich Ruede, Harald Koestler, and Marcus Mohr

Generalized functions occur in many practical applications as source terms in
partial differential applications.  Typical examples are point sources and
sinks in porous media flow that are described by Dirac delta functions or
point loads and dipoles as source terms inducing electrostatic potentials.  We
are particularly interested in bioelectric field computations where the source
terms are modeled by dipoles and where the computational goal is to locate
dipole sources as accurately as possible from electroencephalographic
measurements.

For analyzing the accuracy of such computations, standard techniques cannot be
used since they rely on global smoothness.  This is both true for Sobolev
space arguments for finite element based methods, and for continuity and
differentiability arguments in finite difference analysis.  At the
singularity, the solution tends to infinity and therefore standard error norms
will not even converge.

In this presentation we will demonstrate that these difficulties can be
overcome by using other metrics to measure accuracy and convergence of the
numerical solution.  Only minor modifications to the discretization and solver
are necessary to obtain the same asymptotic accuracy and efficiency as for
regular and smooth solutions.  In particular, no adaptive refinement is
necessary and it is also unnecessary to use techniques which make use of the
analytic knowledge of the singularity.  Our method relies simply on a
mesh-size dependent representation of the singular sources constructed by
appropriate smoothing.  It can be proved that the pointwise accuracy is of the
same order as in the regular case.  The error coefficient depends on the
location and will deteriorate when approaching the singularity where the error
estimate breaks down.  Our approach is therefore useful for accurately
computing the global solution, except in a small neighborhood of the singular
points.  In the talk we will demonstrate how these techniques can be
integrated into a multigrid solver exploiting additional techniques for
improving the accuracy, such as Richardson and tau-Extrapolation.  The talk is
a follow-up to a paper presented in Copper Mountain in 1987.


    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Mohr
    -------------

                             * * * * * * * * * *

Experiences with algebraic multigrid for a 2D and 3D biological
respiration-diffusion model

Dominik Smits, Stefan Vandewalle, Nico Scheerlinck, and Bart Nicola

At the Laboratory of PostHarvest Technology of the University of Leuven, a
respiration-diffusion model is being developed and studied for the oxygen
consumption and carbon dioxyde production inside harvested fruit (in
particular for the Conférence Pear).  The research aims at a better
understanding of the respiratory activity of fruit and the causes that affect
the onset of certain fruit diseases (e.g., the diseases 'brown and hollow' or
'core breakdown').  The current mathematical model consist of a set of two
coupled non-linear reaction diffusion equations, defined on a two- or
three-dimensional domain, with a mixed type of boundary condition.

In this talk, we will present our experiences with using an algebraic
multigrid method for solving the set of equations obtained after a finite
element discretization of the mathematical model.  We have concentrated on the
use of the recent version of the systems AMG code developed by Klaus Stüben,
at the Fraunhofer Institute for Algorithms and Scientific Computing, Sankt
Augustin, Germany.  We will consider its application for solving both the
steady-state problem and the time-evolution problem.  For the latter case, we
will discuss the use of different time-discretisation methods of backward
differentiation or implicit Runge-Kutta type.  The AMG-results will be
compared with the results obtained with classical, single-level solvers.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Smits
    -------------

                             * * * * * * * * * *

Towards Textbook Multigrid Efficiency for Computational Fluid Dynamics:
Applications to Stagnation Flows
J. L. Thomas, B. Diskin, and R. Mineck

The ingredients for attaining textbook multigrid efficiency in solution of CFD
problems are discussed as they arise in application to stagnation flow
problems.  The ingredients include principal linearization, factorizable
schemes, local relaxation, etc.  Textbook multigrid efficiency is demonstrated
for stagnation flows with a pressure-equation formulation of the
incompressible fluid equations.  Both inviscid and viscous flows over a range
of Reynolds number are considered.  Convergence of algebraic errors below
discretization errors in one full multigrid cycle is attained using
flow-dependent relaxation schemes.  The residual convergence rates for the
systems are the same as for scalar elliptic equations on the same grid.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Thomas
    -------------

                             * * * * * * * * * *

Algebraic Multigrid Methods for the Oseen Problem
Markus Wabro

We present and compare concepts for algebraic multigrid (AMG) solvers for the
Oseen linearization of the Navier-Stokes equations for incompressible fluids.

The two main strategies in this area are the following.  The first one is the
segregated approach, where the equations for velocity and pressure are
iteratively decoupled, and AMG is used for the solution of the resulting
scalar problems (examples in this direction are Uzawa or SIMPLE schemes, or
preconditioners for Krylov-space methods, e.g.  as introduced by Silvester,
Wathen et al., 2001).

The main topic of the talk will be the second strategy, the coupled approach,
where an AMG method is developed for the whole saddle-point system.  We
present the ingredients of this method (smoothers, coarse level construction)
and pinpoint a major problem, the stability of the coarse-level systems.

Finally, we will show how the different methods perform in "real life"
situations, i.e.  when flows in complex 3D domains have to be simulated.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Wabro
    -------------

                             * * * * * * * * * *

First-Order System Least Squares (FOSLS) for Geometrically-Nonlinear
Elasticity
Chad Westphal

In this talk we discuss developments in a first-order system least squares
(FOSLS) approach for the numerical approximation of the solution of the
equations of geometrically-nonlinear elasticity.  We follow a Newton-FOSLS
algorithm where each linear step is solved as a two-stage, first-order system
under a least squares finite element discretization.  With appropriate
regularity we show H1 equivalence of the quadratic part of the FOSLS
functional norm in the case of pure displacement boundary conditions.  Results
hold for deformations near the reference configuration, a set we show to be
largely coincident with the set of deformations allowed by the physical model.
In this regime the discrete systems that result from using standard finite
element subspaces of H1 can be solved with optimal complexity.  Numerical
results are given for both pure displacement and mixed boundary conditions and
confirm optimal multigrid performance and finite element approximation
properties.

    Editor's Note: see http://www.mgnet.org/mgnet-cm2003.html#Westphal
    -------------

------------------------------

End of MGNet Digest
**************************