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

World Wide Web: or

Today's editor:  Craig Douglas (

Volume 8, Number 5 (approximately May 31, 1998)

Today's topics:

     Important dates
     Using Mutigrid from Numerical Recipes
     Staff Positions at LANL
     New preprints available (D. Arnold et al)
     Copper Mountain 98 Paper by Bermejo and Infante
     Copper Mountain 98 Paper by Lackner and Menikoff
     Some of the new entries in the bibliography


Date: Sun, 31 May 1998 12:31:11 -0500
From: Craig Douglas 
Subject: Important dates

June 15 The date changed for abstracts for the 10th Anniversary International
        GAMM - Workshop on Multigrid Methods, October 5 - 8, 1998 at Bonn
        (Germany).  See

July 20 The absolute deadline for registration for the 11th International
        Conference on Domain Decomposition Methods.  See


Date: Wed, 3 Jun 1998 10:20:22 -0500
From: "Mainkar, Neeraj" 
Subject: Using Mutigrid from Numerical Recipes

I have been struggling with trying to understand how to use the MultiGrid
Algorithm from Numerical Recipes to tailor it to my problem.  I have a 3D
problem and the domain is NOT a simple box.  Isn't there a program out there
which I could use for 3D and has a separate module to specify the geometry and
the boundary conditions of the problem?  Any help would immensely appreciated.

Desperately seeking help
Neeraj Mainkar
Simulations Modeler

    Editor's Note: Clearly UG, Kaskade, and FE++ should work (links can be
    -------------  found on the codes web page for UG and Kaskade and in the
                   links web page for FE++).  However, this is an opportunity
                   for people with new codes to volunteer information to
                   Mainker.  Please cc MGNet.


Date: Mon, 18 May 1998 10:30:43 -0600 (MDT)
From: Michele Benzi 
Subject: Staff Positions at LANL

                 Technical Staff Member Positions
                  Los Alamos National Laboratory

The Scientific Computing Group of Los Alamos National Laboratory is currently
seeking highly qualified researchers in parallel computing and sparse linear
algebra to participate in an interdisciplinary research and development effort
in high performance computing for large-scale physical modeling and simulation
problems.  Researchers with experience in the following categories are
encouraged to apply:

     Parallel Computer Programming
     Numerical Linear Algebra
     Software Library Development
     Parallel Applications Development
     Iterative Linear Solver Methods
     Parallel Preconditioning Techniques
     Geometric and Algebraic Multigrid Methods

Participants will assist in developing innovative algorithms and codes in
conjunction with LANL/DOE projects such as ASCI as well as industrial
collaborations seeking to perform multibillion gridcell computations on
parallel platforms of up to 100 Tflops and beyond.

Expertise and experience in iterative linear solution techniques such as
generalized conjugate gradient methods, preconditioning techniques such as
incomplete LU preconditioning, domain decomposition methods, and geometric
and/or algebraic multigrid and multilevel methods is desirable.
Professional-level experience in programming and software development on
parallel computers using message passing and Fortran 90 or C is desirable.  A
Ph.D. in applied mathematics, computer science or related technical field, or
equivalent combination of technical degree(s) and experience is required.  A
"Q" clearance or ability to obtain one is highly desirable.

Technical staff positions at Los Alamos National Laboratory offer competitive
salaries and a generous benefits package.  Team members have access to
world-class computing facilities and are granted a substantial travel budget.

Further information about currently available positions may be found at

Information regarding the technical content of these efforts can be found at
the Parallel Architectures and Algorithms Team web site

Instructions on how to apply for these positions may be found at

Individuals interested in obtaining further information on these positions may
contact Michele Benzi for further information:

     Michele Benzi
     Los Alamos National Laboratory
     Group CIC-19, MS B-256
     Los Alamos, NM  87545


Los Alamos National Laboratory, a world-class multidisciplinary research
facility, is engaged in state-of-the-art research in areas such as advanced
computing, computer simulation and computer modeling, sensors and
instrumentation for complex experimentation and measurements, nuclear weapons,
earth and environmental science, bioscience and biotechnology, materials
science, and nuclear science, plasmas, and beams.  Los Alamos is located
between the majestic Sangre de Cristo and Jemez mountain ranges of northern
New Mexico and is near the cultural and resort centers of Santa Fe and Taos,

Los Alamos is an equal-opportunity employer.


Date: Wed, 13 May 1998 12:29:27 -0400
From: "Douglas N. Arnold" 
Subject: New preprints available (D. Arnold et al)

Dear Colleagues:

This note is to let you know of four recent preprints that have been added to
my Web page and which may be of interest to you.  These are listed below,
first titles only, and then full bibliographic information.  You can view or
download these papers at, or
retrieve them by anonymous ftp at, directory pub/dna/papers.
These bring to 32 the number of my papers available online.

If you would prefer that I mail you a hardcopy of one or more of these, just
let me know.

Regards -- Doug

New titles as of 5/98:

  Multigrid preconditioning in H(div) on non-convex polygons

  Locally adapted tetrahedral meshes using bisection

  Adaptive finite elements and colliding black holes

  Multigrid in H(div) and H(curl)
==> hdivn-info.txt <==
Title:         Multigrid preconditioning in H(div) on non-convex polygons
Authors:       Douglas N. Arnold, Richard S. Falk, and Ragnar Winther
Source:        Computational and Applied Mathematics
Status:        To appear

Abstract:  In an earlier paper we constructed and analyzed a multigrid
preconditioner for the system of linear algebraic equations arising from the
finite element discretization of boundary value problems associated to the
differential operator I - grad div.  In this paper we analyze the procedure
without assuming that the underlying domain is convex and show that, also in
this case, the preconditioner is spectrally equivalent to the inverse of the
discrete operator.

Keywords: preconditioner, finite element, multigrid, nonconvex domain
Subj. class.:  65N55, 65N30
FTP site:
File name:     pub/dna/papers/hdivn.dvi
File format:   TeX DVI file
File name:     pub/dna/papers/
File format:   PostScript file

==> bistet-info.txt <==
Title:         Locally adapted tetrahedral meshes using bisection
Authors:       Douglas N. Arnold, Arup Mukherjee, and Luc Pouly
Source:        SIAM Journal on Scientific Computing
Status:        Submitted

Abstract:  We present an algorithm for the construction of locally adapted
conformal tetrahedral meshes.  The algorithm is based on bisection of
tetrahedra.  A new data structure is introduced, which simplifies both the
selection of the refinement edge of a tetrahedron and the recursive refinement
to conformity of a mesh once some tetrahedra have been bisected.  We prove
that repeated application of the algorithm leads to only finitely many
tetrahedral shapes up to similarity, and bound the amount of additional
refinement that is needed to achieve conformity.  Numerical examples of the
effectiveness of the algorithm are presented.

Keywords:      bisection, tetrahedral meshes, adaptive refinement, similarity classes, finite elements
Subj. class.:  65N50
FTP site:
File name:     pub/dna/papers/bistet.dvi
File format:   TeX DVI file
File name:     pub/dna/papers/
File format:   PostScript file
Note:          PostScript version contains figures

==> hdivcurl-info.txt <==
Title:         Multigrid in H(div) and H(curl)
Authors:       Douglas N. Arnold, Richard S. Falk, and Ragnar Winther
Source:        Numerische Mathematik
Status:        Submitted

Abstract:  We consider the solution of systems of linear algebraic equations
which arise from the finite element discretization of variational problems
posed in the Hilbert spaces H(div) and H(curl) in three dimensions.  We show
that if appropriate finite element spaces and appropriate additive or
multiplicative Schwarz smoothers are used, then the multigrid V-cycle is an
efficient solver and preconditioner for the discrete operator.  All results
are uniform with respect to the mesh size, the number of mesh levels, and
weights on the two terms in the inner products.

Keywords:      multigrid, preconditioner, mixed method, finite element
Subj. class.:  65N55, 65N30
FTP site:
File name:     pub/dna/papers/hdivcurl.dvi
File format:   TeX DVI file
File name:     pub/dna/papers/
File format:   PostScript file

==> dundee-info.txt <==
Title:         Adaptive finite elements and colliding black holes
Authors:       Douglas N. Arnold, Arup Mukherjee, and Luc Pouly
Source:        Numerical Analysis 1997: Proceedings of the 17th Biennial Conference on Numerical Analysis
Status:        To appear

Abstract:  According to the theory of general relativity, the relative
acceleration of masses generates gravitational radiation.  Although
gravitational radiation has not yet been detected, it is believed that
extremely violent cosmic events, such as the collision of black holes, should
generate gravity waves of sufficient amplitude to detect on earth.  The
massive Laser Interferometer Gravitational-Wave Observatory, or LIGO, is now
being constructed to detect gravity waves.  Consequently there is great
interest in the computer simulation of black hole collisions and similar
events, based on the numerical solution of the Einstein field equations.  In
this note we introduce the scientific, mathematical, and computational
problems and discuss the development of a computer code to solve the initial
data problem for colliding black holes, a nonlinear elliptic boundary value
problem posed in an unbounded three dimensional domain which is a key step in
solving the full field equations.  The code is based on finite elements,
adaptive meshes, and a multigrid solution process.  Here we will particularly
emphasize the mathematical and algorithmic issues arising in the generation of
adaptive tetrahedral meshes.

Keywords:      adaptivity, finite elements, black holes, Einstein equations
Subj. class.:  65N50, 65N30, 83C05, 83C35, 83C57
FTP site:
File name:     pub/dna/papers/dundee.dvi
File format:   TeX DVI file
File name:     pub/dna/papers/
File format:   PostScript file
Note:          PostScript version contains figures


Date: Wed, 20 May 98 16:27:45 +0200
From: (Juan Antonio Infante)
Subject: Copper Mountain 98 Paper by Bermejo and Infante

This is to inform you that we put an abstract and a ps-file of our Copper
Mountain 98 paper into the directory /incoming/bermejo at ftp
The paper is definite version of the extended abstract of the Copper Mountain

Thank you very much,
R.Bermejo and J.A. Infante

        A Multigrid Algorithm for Nonlinear Monotone Elliptic Problems

                       R. Bermejo and J.A. Infante

We introduce a FAS multigrid algorithm to find the finite element solution for
a class of nonlinear monotone elliptic problems.  Since the solution of the
problem is equivalent to minimize a strictly convex functional, we use
Polak-Ribiere conjugate gradient method as the nonlinear smoother in our
algorithm.  The advantage in so doing is that we do not have to calculate
derivatives of operators.  We prove the convergence of our algorithm and
illustrate its performance by solving benchmark problems.

    Editor's Note: in or you can directly
    -------------  access it in mgnet/Conferences/CMCIM98/


Date: Fri, 22 May 1998 10:10:23 -0500
Subject: Copper Mountain 98 Paper by Lackner and Menikoff

Multi-Scale Linear Solvers for Very Large Systems Derived from PDEs

        Klaus Lackner (
                Theoretical Division, Mail Stop B-216,
                Los Alamos National Laboratory,
                Los Alamos, NM 87544
        Ralph Menikoff (
                Theoretical Division, Mail Stop B-214,
                Los Alamos National Laboratory,
                Los Alamos, NM 87544

We present a novel linear solver that works well for large systems obtained
from discretizing PDEs.  It is robust and, for the examples we studied, the
computational effort scales linearly with the number of equations.  The
algorithm is based on a wavelength decomposition that combines conjugate
gradient, multi-scaling and iterative splitting methods into a single
approach.  On the surface, the algorithm is a simple preconditioned conjugate
gradient with all the sophistication of the algorithm in the choice of the
preconditioning matrix.  The preconditioner is a very good approximate inverse
of the linear operator.  It is constructed from the inverse of the coarse
grained linear operator and from smoothing operators that are based on an
operator splitting on the fine grid.  The coarse graining captures the long
wavelength behavior of the inverse operator while the smoothing operator
captures the short wavelength behavior.  The conjugate gradient iteration
accounts for the coupling between long and short wavelengths.  The coarse
grained operator corresponds to a lower resolution approximation to the PDEs.
While the coarse grained inverse is not known explicitly, the algorithm only
requires that the preconditioner can be a applied to a vector.  The coarse
inverse applied to a vector can be obtained as the solution of another
preconditioned conjugate gradient solver that applies the same algorithm to
the smaller problem.  Thus, the method is naturally recursive.  The recursion
ends when the matrix is sufficiently small for a solution to be obtained
efficiently with a standard solver.  The local feedback provided by the
conjugate gradient step at every level makes the algorithm very robust.  In
spite of the effort required for the coarse inverse, the algorithm is
efficient because the increased quality of the approximate inverse greatly
reduces the number of times the preconditioner needs to be evaluated.  A
feature of the algorithm is that the transition between coarse grids is
determined dynamically by the accuracy requirement of the conjugate gradient
solver at each level.  Typically, later iterations on the finer scales need
fewer iterations on the coarser scales and the computational effort is
proportional to N rather than NlogN, where N is the number of equations.  We
have tested our solver on the porous flow equation.  On a workstation we have
solved problems on grids ranging in dimension over 3 orders of magnitude, from
103 to 106, and found that the linear scaling holds.
The algorithm works well, even when the permeability tensor has spatial
variations exceeding a factor of 109.

    Editor's Note: in or you can directly
    -------------  access it in mgnet/Conferences/CMCIM98/


Date: Sun, 31 May 1998 14:42:12 -0200
From: Craig Douglas 
Subject: Some of the new entries in the bibliography

The latest version is dated June 4, 1998 and has 3240 entries.

Here are some recent new entries.  As usual, please send additions and


  [1] M. Arioli and C. Fassino, Roundoff error analysis of algo-
          rithms based on Krylov subspace methods, BIT, 36 (1996),
          pp. 189-205.
  [2] C. Ashcraft and J. W. H. Liu, Using domain decomposition
          to find graph bisectors., BIT, 37 (1997), pp. 506-534.
  [3] B. Bialecki and D. S. Dillery, Fourier analysis of Schwarz
          alternating methods for piecewise Hermite bicubic orthogo-
          nal spline collocation, BIT, 33 (1993), pp. 634-646.
  [4] S. C. Brenner and L. Y. Sung, Multigrid methods for the
          computation of singular solutions and stress intensity factors
          II. Crack singularities, BIT, 37 (1997), pp. 623-643.
  [5] C.  Brezinski  and  M.  Redivo  Zaglia,  Look-ahead  in  Bi-
          CGSTAB and other product-type methods for linear systems,
          BIT, 35 (1995), pp. 169-201.
  [6] A. M. Bruaset and A. Tveito, A numerical study of opti-
          mized sparse preconditioners, BIT, 34 (1994), pp. 177-204.
  [7] K. Burrage, Z. Jackiewicz, S. P. Norsett, and R. A.
          Renaut, Preconditioning waveform relaxation iterations for
          differential systems, BIT, 36 (1996), pp. 54-76.
  [8] S. L. Campbell, I. C. F. Ipsen, C. T. Kelley, and C. D.
          Meyer, GMRES and the minimizing polynomial, BIT, 36
          (1996), pp. 664-675.
  [9] T.  F.  Chan,  W.  P.  Tang,  and  W.  L.  Wan,  Wavelet
          sparse approximate inverse preconditioners, BIT, 37 (1997),
          pp. 644-660.
[10]  C.  Christara  and  B.  F.  Smith,  Multigrid  and  multilevel
          methods  for  quadratic  spline  collocation,  BIT,  37  (1997),
          pp. 781-803.
[11]  S. S. Clift and W.-P. Tang, Weighted graph based order-
          ing techniques for preconditioned conjugate gradient meth-
          ods, BIT, 35 (1995), pp. 30-47.
[12]  C.  C.  Douglas,  S.  Malhotra,  and  M.  H.  Schultz,  A
          characterization of mapping unstructured grids onto struc-
          tured grids and using multigrid as a preconditioner, BIT, 37
          (1997), pp. 661-677.
[13]  J. Douglas and C.-S. Huang, An accelerated domain decom-
          position procedure based on Robin transmission conditions,
          BIT, 37 (1997), pp. 678-686.
[14]  J.  Drko~sov'a,   A.  Greenbaum,   M.  Rozlo~znik,   and
          Z.  Strako~s,  Numerical  stability  of  GMRES,  BIT,  35
          (1995), pp. 309-330.
[15]  M.  Dryja  and  W.  Hackbusch,  On  the  nonlinear  domain
          decomposition method, BIT, 37 (1997), pp. 296-311.
[16]  D. J. Evans and G.-Y. Lei, Approximate inverses of multi-
          diagonal matrices and application to the block PCG method,
          BIT, 35 (1995), pp. 48-63.
[17]  S. Farestam and R. B. Simpson, A framework for advancing
          front techniques of finite element mesh generation, BIT, 35
[18]  J. L. Fattebert, An inverse iteration method using multigrid
          for quantum chemistry, BIT, 36 (1996), pp. 509-522.
[19]  A. Greenbaum, M. Rozlo~znik, and Z. Strako~s, Numerical
          behaviour of the modified Gram-Schmidt GMRES implemen-
          tation, BIT, 37 (1997), pp. 706-719.
[20]  I.  Gustafsson,  An  incomplete  factorization  preconditioning
          method based on modification ofelement matrices, BIT, 36
          (1996), pp. 86-100.
[21]  T.  Huckle,  Fast  transforms  for  trdiagonal  linear  equations,
          BIT, 34 (1994), pp. 99-112.
[22]  H. Q. Jin, A note on best conditioned preconditioners, BIT, 34
          (1994), pp. 312-317.
[23]  C.  Lacour  and  Y.  Maday,  Two  different  approaches  for
          matching nonconforming grids: the mortar element method
          and the FETI method, BIT, 37 (1997), pp. 720-738.
[24]  Z. Leyk, Breakdowns and stagnation in iterative methods., BIT,
          37 (1997), pp. 377-403.
[25]  H. L"otzbeyer and U. R"ude, Patch-adaptive multilevel iter-
          ation, BIT, 37 (1997), pp. 739-758.
[26]  O. Nevanlinna, Convergence of Krylov methods for sums of
          two operators, BIT, 36 (1996), pp. 775-785.
[27]  Th.     Rottner,     L.     Lenhardt,     G.     Alefeld,
          and K. Schweizerhof, Nonlinear structural finite element
          analysis using the preconditioned Lanczos method on serial
          and parallel computers, BIT, 37 (1997), pp. 759-769.
[28]  M. A. Saunders, Solution of sparse rectangular systems with
          LSQR and CRAIG, BIT, 35 (1995), pp. 586-602.
[29]  R. B. Simpson, A data base abstraction of describing triangular
          mesh algorithms, BIT, 37 (1997), pp. 138-163.
[30]  S.  Ta'asan  and  H.  Zhang, Fourier-Laplace analysis of the
          multigrid waveform relaxation method for hyperbolic equa-
          tions, BIT, 36 (1996), pp. 831-841.


End of MGNet Digest