Send mail to:    mgnet@cs.yale.edu             for the digests or bakeoff
                  mgnet-requests@cs.yale.edu    for comments or help
 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

Graduiertenkolleg fuer Modellierung und Diskretisierungsmethoden
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
        Advanced Computational Toolkit
                Accessible MPI-based parallelism for finite difference grids
                Access to a variety of supercomputing architectures 
                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

Summer address:
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
**************************