Send mail to:    mgnet@cs.yale.edu             for the digests or bakeoff
Current editor:  Craig Douglas                 douglas-craig@cs.yale.edu
Anonymous ftp repository:    ftp.ccs.uky.edu (128.163.209.106)

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 9, Number 7 (approximately July 31, 1999)

Today's topics:

Important Date
AMG Tutorial on MGNet
Research Studentship at Brunel University
Two Papers (Guo Qingping et al)
Paper by Achi Brandt and Dorit Ron
Two Papers (Suely Oliveira et al)
Cactus Computational Toolkit beta release
Some of the new entries in the bibliography

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

Date: Fri, 31 Jul 1999 11:59:61 +0500
From: Craig Douglas
Subject: Important Date

August 15   Early registration for the 6th European Multigrid Conference:
260 Euros by check or bank transfer
1. By bank transfer to ASLK BANK, account nr 001-1950612-18 of
Universiteit Gent, m entioning EMG99/P8730 and participant
name (the code P8730 is extremely important to make sure that
the payment arrives at its correct destination).  The
international bank code (swift code) is CGAKBEBB
2. By cheque addressed at UNIVERSITEIT GENT, Attn.  Prof.  E.
DICK, Sint-Pietersnieuwstraat 41, 9000 GENT, BELGIUM.
After August 15, 300 Euros

See http://allserv.rug.ac.be/~edick/emg/register.html for online
registration for the conference.

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

Date: Wed, 14 Jul 1999 12:04:16 +0200 (METDST)
From: Christian Wrobel
Subject: AMG Tutorial on MGNet

I have a suggestion for the AMG Tutorial in
http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Tutorials/amgtut_files.
There are so many files, that getting them with "mget *" fails with "file list
to long".  It would be a great help if the whole directory would be tar'ed and
gzipp'ed; then a single get is sufficient.

Christian Wrobel

fuer Kontinua und Stroemungen (GKKS)

Universitaet Stuttgart
ICA 3 (Institut fuer Computer-Anwendungen)
Allmandring 5b (Verfuegungsgebaeude)
D-70569 Stuttgart
Tel.: 0711 / 685 - 8240
Fax : 0711 / 685 - 8325
e-mail: christian@ica3.uni-stuttgart.de
WWW:    http://www.ica3.uni-stuttgart.de/~christia

Editor's Note: I had assumed that everyone would use a web browser to look
-------------  at the tutorial.  I have placed a single gzipped tar file in
http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Tutorials/amgtut.tgz
See http://www.mgnet.org/mgnet-ccmm99.html or
http://www.mgnet.org/mgnet-tuts.html

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

Date: Thu, 15 Jul 1999 12:32:01 +0100 (BST)
From: Mike.Warby@brunel.ac.uk
Subject: Research Studentship at Brunel University

Research Studentship
BICOM, Institute of Computational Mathematics, Brunel University

Applications are invited for a three-year CASE research studentship
at BICOM as part of the EPSRC funded project

Computational Modelling of Thermoforming and In-Mould Decoration Processes

In these processes thin polymeric sheets, on which patterns are printed, are
deformed into specific shapes.  The research will involve the modelling and
numerical simulation of the deformation of the sheets.  Of particular interest
in the modelling is the prediction of the thickness distribution of the
deformed structures and the prediction of the distortion of the patterns
printed on the sheets.

The project will be undertaken in close collaboration with two British
manufacturing companies.

Applicants should hold, or expect to obtain, a good first degree or Masters
degree in a subject with a high mathematical content.  The successful
applicant will work in areas of computational solid mechanics associated with
the above process.  Previous knowledge of the areas is not essential as a
programme of reading and instruction will be available.

Interested persons should contact as soon as possible

Professor J. R. Whiteman or Dr. M. K. Warby,
BICOM, Dept. of Mathematics and Statistics,
Brunel University, Uxbridge, Middlesex UB8 3PH, UK
TEL:   ++44 1895 203270               FAX:    ++44 1895 203303
e-mails:  john.whiteman@brunel.ac.uk  or  Mike.Warby@brunel.ac.uk

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

Date:  Thu, 3 Jun 1999 23:07:20 +0800
From:  "qpguo"
Subject: Two Papers (Guo Qingping et al)

Parallel Multi Grid Algorithm with Virtual Boundary Forecast Domain
Decomposition Method for Solving Non-linear Heat Transfer Equation

Guo Qingping
Wuhan Transportation University
Wuhan 430063, P. R. China

Yakup Paker
Queen Mary & West field College
University of London
E1 4NS U.K.

Zhang Shesheng
Wuhan Transportation University
Wuhan 430063, P. R. China

Dennis Parkinson
Queen Mary & West field College
University of London
E1 4NS U.K.

Wei Jialin
Wuhan Transportation University
Wuhan 430063, P. R. China

Abstract

This paper proposes a virtual boundary condition forecast method in parallel
multi-grid algorithm design with domain decomposition for solving non-linear
transient problem.  Numerical results of non-linear transient heat transfer
problem by the algorithm in a PVM network computing environment show that the
algorithm has high parallel efficiency.

Key words:  Multi-Grid, Domain Decomposition, Virtual Boundary, Boundary
Condition Forecast

Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or access it at
-------------  http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Papers/gpguo1.rtf

* * * * *

Virtual Boundary Condition Forecast Algorithm In Multigrid Domain
Decomposition Parallel Computing

Guo Qingping
Wuhan Transportation University
Wuhan 430063, P. R. China

Yakup Paker
Queen Mary & West field College
University of London
E1 4NS U.K.

Zhang Shesheng
Wuhan Transportation University
Wuhan 430063, P. R. China

Dennis Parkinson
Queen Mary & West field College
University of London
E1 4NS U.K.

Wei Jialin
Wuhan Transportation University
Wuhan 430063, P. R. China

Abstract

We propose a virtual boundary condition forecast algorithm for multi grid
parallel computing, and derive a forecast function formula in this paper.
Numerical results of one and two-dimension boundary condition problems
obtained with the algorithm in a PVM network computing environment show that
the algorithm has high parallel efficiency.

Key words:  Multi-Grid, Domain Decomposition, Virtual Boundary Forecast

Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or access it at
-------------  http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Papers/gpguo2.doc

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

Date: Thu, 15 Jul 1999 06:59:61 +0500
From: Craig Douglas
Subject: Paper by Achi Brandt and Dorit Ron

Renormalization Multigrid (RMG):
Statistically Optimal Renormalization Group Flow
and Coarse-to-Fine Monte Carlo Acceleration

Achi Brandt and Dorit Ron
Department of Applied Mathematics and Computer Science,
Weizmann Institute of Science, Rehovot 76100, Israel

Abstract

New renormalization-group algorithms are developed with adaptive
representations of the renormalized action which automatically express only
significant interactions.  As the amount of statistics grows, more
interactions enter, thereby systematically reducing the truncation error.
This allows statistically optimal calculation of thermodynamic limits, in the
sense that it achieves accuracy e in just O(1/(e*e)) random number
generations.  There are practically no finite-size effects and the
renormalization transformation can be repeated arbitrarily many times.
Consequently, the desired fixed point is obtained and the correlation-length
critical exponent $\nu$ is extracted.In addition, we introduce a new
multiscale coarse-to-fine acceleration method, based on a multigrid-like
approach.  This general (non-cluster) algorithm generates independent
equilibrium configurations without slow down.  A particularly simple version
of it can be used at criticality.  The methods are of great generality; here
they are demonstrated on the 2D Ising model.

Key words.  Ising model, Renormalization Multigrid, P+ probabilities,
neighborhoods, criticalization, coarse-to-fine Monte Carlo acceleration,
Compatible Monte Carlo, Post Relaxation.

Editor's Note: See http://www.mgnet.org/mgnet-papers.html or access it at
-------------  http://www.mgnet.org/mgnet/papers/Brandt/rmg299.ps.gz

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

Date:  Fri, 06 Aug 1999 15:32:13 -0500
From:  Suely Oliveira
Subject: Two Papers (Suely Oliveira et al)

Title: On the convergence rate of a Preconditioned Subspace Eigensolver
Author: S. Oliveira (oliveira@cs.uiowa.edu).

In this paper we present a proof of convergence for a preconditioned subspace
method which shows the dependency of the convergence rate on the
preconditioner used.  This convergence rate depends only on the condition of
the pre-conditioned system $$\kappa _{2}(MA)$$ and the relative separation
of the first two eigenvalues $$1-\lambda _{1}/\lambda _{2}$$.  This means
that, for example, multigrid preconditioners can be used to find eigenvalues
of elliptic PDE's at a grid-independent rate.

Note: this paper is to appear in Computing.

Editor's Note: See http://www.mgnet.org/mgnet-papers.html or access it at
-------------  http://www.mgnet.org/mgnet/papers/Oliveira/conv.ps.gz

* * * * *

TITLE: A Graph Based Davidson Algorithm for the Graph Partitioning Problem"
Authors: M. Holzrichter and S. Oliveira.

The problem of partitioning a graph such that the number of edges incident to
vertices in different partitions is minimized, arises in many contexts.  Some
examples include its recursive application for minimizing fill-in in matrix
factorizations and load-balancing for parallel algorithms.  Spectral graph
partitioning algorithms partition a graph using the eigenvector associated
with the second smallest eigenvalue (Fiedler value) of a matrix called the
{\em graph Laplacian}.  The focus of this paper is the use graph theory to
compute this eigenvector more quickly.

Specifically we design a multigrid preconditioner coupled with the Davidson
algorithm which works well for finding the Fiedler vector.  This multigrid
preconditioner uses ideas of graph coarsening, such as heavy edge matching, in
its development.  We anticipate that similar ideas can be used when developing
Multigrid Algorithms for other unstructured problems.

Editor's Note: See http://www.mgnet.org/mgnet-papers.html or access it at
-------------  http://www.mgnet.org/mgnet/papers/Oliveira/graph.ps.gz

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

Date: Sun, 8 Aug 1999 20:42:10 -0500 (CDT)
From: Ed Seidel
Subject: Cactus Computational Toolkit beta release

We are pleased to announce the public beta release of the Cactus Computational
Toolkit 4.0!  In advance of the Cactus 4.0 workshop, sponsored jointly by NCSA
and AEI (Albert-Einstein-Institut), theToolkit, complete with documentation
and tutorials, is now publicly accessible at http://www.cactuscode.org.

In a nutshell, the Toolkit provides a modular, portable, and manageable
environment for collaboratively developing high-performance multidimensional
numerical simulations.  It allows one, with only a working knowledge of
Fortran or C, to plug application specific computational modules into the
framework, allowing one to make use of the following features:

Powerful Application Programming Interface
User modules (thorns) plug-into compact core (flesh)
Configurable interfaces, schedules and parameters
Accessible MPI-based parallelism for finite difference grids
and clusters
Several parallel I/O layers
Fixed and Adaptive mesh refinement under  development
Elliptic solvers
Metacomputing, distributed computing and visualization tools
Collaborative Development
Enables sharing code base
TestSuite checking technology
Exhaustive Numerical Relativity and Astrophysical Applications
Black Hole coalescence
Neutron star collisions
Other cataclysms...

We encourage people to check it out and give feedback about the code or the
documentation as we prepare to release the final version.  We also encourage
you to attend the workshop, scheduled for Sept.  27-Oct.  1, 1999, at NCSA in
Champaign, IL.  Please see the first workshop announcement at
http://www.ncsa.uiuc.edu/SCD/Training/CactusAnnounce.html for further details.
A second announcement with a more detailed agenda will be made by the end of
August.  We remind potential attendees to email us to register at
workshop99@cactuscode.org.

If you do not wish to receive further emails on Cactus, please email us and we
will remove your name from our mailing lists.  On the other hand, please pass
this announcement on to others who may have interest!

Thanks,
Ed Seidel

Ed Seidel
Max-Planck-Institut fuer Gravitationsphysik
and
University of Illinois

Phone:  (217) 244-1976
Fax:    (217) 244-2909
Mail:
NCSA
U of Illinois
605 E. Springfield Ave
Champaign, IL 61820 USA

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

Date: Tue, 9 Aug 1999 14:42:12 +0500
From: Craig Douglas
Subject: Some of the new entries in the bibliography

The latest version is dated August 10, 1999, has 3341 entries, and is 169
pages long.

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

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

REFERENCES

[1] R. E. Bank and S. Gutsch, The generalized hierarchical ba-
sis two-level method for the convection-diffusion equation on
a regular grid, in Multigrid Methods V, vol. 3 of Lecture
Notes in Computational Science and Engineering,  Berlin,
1998, Springer, pp. 1-20.
[2] A. Brandt and C. H. Venner, Multilevel evaluation of in-
tegral transforms on adaptive grids, in Multigrid Methods
V, vol. 3 of Lecture Notes in Computational Science and
Engineering, Berlin, 1998, Springer, pp. 21-44.
[3] H.-J.  Bungartz  and  Th.  Dornseifer,  Sparse  grids:  re-
cent developments for elliptic partial differential equations,
in Multigrid Methods V, vol. 3 of Lecture Notes in Com-
putational Science and Engineering, Berlin, 1998, Springer,
pp. 45-70.
[4] M. Czajkowski, Solution of an initial control problem for the
shallow water equations by a multi-grid method, in 5th Euro-
pean Multigrid Conference Special Topics and Applications,
University of Stuttgart, Stuttgart, 1998, pp. 5-17.
[5] J. E. Dendy and H. Tchelepi, Multigrid applied to implicit
well problems, in 5th European Multigrid Conference Special
Topics and Applications, University of Stuttgart, Stuttgart,
1998, pp. 18-34.
[6] V.  V.  Denissenko,  The  mutligrid  method  for  symmetrized
boundary value problems of diffusion in moving medium, in
5th European Multigrid Conference Special Topics and Ap-
plications, University of Stuttgart, Stuttgart, 1998, pp. 35-
46.
[7] P. Deuflhard and M. Weiser, Global inexact Newton mul-
tilevel  FEM  for  nonlinear  elliptic  equations,  in  Multigrid
Methods V, vol. 3 of Lecture Notes in Computational Sci-
ence and Engineering, Berlin, 1998, Springer, pp. 71-89.
[8] C. C. Douglas, S. Malhotra, and M. H. Schultz, Paral-
lel multigrid with ADI-like smoothers in two dimernsions, in
5th European Multigrid Conference Special Topics and Ap-
plications, University of Stuttgart, Stuttgart, 1998, pp. 47-
57.
[9] R.  Enander  and  E.  Sterner,  Analysis of internal bound-
ary conditions and communication strategies for multigrid
multiblock methods, in 5th European Multigrid Conference
Special  Topics  and  Applications,  University  of  Stuttgart,
Stuttgart, 1998, pp. 58-73.
[10]  L. V. Gilyova and V. V. Shaidurov, A cascadic mutigrid
algorithm in finite element method for an indefinte-sign el-
liptic problem, in 5th European Multigrid Conference Special
Topics and Applications, University of Stuttgart, Stuttgart,
1998, pp. 74-89.
[11]  Th. Gjesdal, Accuracy and convergence of defect correction in
an incompressible multigrid solver basewd onpressure correc-
tion smoothers, in Multigrid Methods V, vol. 3 of Lecture
Notes in Computational Science and Engineering,  Berlin,
1998, Springer, pp. 90-104.
[12]  W.  Hackbusch  and  G.  Wittum,  5th  European  Multigrid
Conference Special Topics and Applications, University of
Stuttgart, Stuttgart, 1998.
[13]  ______, Multigrid Methods V, vol. 3 of Lecture Notes in Compu-
tational Science and Engineering, Springer, Berlin, 1998.
[14]  M. G. Hackenberg, W. Joppich, and S. Mijalkovic, A
paralle multigrid environment for coupled problems on time-
dependent structures, in 5th European Multigrid Conference
Special  Topics  and  Applications,  University  of  Stuttgart,
Stuttgart, 1998, pp. 90-100.
[15]  W. Heinrichs, Operator splitting for the unsteady Stokes equa-
tions, in 5th European Multigrid Conference Special Topics
and Applications, University of Stuttgart, Stuttgart, 1998,
pp. 101-112.
[16]  P. W. Hemker, B. Koren, and J. Noordmans, 3D multi-
grid on partially ordered sets of grids, in Multigrid Methods
V, vol. 3 of Lecture Notes in Computational Science and
Engineering, Berlin, 1998, Springer, pp. 105-124.
[17]  M. Holzrichter and S. Oliveira, A graph based Davidson
algorithm for the graph partitioning problem, Int. J. Found.
Comp. Sci., 10 (1999), pp. 225-247.
[18]  JSch"oberl,  Robust  multigrid  preconditioning  for  parameter-
dependent problems I: the Stokes case, in Multigrid Methods
V, vol. 3 of Lecture Notes in Computational Science and
Engineering, Berlin, 1998, Springer, pp. 260-2275.
[19]  M. Jung, Parallel multi-level solvers for elliptic boundary value
problems in three-dimensional domains, in Multigrid Meth-
ods V, vol. 3 of Lecture Notes in Computational Science and
Engineering, Berlin, 1998, Springer, pp. 125-139.
[20]  B. N. Khoromskij and G. Wiitum, Robust interface reduc-
tion for highly anisotropic elliptic equations,  in Multigrid
Methods V, vol. 3 of Lecture Notes in Computational Sci-
ence and Engineering, Berlin, 1998, Springer, pp. 140-156.
[21]  F. Kickinger, Algebraic multigrid for discrete elliptic second-
order problems, in Multigrid Methods V, vol. 3 of Lecture
Notes in Computational Science and Engineering,  Berlin,
1998, Springer, pp. 157-172.
[22]  R. Kornhuber, On robust multigrid methods for non-smooth
variational  problems,  in  Multigrid  Methods  V,  vol.  3  of
Lecture Notes in Computational Science and Engineering,
Berlin, 1998, Springer, pp. 173-188.
[23]  A. Krechel and K. St"uben, Operator dependent interpola-
tion in algebraic multigrid, in Multigrid Methods V, vol. 3
of Lecture Notes in Computational Science and Engineering,
Berlin, 1998, Springer, pp. 189-211.
[24]  C.  W.  Oosterlee,   F.  J.  Gaspar,   T.  Washio,   and
R. Wienands, Fast multigrid solvers for higher order up-
wind  discretizations  of  convection-dominated  problems,  in
Multigrid Methods V, vol. 3 of Lecture Notes in Compu-
tational  Science  and  Engineering,  Berlin,  1998,  Springer,
pp. 212-224.
[25]  J. Piquet and X. Vasseur, Comparisions between precondi-
tioned BICGSTAB and a multigrid method for the resolution
of the pressure equation in a Navier-Stokes solver, in Multi-
grid Methods V, vol. 3 of Lecture Notes in Computational
Science and Engineering, Berlin, 1998, Springer, pp. 225-
242.
[26]  A. Quarteroni and A. Valli, Domain Decomposition Meth-
ods  for  Partial  Differential  Equations,  Oxford  University
Press, Oxford, 1999.
[27]  A. Reusken, Approximate cyclic reduction preconditioning, in
Multigrid Methods V, vol. 3 of Lecture Notes in Compu-
tational  Science  and  Engineering,  Berlin,  1998,  Springer,
pp. 243-259.
[28]  A.         Schuller,           C.         W.         Ooster-
lee, H. Ritzdorf, H. Schwichtenberg, B. Steckel,
and J. Wu, Parallelization and adapative grids for indus-
trial areadynamic multigrid codes, in 5th European Multi-
grid Conference Special Topics and Applications, University
of Stuttgart, Stuttgart, 1998, pp. 113-124.
[29]  V. Shultz and G. Wittum, Multigrid optimization methods
for stationary problems I: the Stokes-type case, in Multigrid
Methods V, vol. 3 of Lecture Notes in Computational Sci-
ence and Engineering, Berlin, 1998, Springer, pp. 276-288.
[30]  J. Steelent, E. Dick, and S. Pattijn, Analysis of multigrid
efficiency for viscous low mach mumber flows, in Multigrid
Methods V, vol. 3 of Lecture Notes in Computational Sci-
ence and Engineering, Berlin, 1998, Springer, pp. 289-305.
[31]  R. Stevenson, Piecewise linear (pre-)wavelets on non-uniform
meshes,  in Multigrid Methods V, vol. 3 of Lecture Notes
in  Computational  Science  and  Engineering,  Berlin,  1998,
Springer, pp. 306-319.
[32]  Ch. Wagner and G. wittum, Filtering decompositions with
respect  to  adaptive  test  vectors,  in Multigrid Methods V,
vol. 3 of Lecture Notes in Computational Science and Engi-
neering, Berlin, 1998, Springer, pp. 320-334.
[33]  T. Washio and K. Oosterlee, Krylov subspave accelration
for nonlinear mutigrid schemes, in 5th European Multigrid
Conference Special Topics and Applications, University of
Stuttgart, Stuttgart, 1998, pp. 125-137.

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

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