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.hpcc.gr.jp/mirrors/mgnet
http://www.nchc.gov.tw/RESEARCH/Math/mgnet/www/mgnet.html

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

Volume 11, Number 4 (approximately April 30, 2001)

Today's topics:

Mirroring of MGNet
Postdoctoral Position at University of Kentucky
Release of PETSc 2.1.0
HELP
Copper Mountain Virtual Proceedings
Tutorial on Cache Based Methods I-III
Multigrid and Schwarz Methods for Time-Harmonic Maxwell Equations
Enhancing the Cache Performance of Multigrid Codes on Structured Grids
Monotonicity Preserving and Total Variation Diminishing ...
Comparisons of Unstructured Multigrid...
Computational and Numerical Mathematics Opportunities at NSF
Multigrid Waveform Relaxation for Anisotropic...
LFA00_2D_scalar Code and Talk
PRISM'2001: Preconditioned Robust Iterative Solution Methods...
Contents Numerical Linear Algebra with Applications
Contents, ETNA

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

Date: Thu, 05 Apr 2001 04:40:29 +0900
From: NISHIDA Akira
Subject: Mirroring of MGNet

I have recently fixed our mirroring configuration of

http://phase.hpcc.gr.jp/mirrors/mgnet/

which was formerly http://phase.etl.go.jp/mgnet/.

NISHIDA Akira
Department of Computer Science, The University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo
113-0033 JAPAN
TEL +81-3-5841-4076
FAX +81-3-3818-1073
E-mail: nishida@is.s.u-tokyo.ac.jp

Editor's Note: This is great news.  A Japanese mirror now works again and
-------------  is up to date.  Thanks!

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

Date: Wed, 11 Apr 2001 01:38:26 -0400 (EDT)
From: Jun Zhang
Subject: Postdoctoral Position at University of Kentucky

Postdoctoral Research Associate Position in High Performance Scientific
Computing, University of Kentucky

A new postdoctoral research associate position is expected to become available
in the Laboratory for High Performance Scientific Computing and Computer
Simulation (HiPSCCS Lab) at the University of Kentucky.  The postdoctoral
associate will be working on a collaborative research project between the
HiPSCCS Lab and an international research organization, to develop parallel
preconditioning techniques and software package for some very large scale
scientific applications and computer simulation.  The following qualifications
are highly desirable:

1.) a PhD in scientific computing or computational sciences;
2.) sound knowledge in modern preconditioning techniques;
3.) good programming skill in Fortran 90 and MPI.

The starting date is in early July.  Although this is a multi-year research
effort, progress is reviewed and contract is renewed annually based on
accomplishment and funding availability.

More information about research activities in the HiPSCCS Lab can be found at
http://www.cs.uky.edu/~hipscns.  If you are interested in this position,
please e-mail your curriculum vitae (with full publication list and e-mail
addresses of three referees) in postscript, pdf or ASCII (no MSWORD, please)
to Jun Zhang at jzhang@cs.uky.edu, or fax it to (859)323-1971.  A postal mail
can be sent to:

Professor Jun Zhang, Director
Laboratory for High Performance Scientific Computing
and Computer Simulation
Department of Computer Science
University of Kentucky
773 Anderson Hall
Lexington, KY 40506-0046
USA

Applicants may be asked to show evidences of programming skill.
Overseas travel may be required for this position.

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

Date: Fri, 13 Apr 2001 15:32:14 -0500 (CDT)
From: Barry Smith
Subject: Release of PETSc 2.1.0

Portable, Extensible Toolkit for Scientific Computation (PETSc)

http://www.mcs.anl.gov/petsc

We are pleased to announce the release of the PETSc 2.1.0 parallel software
libraries for the implicit solution of PDEs and related problems.  New
features of this release include:

(1) a parallel, sparse, symmetric matrix storage format, this includes
support for sequential Cholesky and ICC(k)
(2) a complete   framework    for parallel  linear  multigrid  on
structured grids (for both linear and nonlinear problems)
(3) Mandel's balancing Neumann-Neumann method for scalar PDEs
(4) an interface to  the  Tufo-Fischer highly efficient parallel
coarse grid direct solver library tfs
(5) support  for managing   "composite"  vectors  consisting  of
subvectors that represent conceptually different quantities
(for example, constraints or Lagrange multipliers)
(6) more complete hypertext documentation, including links to
hypertext versions of all the examples and source code

As always, please send bug reports, questions, and requests for new features
to petsc-maint@mcs.anl.gov.

Thanks for your continued support.

The PETSc developers,
Satish, Kris, Bill, Dinesh, Lois, and Barry

Why 2.1.0?  PETSc 2.1.0 represents the cumulation of several years of effort
to convert PETSc 2.0 to use dynamic libraries.  Dynamic libraries allow users
to delay until runtime the choices of what algorithms and data structures to
run without generating enormous executables.

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

Date: Wed, 18 Apr 2001 17:30:49 -0400 (EDT)
From: mehrez@physics.mcgill.ca
Subject: HELP

Please I would like to ask for some help and I would appreciate if you
can guide me.
I am solving Poisson Eq. in 3D using Mutigrid Solver method in a unit
cell. Intially I have used Fixed Boundary Conditions and things are fine.
Now I would like to use periodic Boundary Conditions in two of the
directions and fixed in the third. However, because the total charge in
the system is not 0, I run into instability problems. Do you have any idea
about a Ref. or a direction that I should follow.
Thanks in advance for your help.
Hatem

HATEM MEHREZ
Physics Department, McGill University
3600 University St. 420
Montreal, QP H3A 2T8
Tel:(1-514) 398 8322(W) -  845 9303(H)

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

Date: Sun, 01 Apr 2001 17:35:37 -0500 (EST)
From: Craig Douglas
Subject: Tutorial on Cache Based Methods I-III

Cache Based Methods

Uli Ruede, Markus Kowarschik, and Craig Douglas

Additional contributors:
Jonathan Hu
and
Christian Weiss

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-cm2001.html
-------------

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

Date: Fri, 6 Apr 2001 15:24:05 -0500 (CDT)
From: Jay Gopalakrishnan
Subject: Multigrid and Schwarz Methods for Time-Harmonic Maxwell Equations

Jayadeep Gopalakrishnan
Institute for Mathematics and its Applications
514 Vincent Hall, 206 Church St SE
Minneapolis, MN 55414

Abstract

Time-harmonic Maxwell equations in a lossless cavity 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's
curl-conforming finite elements can be employed to get approximate solutions
numerically.  In this talk, results of [4, 5] on the suitability of multigrid
and Schwarz methods for efficiently solving the resulting indefinite linear
system will be presented.

The analysis of the present work builds on techniques in [1, 6] to overcome
the difficulties caused by the non-ellipticity of the operator.  As in their
analysis, discrete Helmholtz decompositions play a crucial role.  A new and
critical ingredient of our analysis is an estimate on discrete solution
operators of Maxwell equations.  This estimate allows analysis of overlapping
Schwarz methods in the spirit of perturbation arguments in [3], even though
our operator is not elliptic.  It also allows analysis of a \' multigrid
cycle using techniques of [2], although prima facie it may appear that
ellipticity is required for application of these techniques.  In both cases,
the analysis involves comparison of operators with their analogues in positive
definite case.

Of practical importance is the fact that some algorithms that work well in the
elliptic case, fails in our application.  It has now been known for some time
that a multigrid V-cycle with a point-Jacobi smoother is not appropriate for
our problem.  However, we show that a multigrid algorithm with block Jacobi or
block Gauss-Seidel smoother, if the blocks are chosen as in [1], leads to good
convergence rates, provided the coarse mesh used is sufficiently fine.  Our
results also indicate that, in contrast to the elliptic case, replacing
subdomain solves by equivalent operations in overlapping Schwarz methods does
not lead to good results.

References:

[1] D. N. Arnold, R. S. Falk and R. Winther. Multigrid in H(div) and
H(curl). Numer. Math., 85(2):197-217, 2000.
[2] J. H. Bramble, D. Y. Kwak, and J. E. Pasciak. Uniform convergence
of multigrid V-cycle iterations for indefinite and nonsymmetric
problems. SIAM J. Numer. Anal., 31(6):1746-1763, 1994.
[3] X.-C. Cai and O. B. Widlund. Domain decomposition algorithms for
indefinite elliptic problems. SIAM J. Sci. Stat. Comput.,
13(1):243-258, 1992.
[5] J. Gopalakrishnan and J. E. Pasciak. Overlapping Schwarz
preconditioners for indefinite time harmonic Maxwell
equations. Submitted. Available as IMA Preprint 1711, June 2000.
[6] J. Gopalakrishnan, J. E. Pasciak and L. Demkowicz. A multigrid
algorithm for time harmonic Maxwell equations. In preparation.
[4] R. Hiptmair. Multigrid method for Maxwell's equations.
SIAM J. Numer. Anal., 36(1):204-225, 1999.

Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html
-------------

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

Date: Mon, 9 Apr 2001 14:09:55 +0200
From: Markus Kowarschik
Subject: Enhancing the Cache Performance of Multigrid Codes on Structured Grids

Enhancing the Cache Performance of Multigrid Codes on Structured Grids

Markus Kowarschik

System Simulation Group
Department of Computer Science
University of Erlangen-Nuremberg
Germany
markus.kowarschik@cs.fau.de

Abstract

Modern computer architectures use hierarchical memory designs in order to hide
the latencies of accesses to main memory components, which are dramatically
slow in contrast to the floating-point performance of the CPUs.  Current
memory designscommonly involve several levelsof cache memories, which can be
accessed up to a hundred times faster than main memory.  It is well-known that
efflcient program execution can merely be achieved, if the codes respect the
hierarchical memory design.

However, iterative methods are characterized by successive sweeps over data
sets, which -- for representative problems in science and engineering -- are
much too large to fit in cache.

In this paper we present techniques in order to enhance the cache efflciency
of multigrid methods for variable-coefficient problems on regular mesh
structures.  A variety of performance results are provided, showing both
profiling data and the speedups which can be achieved by applying our
optimizations.

Key words.  Computer architecture, high performance computing, cache,
iterative algorithms, multigrid methods

AMS subject classifications.  65N55, 65F10, 65-04

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

Date: Fri, 13 Apr 2001 13:31:48 -0400
From: Dimitri Mavriplis
Subject: Comparisons of Unstructured Multigrid...

Here are my viewgraphs for Copper Mtn.  I now also have a paper to put there,
it is the ICASE report that is due to come out soon, and also submitted to
JCP.

Dimitri Mavriplis -
ICASE  MS 132C
NASA Langley Research Center
Hampton, VA 23681
(757)-864-2213  (Voice)
(757)-864-6134  (FAX)
dimitri@icase.edu
http://www.icase.edu/~dimitri

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

Dimitri Mavriplis
ICASE MS 132C
NASA Langley Research Center
Hampton, VA 23681

Abstract

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

Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html for both.
-------------

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

Date: Fri, 13 Apr 2001 17:17:17 -0400
From: "Mavriplis, Catherine"
Subject: Computational and Numerical Mathematics Opportunities at NSF

As a program officer in Applied Mathematics and Computational Mathematics, the
speaker will give an overview of avenues for requesting funding and discuss
new directions in the mathematical sciences funding landscape.

Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html
-------------

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

Date: Mon, 16 Apr 2001 09:47:02 -0400 (EDT)
From: "Justin W.L. Wan"
Subject: Monotonicity Preserving and Total Variation Diminishing ...

Monotonicity Preserving and Total Variation
Diminishing Multigrid Time Stepping Methods

Antony Jameson

Departmentof Aeronautics and Astronautics
Stanford University
Stanford, CA 94305-4035
jameson@baboon.stanford.edu

Justin Wan

Department of Computer Science
University of Waterloo
Waterloo, Ontario N2L 3G1, Canada
jwlwan@bryce1.uwaterloo.ca

Abstract

We propose a fast multiplicative and additive multigrid time stepping schemes
for solving linear and nonlinear wave equations in one dimension.  The idea is
based on an upwind biased interpolationand residual restriction operators, and
a nonstandard coarse grid update formula for linear equations.  We prove that
the two-level schemes preserve monotonicity and are total variation
diminishing, and the same results hold for the multilevel additive scheme.  We
generalize the idea to nonlinear equations by solving local Riemann problems.
We demonstrate numerically that these schemes are essentially nonoscillatory,
and that the optimal speed of wave propagation of 2M-1 is achieved,
where M is the number of grids.

Keywords.  monotonicity preserving, total variation diminishing, multigrid
time stepping

AMS subject classifications.  65M12, 65M25, 65M55, 65F10

Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html
-------------

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

Date: Tue, 17 Apr 2001 18:10:22 +0200
From: Jan Van Lent
Subject: Multigrid Waveform Relaxation for Anisotropic...

Multigrid Waveform Relaxation for Anisotropic Partial Differential Equations

Jan Van lent and Stefan Vandewalle

Abstract

Multigrid waveform relaxation provides fast iterative methods for the solution
of time-dependent partial differential equations.  In this paper we consider
anisotropic problems and extend multigrid methods developed for the stationary
elliptic case to waveform relaxation methods for the time-dependent parabolic
case.  We study line-relaxation, semicoarsening and multiple semicoarsening
multilevel methods.  A two-grid Fourier-Laplace analysis is used to estimate
the convergence of these methods for the rotated anisotropic diffusion
equation.  We treat both continuous time and discrete time algorithms.  The
results of the analysis are confirmed by numerical experiments.

Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html
-------------

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

Date: Tue, 24 Apr 2001 12:29:55 +0200
From: Roman Wienands
Subject: LFA00_2D_scalar Code and Talk

LFA00_2D_scalar is a Fourier analysis program written in Fortran-77.  Both two
and three grid analysis (LFA) for 2D scalar partial differential equations is
included.  The code supports many variants of coarsening strategies, coarse
grid discretization, prolongation, restriction, and relaxation methods.
This is copyrighted by Roman Wienands, 2000.

Roman Wienands
GMD - Institute for Algorithms and Scientific Computing (SCAI)
D-53754 Sankt Augustin, Germany
email: wienands@gmd.de

Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html or
-------------  http://www.mgnet.org/mgnet-codes.html

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

Date: Thu, 12 Apr 2001 17:42:09 +0200
From: Maya Neytcheva
Subject:  PRISM'2001: Preconditioned Robust Iterative Solution Methods...

CONFERENCE ON
Preconditioned Robust Iterative Solution Methods
for Problems with Singularities (PRISM'2001)
University of Nijmegen, May 21-23, 2001

Special issue of NLA
An issue of the journal Numerical Linear Algebra with Applications''
will be devoted to papers presented at the conference.

A preliminary program can be found at the conference web-page.

Contact address:
PRISM'2001, Department of Mathematics, University of Nijmegen
Toernooiveld 1, 6525 ED Nijmegen, NL
e-mail: prism01@sci.kun.nl
URL:http://www.sci.kun.nl/math/prism01

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

Date: Thu, 12 Apr 2001 17:49:01 +0200
From: Maya Neytcheva
Subject: Contents Numerical Linear Algebra with Applications

NLA web-page http: //www.interscience.wiley.com/jpages/1070-5325

Numerical Linear Algebra with Applications
Volume 8, Issues 1-3, 2001

Reversing the row order for the row-by-row frontal method
J.K. Reid and J.A. Scott (pp. 1-6)

Fast and stable two-way algorithm for diagonal plus semi-separable systems
of linear equations
N. Mastronardi, S. Chandrasekaran and S. Van Huffel (pp. 7-12)

Iterative solution of a coupled mixed and standard Galerkin discretization
method for elliptic problems
R. Lazarov, J. Pasciak and P. Vassilevski (pp. 13-31)

Changing poles in the rational Lanczos method for the
Hermitian eigenvalue problem
K. Meerbergen (pp. 33-52)

Nonequivalence transformation of $\lambda$-matrix eigenproblems and model
embedding approach to model tuning
W.R. Ferng, Wen-Wei Lin, D.J. Pierce and Chern-Shuh Wang (pp. 53-70)

On the Odir iterative method for nonsymmetric indefinite linear systems
A. Chronopoulos and D. Kincaid (pp. 71-82)

Preconditioners for non-Hermitian Toeplitz systems
R.H. Chan, D. Potts and G. Steidl (pp. 83-98)

Superconvergence of finite difference approximations for
convection-diffusion problems
Q. Fang and T. Yamamoto (pp. 99-110)

Reliable preconditioned iterative linear solvers for some
numerical integrators
D. Bertaccini (pp. 111-125)

A note on hyperbolic transformations
D. Janovska and G. Opfer (pp. 127-146)

Minimum residual iteration for a dual-dual mixed formulation of exterior
transmission problems
G. Gatica and N. Heuer (pp. 147-164)

A robust AINV-type preconditioning method for constructing sparse
approximate inverse preconditioners in factored form
S.A. Kharchenko, L.Yu. Kolotilina, A.A. Nikishin, A.Yu. Yeremin (pp. 165-179)

Parallel multisplitting iterative methods for singular M-matrices
Wen Li, Weiwei Sun, K. Liu (pp. 181-190)

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

Date: Sun, 29 Apr 2001 01:53:30 -0400 (EDT)
From: Lothar Reichel
Subject: Contents, ETNA

Table of Contents, Electronic Transactions on Numerical Analysis (ETNA),
vol. 11, 2000. ETNA is available at http://etna.mcs.kent.edu and several
mirror sites as well as on CDROM.

A. Toselli, Neumann-Neumann methods for vector field problems, pp. 1-24.

M. A. Cawood and C. L. Cox, Perturbation analysis for eigenstructure
assignment of linear multi-input systems, pp. 25-42.

B. I. Wohlmuth, A multigrid method for saddle point problems arising from
mortar finite element discretizations, pp. 43-54.

S. Serra Capizzano and C. Tablino Possio, High-order finite difference
schemes and Toeplitz based preconditioners for elliptic problems,
pp. 55-84.

P. Benner, R. Byers, H. Fassbender, V. Mehrmann, and D. Watkins,
Cholesky-like factorizations of skew-symmetric matrices, pp. 85-93.

K. Atkinson, D. D.-K. Chien and J. Seol, Numerical analysis of the
radiosity equation using the collocation method, pp. 94-120.

R. Gutie'rrez J. Rodriguez, and A. J. Sa'ez, Approximation of
hypergeometric functions with matricial argument through their
development in series of zonal polynomials, pp. 121-130.

C. T. H. Baker and E. Buckwar, Continuous Theta-methods for the
stochastic pantograph equation, pp. 131-151.

Publication of volume 12 of ETNA is in progress. Presently the following
papers are available:

G. Meurant, Numerical experiments with algebraic multilevel
preconditioners, pp. 1-65.

H. Zhang, Numerical condition of polynomials in different forms,
pp. 66-87.

M. J. Castel, V. Migallo'n, and J. Penade's, On parallel two-stage methods
for Hermitian positive definite matrices with applications to
preconditioning, pp. 88-112.

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

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