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

World Wide Web:  file:// or

Today's editor:  Craig Douglas (

Volume 4, Number 10 (approximately October 31, 1994)

Today's topics:

     European MGNet Mirror and Re-organization of the Archives
     Meisdorf Meeting Abstracts
     Call for papers (Computing special issue)
     Time Parallel Paper
     Paper on Nonnested Space Multilevel Methods
     Bib Items for MGNet from Tony Chan


Date: Mon, 31 Oct 1994 09:39:49 GMT
Subject: European MGNet Mirror and Re-organization of the Archives

CERFACS now has a mirror of MGNet.  It is currently available through Mosaic
with the URL name of

It will be available later this week by anonymous ftp (
Hopefully, people in Europe will be able to access this easier than the
repository at Yale.
I took this opportunity to re-organize where some things are stored on MGNet.
For example, I moved all of the software packages from the top level directory
to a new subdirectory called Codes.

The new organization is as follows:

Codes               All software packages are stored in subdirectories in
Conferences         Information, abstracts, or papers from old conferences
                    are stored in here.  For example, CopperMtn93 has the
                    proceedings from the April, 1993 Copper Mountain meeting
                    in it.
How2Submit.mgnet    A short summary of commands that can be used to put
                    something into the archives using ftp.
INDEX.mgnet         A summary of what is in the archives (and where).
README              Simple information to get started.
Whois               Who receives the digests by e-mail (to the best of my
bib                 The 2,000+ BibTeX database.
conferences         Announcements of future meetings.
digests             The old digests (all of them).
incoming            Where new things get put before being stored in the
                    right place (only at Yale, not the mirror sites).
papers              Where lots of preprints are stored.

There are some other files and directories, but they are only for operating


Date: Mon, 17 Oct 1994 18:36:11 +0200 (MESZ)
From: Friedhelm Schieweck 
Subject: Meisdorf Meeting Abstracts

Concerning the abstracts I have to say that only a part of them (27) is
available on the computer (as LaTeX), the other part exists only as a paper.
Please tell me if you are intersted in this LaTeX-part of the abstracts
which I could send you by ftp and if yes please tell me the directory on
the server.

Best regards,

    Editor's Note: Now in mgnet/Conferences/Meisdorf94.  The incomplete set
    -------------  is in COLLECTION.dvi.  Individual ones are in the
                   Abstracts subdirectory.


Date: Wed, 26 Oct 1994 13:25:09 +0100
From: Annemarie Joehnk 
Subject: Call for papers (Computing special issue)

  Dear Mr Douglas,
  please post this call for papers at the appropriate place.
  Sincerely yours
  W. Hackbusch
  Call for Papers  
  The journal COMPUTING is planning a special issue devoted to the subject of 
                               adaptive techniques. 
  Special topics may, e.g., be 
   - adaption techniques 
   - grid refinement (isotropic, anisotropic, etc) 
   - grid coarsening 
   - error estimators 
   - implementational details 
   - adaptions of discretisations 
   - treatment of different time-scales. 
  The papers should be sent to the address below (or to any other editor of 
  COMPUTING) until 
                          December 15, 1994.  
  The "instructions to authors" are in every issue of COMPUTING (2 copies 
  with summary, AMS subject classification, keywords, if possible German
  translation of the title and summary). The paper is to be sent to 
    Prof Dr Wolfgang Hackbusch 
    Editor of Computing 
    Institut f"ur Informatik und Praktische Mathematik 
    D-24098 Kiel 
  Fax.++431-880 4054 e-mail: 
  Please forward this information to interested colleagues. 
Date: Sun, 2 Oct 94 14:09:57 MET
From: Graham Horton 
Subject: Time Parallel Paper

Here is a "time-parallel" method that will appear in sisc next year.


                      G. HORTON and S. VANDEWALLE


We consider the solution of parabolic partial differential equations.
In standard time- stepping techniques multigrid can be used as an
iterative solver for the elliptic equations arising at each discrete
time-step.  By contrast, the method presented in this paper treats the
whole of the space-time problem simultaneously.  Thus the multigrid
operations of smoothing and coarse grid correction are defined on all of
the space-time variables of a given grid-level.  The method is
characterized by a coarsening strategy with prolongation and restriction
operators which depend at each grid level on the degree of anisotropy of
the discretization stencil.  Numerical results for the one- and
two-dimensional heat equation are presented and are shown to agree
closely with predictions from Fourier mode analysis.

    Editor's Note: in mgnet/papers/Horton-Vandewalle/
Date: Thu, 20 Oct 1994 17:06:40 GMT
Subject: Paper on Nonnested Space Multilevel Methods

A Unified Multigrid Theory for Non-Nested Grids and/or Quadrature

C. C. Douglas, J. Douglas, Jr., and D. E. Fyfe

In this paper, we extend some results from an earlier paper (SIAM J. Numer.
Anal., 30 (1993), pp. 136-158) of the first two authors.  We provide a
unified theory for multilevel and multigrid methods when the usual assumptions
are not present.  For example, we do not assume that the solution spaces or
the grids are nested.  Further, we do not assume that there is an algebraic
relationship between the linear algebra problems on different levels.

What we provide is a computationally useful theory for adaptively changing
levels.  Theory is provided for multilevel correction schemes, nested
iteration schemes, and one way (i.e., coarse to fine grid with no correction
iterations) schemes.  We include examples showing the applicability of this
theory:  finite element examples using quadrature in the matrix assembly and
finite volume examples with non-nested grids.  Our theory applies directly to
finite difference, wavelet, and collocation based multilevel examples as well.

(To appear in the East-West Journal of Numerical Mathematics, 1995.)

    Editor's Note: in mgnet/papers/Douglas-Douglas-Fyfe/nonnested.dvi.


Date: Wed, 2 Nov 1994 14:03:27 +0800 (EAT)
From: Prof. Tony Chan 
Subject: Bib Items for MGNet from Tony Chan

  I promised you some bibitems for MGNet. Here they are.
Sorry that not all of them are in bibtex format.

    Editor's Note: These will appear in mgnet/bib/mgnet.bib sometime in early
    -------------  November.  Thanks.

\item {\it Domain Decomposition Algorithms,}
Tony F Chan and  Tarek Mathew,
Acta Numerica, Cambridge Univ. Press, 1994, pp. 61-143.

\item {\it Templates for the solution of linear systems: Building
blocks for iterative methods},
with R. Barrett et al, SIAM, Philadelphia, 1994 (book).

\item {\it Scientific Computation}, Tony F Chan and Zhong-ci Shi
(Eds), Proceedings of International Conference on Scientific Computation,
Hangzhou, China, 20-23 August 1991, Series on Applied Mathematics, Vol. 1,
World Scientific Press, 1992.

\item {\it The interface probing technique in domain decomposition},
Tony F Chan and T. Mathew,
SIAM J. Matrix Anal. Appl., 13, 1992, 212-238.

\item {\it On the relationship between overlapping and nonoverlapping
domain decomposition methods},
Tony F Chan and D. Goovaerts,
SIAM J. Matrix Anal. Appl., 13, 1992, 663-670.

\item {\it Multilevel filtering elliptic preconditioner},
C.C.J. Kuo, Tony F Chan and C. Tong,
SIAM J. Sci. Stat. Comp., 11, 1990, 403-429.

\item {\it Hierarchical Algorithms and Architectures for Parallel
Scientific Computing}, Tony F Chan, invited paper
in Proceedings of the ACM International Conference on Supercomputing,
pp. 318-329, Amsterdam, The Netherlands, June 1990.

\item {\it Geometry-Independent Convergence Results for Domain Decomposition
with Thomas Hou and P.L. Lions,
%UCLA CAM Report 89-11, May 1989.
SIAM J. Numer. Anal., Vol. 28, No.2, pp. 378-391, April 1991.

\item {\it Parallel Elliptic Preconditioners: Fourier Analysis and Performance
on the Connection Machine},
Tony F Chan, Jay Kuo and Charles Tong,
Computer Physics Communicatins 53 (1989) 237-252.

\item {\it Fourier Analysis of Preconditioned Iterative Methods},
Tony F Chan and Howard Elman,
SIAM Review, Vol. 31, No. 1, pp. 20-49, March 1989.

\item {\it The alternating-block-factorization procedure for
systems of partial differential equations},
R.E. Bank, T.F. Chan, W.M. Coughran and R.K. Smith,
BIT, 29, 1989, 938-954.

%\item {\it Domain Decomposition Methods}, 
%Proceedings of the Second International
%Symposium on Domain Decomposition Methods, UCLA, January 1988.
%T.F. Chan, R. Glowinski, J. Periaux, O. Widlund (Eds.), 
%SIAM, Philadelphia, 1989.

\item {\it FLO52 on hypercubes: performance of a parallel code
for the Euler equations on hypercubes},
E. Barszcz, T.F. Chan, D.C. Jespersen, R.S. Tuminaro,
J. High Speed Comp., 1, 1989, 481-503.

\item {\it Analysis of preconditioners for domain decomposition}
Tony F Chan,
SIAM J. Numer. Anal., 24, 1987, 382-390.

\item {\it Multigrid Algorithms on the Hypercube Multiprocessor},
Tony F Chan and Youcef Saad,
IEEE Trans. Computers, Vol. C-35, No. 11, Nov. 1986, pp.969-977.

\item {\it PLTMGC: A multigrid continuation program package for
solving parametrized nonlinear elliptic systems},
SIAM J. Sci. Stat. Comp., 7, 1986, 540-559.

\item {\it Analysis of projection methods for solving linear systems
with multiple right-hand-sides}, with W.L. Wan,
UCLA CAM Report 94-26, August 1994.

\item {\it Multigrid and domain decomposition methods for unstructured
with B. Smith and J. Zou.
In Proc. of the 3rd Int'l Conf. on Advances in Numerical Methods
and Applications, Sofia, Bulgaria, August 1994, World Scientific,
Singapore, pp. 53-62.

\item {\it Parallel complexity of domain decomposition methods
and optimal coarse grid size},
UCLA CAM Report 94-15, June 1994.

\item {\it The composite step family of nonsymmetric conjugate
gradient methods}, with Tedd Szeto,
UCLA CAM Report 94-11, April 1994.
In Proc. of PCG'94, Keio Univ., Yokahama, Japan.
T. Nodera (ed.), Keio Univ. Press, 1994.

\item {\it Overlapping Schwarz Methods on Unstructured Meshes
Using Non-Matching Coarse Grids,}
with Barry Smith and Jun Zou, UCLA CAM report 94-8, March 1994.

\item {\it A sign cut version of the recursive spectral
bisection graph partitioning algorithm},
with W.K. Szeto.
UCLA CAM Report 94-7, March 1994.
In Proc. SIAM Conf. Numer. Lin. Alg., Snowbird, Utah, June 1994.

\item {\it Domain decomposition and multigrid algorithms for
elliptic problems on unstructured meshes},
 with Barry Smith.
UCLA CAM Report 93-42, Dec. 93.
To appear in Elec. Trans. Numer. Anal.

\item {\it Additive Schwarz domain decomposition methods for
elliptic problems on unstructured meshes},
with Jun Zou.
UCLA CAM Report 93-40, Dec. 93.
To appear in Numer. Algorithms. 

\item {\it A composite step conjugate gradient squared algorithm
for solving nonsymmetric linear systems},
with Tedd Szeto,
UCLA CAM Report 93-27, July 1993.
Numer. Alg., vol. 7, no. 1, 1994, pp. 17-32.

\item {\it Optimal coarse grid size in domain decomposition},
with J.P. Shao,
UCLA CAM Report 93-24, July 1993.
To appear in J. Comp. Math.

\item {\it A composite step bi-conjugate gradient algorithm for
nonsymmetric linear systems},
with Randy Bank,
UCLA CAM Report 93-21, June 1993.
Numer. Alg., vol. 7, no. 1, 1994, pp. 1-16.

\item {\it On the optimality of the median cut spectral
bisection graph partitioning method},
UCLA CAM Report 93-14, June 1993.

\item {\it Performance modelling for high order finite difference
methods on the Connection Machine CM-2},
with Y.C. Chang.
UCLA CAM Report 93-04, March 1993.
To appear in J. Supercomputer and Applic.

\item {\it An analysis of the composite step bi-conjugate gradient
with Randy Bank,
Numer. Math., 66, 1993, 295-319.

\item {\it Domain decomposition preconditioners for convection
diffusion problems},
with Tarek Mathew.
UCLA CAM Report 92-43, Oct. 1992.
In Proc. of 6th Int'l Conf. on Domain Decomposition, 
A. Quarternoni et al (eds.), AMS, Providence, 1994.

\item {\it A framework for block ILU factorizations using
block-size reduction},
with P. Vassilevski.
UCLA CAM Report 92-29, June 1992.
To appear in Math. Comp.

\item {\it QMRCGSTAB: A quasi-minimal residual variant of the Bi-CGSTAB
algorithm for nonsymmetric systems},
with E. Gallopoulos, V. Simoncini, T. Szeto and C. Tong.
SIAM J. Sci. Comp., 15, 1993, 338-347.
%UCLA CAM Report 92-26, June 92.



        AUTHOR="Tony F. Chan and Tarek P. Mathew and Jian Ping Shao",
        TITLE="Efficient Variants of the Vertex Space 
               Domain Decomposition Algorithm",
        INSTITUTION="Department of Mathematics, UCLA  ",
        YEAR="1992  ",
        NOTE="To appear in SIAM J. Sci. Comp.",
        NUMBER=" CAM 92-07 "

       TITLE="Domain Decomposition Methods ",
       EDITOR="Tony Chan and Roland Glowinski and
                and Jacques P{\'e}riaux and
                Olof Widlund",
       NOTE="Proceedings of the {S}econd {I}nternational
            {S}ymposium on {D}omain {D}ecomposition
            {M}ethods , {L}os {A}ngeles, {C}alifornia
            , January 14 - 16, 1988.",

       TITLE="Domain Decomposition Methods ",
       EDITOR="Tony Chan and Roland Glowinski and
                and Jacques P{\'e}riaux and
                Olof Widlund",
       NOTE="Proceedings of the {T}hird {I}nternational
            {S}ymposium on {D}omain {D}ecomposition
            {M}ethods , {H}oston, {T}exas,

       TITLE="Domain Decomposition Methods ",
       EDITOR="Tony Chan and Roland Glowinski and
                and Jacques P{\'e}riaux and
                Olof Widlund",
       NOTE="Proceedings of the {F}ourth {I}nternational
            {S}ymposium on {D}omain {D}ecomposition
            {M}ethods , {M}oscow, {U}SSR,

       TITLE="Domain Decomposition Methods For Partial Differential
       EDITOR="David E. Keyes and Tony F. Chan and Gerard Meurant
               and Jeffrey S. Scroggs and Robert G. Voigt",
       NOTE="Proceedings of the {F}ifth {I}nternational
            {S}ymposium on {D}omain {D}ecomposition
            {M}ethods , {N}orfolk, USA,

author={T.F. Chan and L. de Pillis and H.A. Van der Vorst},
 title="A transpose-free squared Lanczos algorithm and application
    to solving nonsymmetric linear systems",
  number="CAM 91-17",
  institution="UCLA, Dept. of Math., Los Angeles, CA 90024-1555",

    author={R. Barrett and M. Berry and T.F. Chan and J. Demmel and
         J. Donato and J. Dongarra and V. Eijkhout and R. Pozo and
         C. Romine and H. van der Vorst},
    title={Templates for the solution of linear systems:
             building blocks for iterative methods},
    publisher={SIAM, Philadelphia},

     author={T.F. Chan and G. Meurant},
     title={Fourier analysis of block preconditioners},
     institution={Dept. of Math., UCLA, Los Angeles},
     number={CAM 90-04}, year={1990}}

     author={T.F. Chan and P. Vassilevski},
     title={A framework for block {ILU} factorizations using
          block size reduction},
     journal={Math. Comp.}, note={to appear}, year={1994}}

     author={T.F. Chan},
     title={Hierarchical algorithms and architectures for parallel
           scientific computing},
     booktitle={Proc. ACM Int'l Conf. Supercomputing, Amsterdam,
        The Netherlands},
     pages={318-329}, year={1990}}

      author={T.F. Chan and Jay C.C. Kuo and C.H. Tong},
      title={Parallel elliptic preconditioners: Fourier analysis
        and performance on the {C}onnection {M}achine},
      journal={Comp. Phys. Commun.}, pages={237-252},
      volume={53}, year={1989}}

      author={C.H. Tong},
      title={Parallel preconditioned conjugate gradient
          methods for elliptic partial differential equations},
      year={1990}, school={Dept. of Comp. Sci., 
        Univ. of Calif. at Los Angeles}}

      author={J.C.C. Kuo and T.F. Chan},
      title={Two-color Fourier analysis of iterative algorithms
           for elliptic problems with red/black ordering},
      journal={SIAM J. Sci. Stat. Comp.},
      year={1990}, pages={767-793}, volume={11}}

      author={C.H. Tong},
      title={The preconditioned conjugate gradient method
        on the {C}onnection {M}achine},
      booktitle={Scientific application of the Connection Machine},
      editor={H. Simon}, publisher={World Scientific},

      author={T.F. Chan and D. Goovaerts},
      title={A note on the efficiency of domain decomposed 
         incomplete factorizations},
      journal={SIAM J. Sci. Stat. Comp.},
      volume={11}, number={4}, pages={794-803}, year={1990}}

       author={T.F. Chan},
      title={Fourier analysis of relaxed incomplete factorization
      journal={SIAM J. Sci. Stat. Comp.},
      volume={12}, pages={668-680}, year={1991}}

      author={J.M. Donato},
      title={Iterative methods for scalar and coupled systems 
         of elliptic equations},
      school={Dept. of Math., Univ. Calif. at Los Angeles},

       author={T.F. Chan and D. Resasco},
       title={A survey of preconditioners for domain decomposition},
       institution={Dept. of Comp. Sci., Yale Univ.},
       number={DCS/RR-414}, year={1985}}

       author={T.F. Chan and T. Mathew},
       title={The interface probing technique in domain
       journal={SIAM J. Matrix Anal. Applic.},
       volume={13}, number={1}, year={1992}, pages={212-238}}


End of MGNet Digest