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
 

World Wide Web:  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.etl.go.jp/mgnet or
                 http://www.nchc.gov.tw/RESEARCH/Math/mgnet/www/mgnet.html

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

Volume 10, Number 8 (approximately August 31, 2000)

Today's topics:

     Maxwell Equations' Paper by Gopalakrishnan and Pasciak
     AMG paper by Beck
     New book available
     AMG Presentation at Strobl - Bayreuther and Miehe
     AMG Presentation at Strobl - Beck
     AMG Presentation at Strobl - Bollhoefer
     AMG Presentation at Strobl - Douglas and Iskandarani
     AMG Presentation at Strobl - Henson and Vassilevski
     Contents of Numerical Linear Algebra with Applications

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

From: Joe Pasciak 
Subject: Maxwell Equations' Paper

Overlapping Schwarz Preconditioners for
Indefinite Time Harmonic Maxwell Equations

Jayadeep Gopalakrishnan and Joseph E. Pasciak

Department of Mathematics
Texas A&M
College Station, Texas

Abstract.  

Time harmonic Maxwell equations in lossless media lead to a second order
differential equation for electric field involving a differential operator
that is neither elliptic nor definite.  A Galerkin method using Nedelec spaces
can be employed to get approximate solutions numerically .  The problem of
preconditioning the indefinite matrix arising from this method is discussed
here.  Specifically , two overlapping Schwarz methods will be shown to yield
uniform preconditioners.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

From: Craig Douglas 
Subject: AMG paper by Beck

Algebraic Multigrid by Component Splitting for
Edge Elements on Simplicial Triangulations

Rudolf Beck

Konrad-Zuse-Zentrum fur Informationstechnik Berlin
Takustrasse 7
D-14195 Berlin-Dahlem
Germany

Preprint SC 99-40 (December 1999)   

Abstract

Our focus is on Maxwell's equations in the low frequency range; two specic
applications we aim at are time-stepping schemes for eddy current computations
and the stationary double-curl equation for time-harmonic fields.  We assume
that the computational domain is discretized by triangles or tetrahedrons; for
the nite element approximation we choose Nedelec's H(curl)-conforming edge
elements of the lowest order .

For the solution of the arising linear equation systems we devise an algebraic
multi-grid preconditioner based on a spatial component splitting of the field.
Mesh coarsening takes place in an auxiliary subspace, which is constructed
with the aid of a nodal vector basis.  Within this subspace coarse grids are
created by exploiting the matrix graphs.  Additionally , we have to cope with
the kernel of the curl-operator, which comprises a considerable part of the
spectral modes on the grid.  Fortunately, the kernel modes are accessible via
a discrete Helmholtz decomposition of the fields; they are smoothed by
additional algebraic multigrid cycles.

Numerical experiments are included in order to assess the efcacy of the
proposed algorithms.

Key words:  Algebraic multigrid, mesh coarsening, edge elements, Nedelec
spaces, Maxwell's equations

AMS(MOS) subject classications:  65N55, 65N30, 65F10, 35Q60

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Mon, 28 Aug 2000 12:51:04 -0500 (CDT)
From: Zhangxin Chen 
Subject: New book available

Numerical Treatment of Multiphase Flows in Porous Media,
Zhangxin Chen, Richard E. Ewing, and Z.-C. Shi, Eds.

http://www.springer.de/cgi-bin/search_book.pl?isbn=3-540-67566-3
e-mails: orders@springer-ny.com or orders@springer.de

Lecture Notes in Physics, Vol. 552, Springer-Verlag

2000. XXI, 445 pages, 3-540-67566-3, 
Hardcover DM 164; US$ 92.64

This book describes in detail the current, state-of-the-art numerical
treatment and simulation of multiphase flows in porous media.  The porous
media considered range from ordinary to fractured and deformable media, the
models treated from single-phase compressible flow to multiphase
multicomponent flow with mass interchange, the numerical methods studied from
standard finite difference and finite element methods to nonstandard mixed
finite element and characteristics-based techniques, and the computational
algorithms encompass everything from classical iterative solvers to modern
multigrid and domain decomposition approaches.  Addressing many problems
originating from the applied geosciences, the book focuses on their common
mathematical and computational aspects.  It will serve as an excellent
research reference for all geoscientists, mathematicians, physicists, and
engineers who work in the mathematical modeling and numerical simulation of
multiphase flows in porous media.

Contents

Introduction--Mathematical and Numerical Techniques in Energy
and Environmental Modeling,
Zhangxin Chen and Richard E. Ewing, 1--21

Domain Decomposition for Some Transmission Problems
in Flow in Porous Media,
Clarisse Alboin, Jerome Jaffre, Jean E. Roberts,
Xuewen Wang, and Christophe Serres, 22--34

Numerical Subgrid Upscaling of Two-Phase Flow
in Porous Media,
Todd Arbogast, 35--49

Numerical Simulation of Multiphase Flow in Fractured
Porous Media,
Peter Bastian, Zhangxin Chen, Richard E. Ewing, Rainer Helmig,
Hartmut Jakobs, and Volker Reichenberger, 50--68

The Modified Method of Characteristics
for Compressible Flow in Porous Media,
Aijie Cheng and Gaohong Wang, 69--79

A Numerical Algorithm for Single Phase Fluid Flow
in Elastic Porous Media,
Hongsen Chen, Richard E. Ewing, Stephen L. Lyons,
Guan Qin, Tong Sun, and David P. Yale, 80--92

On the Discretization of Interface Problems
with Perfect and Imperfect Contact,
Tatiana Chernogorova, Richard E. Ewing, Oleg Iliev,
and Raytcho~Lazarov, 93--103

Finite Element Analysis for Pseudo-Hyperbolic
Integral-Differential Equations,
Xia Cui, 104--115

A CFL-Free Explicit Scheme with Compression
for Linear Hyperbolic Equations,
Ronald A. DeVore, Hong Wang, Jiang Guo Liu,
and Hong Xu, 116--123

Maximizing Cache Memory Usage for
Multigrid Algorithms for Applications
of Fluid Flow in Porous Media,
Craig C. Douglas, Jonathan Hu, Mohamed Iskandarani,
Markus Kowarschik, Ulrich Rude, and Christian Weiss, 124--137

A Locally Conservative Eulerian-Lagrangian Method
for Flow in a Porous Medium of a Mixture
of Two Components Having Different Densities,
Jim Douglas, Jr., Felipe Pereira, and Li Ming Yeh, 138--155

Validation of Non-Darcy Well Models Using Direct
Numerical Simulation,
Vladimir A. Garanzha, Vladimir N. Konshin,
Stephen L. Lyons, Dimitrios V. Papavassiliou,
and Guan Qin, 156--169

Mathematical Treatment of Diffusion Processes of Gases
and Fluids in Porous Media,
Norbert Herrmann, 170--178

Implementation of a
Locally Conservative Eulerian-Lagrangian Method
Applied to Nuclear Contaminant Transport,
Chieh Sen Huang and Anna M. Spagnuolo, 179--189

Application of a Class of Nonstationary Iterative
Methods to Flow Problems,
Xiuren Lei and Hong Peng, 190--194

Reservoir Thermal Recover Simulation
on Parallel Computers,
Baoyan Li and Yuanle Ma, 195--207

A Class of Lattice Boltzmann Models
with the Energy Equation,
Yuanxiang Li, Shengwu Xiong, and Xiufen Zou, 208--215

Block Implicit Computation of Flow Field
in Solid Rocket Ramjets,
Zhibo Ma and Jianshi Zhu, 216-221

Stable Conforming and Nonconforming Finite
Element Methods for the Non-Newtonian Flow
Pingbing Ming and Zhong Ci Shi, 222--232

Numerical Simulation of Compositional Fluid Flow
in Porous Media,
Guan Qin, Hong Wang, Richard E. Ewing, and

Magne S. Espedal, 232--243

Parallelization of a Compositional Reservoir Simulator,
Hilde Reme, Geirge Oye, Magne S. Espedal,
and Gunnar E. Fladmark, 244--266

Relationships Among Some Conservative
Discretization Methods,
Thomas F. Russell, 267--282

Parallel Methods for Solving Time-Dependent
Problems Using the Fourier-Laplace Transformation,
Dongwoo Sheen, 283--291

Cascadic Multigrid Methods for
Parabolic Pressure Problems
Zhong Ci Shi and Xuejun Xu, 292--298

Estimation in the Presence of Outliers:
The Capillary Pressure Case,
Sam Subbey and Jan Erik Nordtvedt, 299--310

A Comparison of ELLAM with ENO/WENO Schemes
for Linear Transport Equations,
Hong Wang and Mohamed Al Lawatia, 311--323

An Accurate Approximation to Compressible Flow
in Porous Media with Wells,
Hong Wang, Dong Liang, Richard E. Ewing,
Stephen L. Lyons, and Guan Qin, 324--323

Fast Convergent Algorithms for Solving 2-D
Integral Equations of the First Kind,
Yan Fei Wang and Ting Yan Xiao, 333--345

A Two-Grid Finite Difference Method
for Nonlinear Parabolic Equations,
Ziting Wang and Xianggui Li, 345--350

A Compact Operator Method
for the Omega Equation,
Francisco R. Villatoro and Jesus Garci a-Lafuente, 351--361

Domain Decomposition Algorithm
for a New Characteristic Mixed Finite Element
Method for Compressible Miscible Displacement
Danping Yang, 362--372

A Boundary Element Method for Viscous Flow
on Multi-Connected Domains,
Dequan Yang, Tigui Fan, and Xinyu Yang, 373--377

A Characteristic Difference Method
for 2D Nonlinear Convection-Diffusion Problems,
Xi Jun Yu and Yonghong Wu, 378--389

Fractional Step Methods for Compressible
Multicomponent Flow in Porous Media,
Yirang Yuan, 390--403

A Model and Its Solution Method for a Generalized
Unsteady Seepage Flow Problem,
Guoyou Zhang, Tigui Fan, Zhongsheng Zhao, and
Dequan Yang, 404--408

Domain Decomposition Preconditioners for
Non-selfconjugate Second-Order Elliptic Problems,
Huaiyu Zhang and Jiachang Sun, 409--418

Performance of MOL for Surface Motion
Driven by a Laplacian of Curvature,
Wen Zhang and Ian Gladwell, 419--429

A High-Order Upwind Method for Convection-Diffusion
Equations with the Newmann Boundary Condition,
Weidong Zhao, 430--441

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

Date: Thu, 31 Aug 2000 11:12:07 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Bayreuther and Miehe

           Construction of homogenization based transfer operators

                     Claus Bayreuther and Christian Miehe

                                   Abstract

This talk deals with an application of homogenization techniques to the
construction of intergrid transfer operators in the case of linear elastic
heterogeneous materials.  So far, this strategy can only be accomplished to
regular meshes.  However, we will discuss an extension to irregular meshes
which represents an alternative to algebraic transfer operators.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Thu, 31 Aug 2000 11:12:07 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Beck

         Algebraic Multigrid for Edge Elements by Component Splitting

                                 Rudolf Beck

                                   Abstract

This talk is about the solution of Maxwell's equations in the low frequency
range; the applications we aim at are implicit time-stepping schemes for eddy
current computations and the stationary double-curl equation for time-harmonic
fields.  We assume that the computational domain is discretized by Nedelec's
H(curl)-conforming edge elements of the lowest order.

Algebraic coarsening strategies for such finite element spaces are harder to
devise than in the case of Lagrange-type elements.  The difficulties are
basically due to the geometric structure of the vectorial shape functions.

The solution presented here relies on a spatial component splitting of the
fields, where mesh coarsening takes place in an auxiliary subspace constructed
with the aid of Lagrange-type basis functions.  Within this subspace coarse
grids are created recursively by an advancing-front algorithm, which merely
exploits the matrix graphs.

Unfortunately, the non-trivial kernel of the curl-operator cannot be tackled
within this setting.  Thus we resort to a discrete Helmholtz decomposition of
the fields, allowing an efficient smoothing of the kernel modes by a separate
algebraic multigrid cycle.

Some numerical experiments will be presented in order to assess the efficacy
of the proposed algorithms.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Thu, 31 Aug 2000 11:12:07 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Bollhoefer

         AMG Preconditioners for Sparse Approximate Inverse Matrices

                              Matthias Bollhoefer
                             Dep. of Mathematics
                      Chemnitz University of Technology
                               D-09107 Chemnitz
                                   Germany

                                   Abstract

In this talk we discuss the construction of an algebraic multilevel method
which is adapted to a given sparse approximate inverse of a symmetric positive
definite matrix.  The idea behind this construction is a heuristic
observation, that sparse approximate inverse preconditioners often approximate
the large eigenvalues of the given matrix quite well, while the smaller ones
are only fairly poor approximated.  The AMG consists of a strategy that uses
suitably selected columns of the scaled residual matrix to construct the
restriction/prolongation operator.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Thu, 31 Aug 2000 11:12:07 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Douglas and Iskandarani

                 Using a Multilayer Ocean Model on Clusters
                     versus a Traditional Supercomputer

                              Craig C. Douglas
                       Department of Computer Science
                           University of Kentucky
                            325 McVey Hall - CCS
                        Lexington, KY 40506-0045, USA
                            douglas@ccs.uky.edu

                             Mohamed Iskandarani
                  Institute of Marine and Coastal Sciences
                             Rutgers University
                                P.O. Box 231
                      New Brunswick, NJ 08903-0231, USA
                          mohamed@ahab.rutgers.edu

                                  Abstract

We simulate oceanic overflow problems. The long term goal of this research
is to understand both the local dynamics of downslope flows in the ocean and
their role in the Earth's global thermohaline circulation. The modeling of
these flows and their climatic impact is complicated by the inherent range
of spatial scales involved, which extend from the global scale [O(10,000)
km] down to the local scale of the overflows themselves [O(1) km], and by
the intrinsic three dimensionality of the overflow dynamics.

The Spectral Element Ocean Model (SEOM) offers an elegant solution to these
difficulties. It 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's geometrical flexibility permits highly inhomogeneous horizontal
grids. An added advantage of the technique is its scalability. Most of the
computations are carried out at the element level; only interface
information needs to be exchanged between elements. The dual characteristic
of dense and structured local computations, and sparse and unstructured
communication enhances the locality of the computations. The dual
characteristic of dense and structured local computations, and sparse and
unstructured communication enhances the locality of the computations, and
makes SEOM ideally suited for parallel computers.

In this talk we demonstrate what types of cluster machine characteristics
are suitable for solving our problems, how much they cost at what point in
time, and how they compare to a traditional RISC based supercomputer
solution. Our comparisions will note time, money, and aggrevation factors.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Thu, 31 Aug 2000 11:12:07 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Henson and Vassilevski

  AMGe and Element-free AMGe: General algorithms for computing interpolation
                                   weights

            Van Emden Henson (speaker) and Panayot S. Vassilevski

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

                                   Abstract

We propose a new algorithm for constructing the interpolation weights in
algebraic multigrid (AMG).  The rule we propose is related to the
interpolation described in [1] for AMGe, an element-based algebraic multigrid.
There, the interpolation is based on an energy-minimization principle for
finite element applications.

We first review the classical algorithm for constructing interpolation weights
in AMG, examining it from an energy-minimization perspective.  Our purpose is
to extend the classical algorithm in a more general setting than is possible
for the traditional M-matrix applications of classical AMG.  Next we examine
the interpolation rule for AMGe, describing how it is related to the AMG rule
and how it is derived as an energy minimization.  However, in the AMGe method,
as outlined in [1], applying the interpolation rule requires access to the
entries of the individual element stiffness matrices.  Further, these element
matrices must be built on all coarse levels, which is a non-trivial and
expensive task [2].

We propose an approach that does not require access to the element matrices
even on the fine-grid.  However, the additional information we require instead
is knowledge of the so-called rigid body modes, that is, the vectors that span
the null-space of the global (assembled) Neumann-type matrix.  In the simplest
case of scalar elliptic PDE discretization matrices, this is just the constant
vector.  For the elasticity problem, this comprises certain linear functions,
which, in practice, means that one needs the coordinates of the fine-grid
nodes.  In some cases this information may not be available; we use only
constant vectors for these cases.

Based on the rigid body modes, we specify appropriate boundary conditions
which are imposed on a local neighborhood matrix associated with a fine degree
of freedom.  This produces a sort of Neumann-type local (or element) matrix.
Finally, we can simply apply the rule from the AMGe methods based on the
Neumann local matrix.

Some numerical results are given, illustrating the application of the method
on discretized elliptic problems.

                                 References

  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.
     (submitted), 1998.

  2. J. E. Jones and P. S. Vassilevski, AMGe based on element agglomeration,
     (1999) submitted.

This work was performed under the auspices of the U.S.  Department of Energy
by University of California Lawrence Livermore National Laboratory under
contract No. W-7405-Eng-48.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Sun, 03 Sep 2000 17:00:26 +0200
From: Maya Neytcheva 
Subject: Contents of Numerical Linear Algebra with Applications

    Numerical Linear Algebra with Applications
    Volume 7, Issue 1, 2000

A comparison of overlapping Schwarz methods and block preconditioners for
saddle point problems
A. Klawonn and L. Pavarino (pp.1-25)

Efficient computation of the exponential operator for large, sparse,
symmetric matrices
L. Bergamaschi and M. Vianello (pp. 27-45)

    Numerical Linear Algebra with Applications
    Volume 7, Issue 2, 2000

Matrix stretching for sparse least squares problems
M. Adlers and \AA. Bj\"{o}rck (pp. 51-65)

Further Analysis of Minimum Residual Iterations
Y. Saad (pp. 67-93)

    Numerical Linear Algebra with Applications
    Volume 7, Issue 3, 2000

Approximate inverse preconditioning in the parallel solution of
sparse eigenproblems
L. Bergamaschi, G. Pini and F. Sartoretto (pp. 99-116)

Generalization of convergence conditions for restarted GMRES
J. Zitko (pp. 117-131)

A Newton-type algorithm for solving an extremal constrained
interpolation problem
K. Vlachkova (pp. 133-164)

    Numerical Linear Algebra with Applications
    Volume 7, Issue 4, 2000

Iterative computation of derivatives of repeated eigenvalues and the
corresponding eigenvectors
A. Andrew and R. Tan (pp. 151-167)

Comparison between the convergence rates of the Chebyshev method and
the related (2,2)-step methods
X. Li (pp. 169-180)

Perturbation theory and condition numbers for generalized and 
constrained linear least squares
M. Gulliksson and P. Wedin (pp. 181-195)

Real valued iterative methods for solving complex symmetric linear systems
O. Axelsson and A. Kucherov (pp. 197-218)

An accurate parallel block Gram-Schmidt algorithm without
reorthogonalization
D. Vanderstraeten (pp. 219-236)

    Numerical Linear Algebra with Applications
    Volume 7, Issue 5, 2000

A robust algebraic multilevel preconditioner for nonsymmetric M-matrices
Y. Notay (pp. 243-267)

Bounding the growth factor in Gaussian elimination for Buckley's class of
complex symmetric matrices
K. Ikramov and A. Kucherov (pp. 269-274)

Almost block diagonal linear systems: sequential and parallel solution
techniques, and applications
P.Amodio, J,R,Cash, G.Roussos, R.W.Wright, G.Fairweather,
I.Gladwell G.L.Kraut and M.Paprzycki (pp. 275-317)

Efficient and stable solution of structured Hessenberg linear systems
arising from difference equations
L. Gemignani (pp. 319-335)

On the condition numbers associated with the polar factorization
of a matrix
F. Chaitin-Chatelin and S. Gratton (pp. 337-354)

Maya Neytcheva             
Department of Mathematics,  University of Nijmegen     
Toernooiveld 1, 6525 ED Nijmegen, The Netherlands            
tel: +31-24-3652365 __fax: +31-24-3652140
e-mail: neytchev@sci.kun.nl

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

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