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:    casper.cs.yale.edu (128.36.12.1)

World Wide Web:  http://na.cs.yale.edu/mgnet/www/mgnet.html or
                 http://www.cerfacs.fr/~douglas/mgnet.html

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

Volume 6, Number 3 (approximately March 31, 1996)

Today's topics:

     Paper by Bakhvalov and Knyazev
     Fifth European Multigrid Conference (EMG 96)
     Copper Mountain Conference on Iterative Methods Preprints
     Some BibTeX Entries

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

Date: Mon, 4 Mar 1996 14:29:13 -0700
From: aknyazev@tiger.cudenver.edu (Andrew Knyazev)
Subject: Paper by Bakhvalov and Knyazev

                Preconditioned Iterative Methods in a Subspace
               for Linear Algebraic Equations with Large Jumps
                             in the Coefficients

                             Nikolai S. Bakhvalov
                      Institute of Numerical Mathematics
                         Russian Academy of Sciences
                                Moscow, Russia

                              Andrew V. Knyazev
                          Department of Mathematics
                      University of Colorado at Denver 
                               P.O. Box 173364
                                Campus Box 170
                            Denver, CO 80217-3364

                                   Abstract

We consider a family of symmetric matrices $A_\omega=A_0+\omega B$, with a
nonnegative definite matrix $A_0$, a positive definite matrix $B$, and a
nonnegative constant $\omega\le 1$.  Small $\omega$ leads to a poor
conditioned matrix $A_\omega$ with jumps in the coefficients.  For solving
linear algebraic equations with the matrix $A_\omega$, we use standard
preconditioned iterative methods with the matrix $B$ as a preconditioner.  We
show that a proper choice of the initial guess makes possible keeping all
residuals in the subspace IM($A_0$).  Using this property we estimate,
uniformly in $\omega$, the convergence of the methods.

Algebraic equation of this type arise naturally as finite element
discretizations of boundary value problems for PDE with large jumps of
coefficients.  For such problems the rate of convergence does not decrease
when the mesh gets finer and/or $\omega$ tends to zero; each iteration has
only a modest cost.  The case $\omega=0$ corresponds to the fictitious
component/capacitance matrix methods.

    Editor's Note: in mgnet/papers/Bakhvalov-Knyazev/jumps.ps.gz and
    -------------                                .../jumps.abs

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

Date: Thu, 28 Mar 1996 11:02:29 +0100
From: Sekretariat des ICA3 
Subject: Fifth European Multigrid Conference (EMG 96)

University of Stuttgart
Institut fuer Computeranwendungen III
Pfaffenwaldring 27
D-70569 Stuttgart
Tel.: ++49-711-685 7091
Fax:  ++49-711-685 7000

Would you please include the following conference in your
"Information about future conferences":

Fifth European Multigrid Conference (EMG 96)
October 1 - 4, 1996, University of Stuttgart, Germany

Further information and registration at URL: 
http://www.ica.uni-stuttgart.de/formular/ica3formular.html

Thank you in advance.

Gunter Faust

    Editor's Note: Here is what I found in the web page, which is now
    -------------  archived in conferences/emg96.txt

University of Stuttgart, Institut fur Computeranwendungen (ICA)

EMG '96

Fifth European Multigrid Conference

Oct. 1-4, 1996 Stuttgart

The Institut fur Computeranwendungen (ICA) of Stuttgart University, in
cooperation with the GAMM Committee on Scientific Computing, SFB 359 and 404
and the research network WiR Ba-Wu, is organising the European Multigrid
Conference '96. Earlier European Multigrid Conferences were held in Cologne
in 1981 and 1985, in Bonn in 1990 and in Amsterdam in 1993. The conference
provides a forum for the presentation and discussion of recent research in
the general area of multigrid methods. Participation will be worldwide.

Chairmen:       Wolfgang Hackbusch, Kiel
                Gabriel Wittum, Stuttgart

Organisation:   Gunter Faust, Prudence Lawday
                ICA, Universitat Stuttgart, 70569 Stuttgart
                Phone: ++49-711-685-7090
                Fax:   ++49-711-685-7000
                email: emg96@ica.uni-stuttgart.de
                Date:  October 1st - 4th, 1996

Location:       Institut fur Computeranwendungen,
                Pfaffenwaldring 27, 70569 Stuttgart
                Germany

Topics:         Multigrid Methods:
                robustness, adaptivity, wavelets, parallel
                methods and software, applications in
                computational fluid dynamics, porous media
                flow, optimisation, computational mechanics
                and statistical physics.

Invited speakers (tentative):
                R. Bank (La Jolla), W. Dahmen (Aachen),  P.
                Deuflhard (Berlin), M. Griebel (Munich),
                P.W. Hemker (Amsterdam), R. Kornhuber (Berlin),
                U. Langer (Linz), G. Mack (Hamburg),
                J. Mandel (Boulder), D. Mavriplis (Ames),
                A. Reusken (Eindhoven), K. Stuben (Bonn)

Abstracts:      Please send an abstract of your proposed lecture
                by  June 1st, 1996. The collection of abstracts
                will be available at the conference. Notice of
                acceptance will be given by July 15th, 1996.

                The conference language is English.

Proceedings:    Invited lectures and a number of selected
                presentations will appear as full papers in
                the conferece proceedings to be publish-ed
                by Birkhauser. Participants may order the
                volume at a reduced price of 100,- DM on
                the registration form.

                Further presentations will be published as
                full papers by ICA.

Registration:   Please mail the enclosed form or register via
                http://www.ica.uni-stuttgart.de. Registration
                is valid only after full payment of the
                conference fee.

Conference fee: DM 400,- payable by Aug. 1st 1996 or DM 500,-
                after this date.
                The fee includes admission to all sessions,
                lunches and coffee breaks, the reception,
                the conference dinner and the collection of
                abstracts.

Payments:       All payments, net of all charges, are to be
                made in Deutschmarks by bank transfer to:
                Universitat Stuttgart, Baden-Wurtt.-Bank
                Stuttgart, bank code 600 200 30, account no.
                105 4611 700, specifying your name, "EMG96"
                and "Titel 11186, BA 4715".

Stuttgart:      Stuttgart is an attractive modern city situated
                in a thriving region between the Black Forest
                and the Schwabische Alb. It is a town of
                fascinating contrasts: on the one hand, an
                industrial metropolis with world-famous firms
                and, on the other hand, a city of parks and open
                spaces - there are even vineyards  extending
                right into the centre. The conference will take
                place at ICA on the university campus in
                Vaihingen, just a short ride from the inner city.

Accommodation:  Hotel rooms can be booked through:
                Stuttgart-Marketing, Postfach 104436,
                                     70173 Stuttgart,
                Tel.: 0711/2228-233 or -246;
                Fax:  0711/2228-251 (please mention EMG '96).

Getting here:   The conference venue is within easy reach of
                both the airport (10 minutes by either taxi
                or metro) and the main railway station
                (15 minutes by either taxi or metro). More
                detailed information will be sent to all
                participants after registration.

Social events:  A conference reception will be held on the
                evening of  Wednesday, 2nd October. On the a
                fternoon of Thursday, 3rd October, there will
                be an excursion followed in the evening by the
                conference dinner. A programme for accompanying
                persons will be organised if there is sufficient
                interest (please see registration form).

                                  * * * * *

University of Stuttgart, Institut fur Computeranwendungen (ICA)

Registration

EMG '96

Fifth European Multigrid Conference

Oct. 1-4, 1996 Stuttgart

Institut fur Computeranwendungen III
Universitat Stuttgart
EMG '96
Pfaffenwaldring 27

70569 Stuttgart
Germany

Please, accept my registration for EMG 96:

Name:        ______________________________________________________________

Affiliation: ______________________________________________________________

Address:     ______________________________________________________________

             ______________________________________________________________

Country:     ______________________________________________________________

E-mail:      ______________________________________________________________

Fax:         ______________________________________________________________

Phone:       ______________________________________________________________

     I would like to receive a copy of the
     proceedings volume at a reduced price of DM 100,-  YES

     I am interested in the programme for accompanying persons  YES

     I have transferred the following sum to the ICA bank account:
           DM 400,- registration fee until Aug. 1st     _________
           DM 500,- registration fee after Aug. 1st     _________
           DM 100,- for the proceedings volume          _________

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

Date: Sun, 31 Mar 1996 14:26:19 -0500 (EST)
From: Craig Douglas 
Subject: Copper Mountain Conference on Iterative Methods Preprints

In the directory, mgnet/Conferences/CMCIM96, are a number of abstracts and
preprints from the forthcoming (next week) conference.  This will be set up
similarly to the multigrid conferences held on odd years.  Particiapants can
download files to the machine casper.cs.yale.edu.  Please put files in the
directory mgnet/incoming/cmcim96/YourLastName.  I will move the file(s) once I
see them.

Here is what is in the directory so far:

Program.gz

J. M. Banoczi and C. T. Kelley
A Multilevel Method for Conductive-Radiative Heat Transfer
banoczi-kelley.abs
banoczi-kelley.ps.gz

A. Basermann, B. Reichel, and Schelthoff
Parallel Preconditioning Techniques for Sparse CG Solvers
basermann-reichel-schelthoff.abs.ps.gz

M. Benzi and M. Tuma
Approximate Inverse Preconditioning of Iterative Methods for Nonsymmetric
Linear Systems
benzi-tuma.abs
benzi-tuma.ps.gz

S. W. Bova and G. F. Carey
Iterative Solution of the Semiconductor Device Equations
bova-carey.ps.gz

H.-J. Bungartz
A unidirectional approach for d-dimensional finite element methods of higher
order on sparse grids
bungartz.abs
bungartz.ps.gz

Z. Cai, T. A. Manteuffel, S. F. McCormick, and S. V. Parter
First Order System Least Squares for the Pure Traction Problem in Planar
Linear Elasticity
cai-manteuffel-mccormick-parter.abs
cai-manteuffel-mccormick-parter.ps.gz

H. Choi and D. B. Szyld
Threshold Partitioning of Sparse Matrices and Applications to Markov Chains
choi-szyld.abs
choi-szyld.ps.gz

M. Clemens and T. Weiland
Iterative Methods for the Solution of Very Large Complex Symmetric Linear
Systems of Equations in Electrodynamics
clemens-weiland.ps.gz

X. Feng
A Mixed Finite Element Domain Decomposition Method for Nearly Elastic Wave
Equations in the Frequency Domain
feng.abs
feng.ps.gz

P. A. Gray
Iteration Schemes for Parallelizing Models of Superconductivity
gray.abs
gray.ps.gz

G. Horton
On the Multi-Level Solution Algorithm for Markov Chains
horton.abs
horton.ps.gz

C. T. Kelley, C. T. Miller, and M. D. Tocci
Method of Lines Solution of Richards' Equation
kelley-miller-tocci.abs
kelley-miller-tocci.ps.gz

P. Kolm, P. Arbenz, and W. Gander
Generalized Subspace Correction Methods
kolm-arbenz-gander.abs
kolm-arbenz-gander.ps.gz

C.-Y. G. Lai
Multilevel Solvers of First-Order System Least-Squares for Stokes Equations
lai.abs
lai.ps.gz

A. A. Lorber, G. F. Carey, S. W. Bova, C. H. Harle
Accelerated Solution of Non-Linear Navier-Stokes Problems using Chebyshev
Iteration Polynomial Based Runge-Kutta Recursions
lorber-carey-bova-harle.abs
lorber-carey-bova-harle.ps.gz

V. Menkov
Solving Block Linear Systems with Low-Rank Off-Diagonal Blocks Is Easily
Parallelizable
menkov.abs
menkov.ps.gz

C. W. Oosterlee and T. Washio
An Evaluation of Parallel Multigrid as Solver and Preconditioner for
Singular Perturbation Problems
oosterlee-washio.abs.ps.gz
oosterlee-washio.ps.gz

Y. Shapira
Parallelizable Approximate Solvers for Recursions Arising in Preconditioning
shapira.abs.ps.gz
shapira.ps.gz

M. Sosonkina, R. A. Kapania, H. F. Walker, and L. T. Watson
A New Adaptive GMRES Algorithm for Achieving High Accuracy
sosonkina-kapania-walker-watson.abs
sosonkina-kapania-walker-watson.ps.gz

S. V. Veronese and H. G. Othmer
Scalable Implicit Methods for Reaction-Diffusion Equations in Two and Three
Space Dimensions
veronese-othmer.ps.gz

K. Wu, Y. Saad, A. Strathopoulos
Preconditioned Krylov Subspace Methods for Eigenvalue Problems
wu-saad-strathopoulos.ps.gz

D. Xie
New Parallel SOR Method by Domain Partitioning
xie.abs
xie.ps.gz

J. Zhang
Multigrid Solution of the Convection-Diffusion Equation with High-Reynolds
Number
zhang.abs
zhang.ps.gz

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

Date: Fri, 1 Mar 1996 20:53:28 -0700
From: jmandel@tiger.cudenver.edu (Jan Mandel)
Subject: Some BibTeX Entries

    Editor's Note: These will eventually be in the bibliography (as they appear
    -------------  in publications), but not necessarily with the same key!

@techreport{SGhosal_JMandel_RTezaur_1994tr,
  author =      "S. Ghosal and J. Mandel and R. Tezaur",
  title =       "Fast Neural Networks for Domain
                 Decomposition in Finite Element Analysis",
  institution = "Center for Computational Mathematics, University of
                 Colorado at Denver",
  address =     "Denver, CO",
  type =        "UCD/CCM Report",
  number =      "23",
  year =        "1994",
  note =        "Submitted to SISC"
  }

The solution of large finite element problems on distributed memory (even
shared virtual memory) computers calls for efficient partitioning of large and
unstructured 3-D meshes into submeshes such that computations can be
distributed across processors.  It is desired that resulting subdomains
(submeshes) are approximately of same size, and the total number of interface
nodes between adjacent subdomains is minimal.  Two fine-grain scalable
parallel algorithms are proposed employing neural network paradigms that can
efficiently perform mesh partitioning for subsequent domain decomposition
computations.  New implementations are developed such that both the techniques
have almost {\em linear complexity} with respect to the problem size for
serial execution.  These substructuring techniques compare favorably to the
well-known recursive spectral bisection (RSB) method and simulated
annealing-based partitioning algorithm.

@unpublished{JMandel_RTezaur_CFarhat_1995unp,
  author =      "J. Mandel and R. Tezaur and C. Farhat",
  title =       "Optimal {L}agrange Multiplier Based Domain Decomposition
                 Method for Plate Bending Problems",
  note =        "SIAM J. Sci. Stat. Comp., submitted",
  year =        "1995"
  }

We present a new Lagrange multiplier based domain decomposition method for
solving iteratively systems of equations arising from the finite element
discretization of plate bending problems.  The proposed method is essentially
an extension of the FETI substructuring algorithm to the biharmonic equation.
The main idea is to enforce the continuity of the transversal displacement
field at the subdomain crosspoints throughout the p reconditioned conjugate
gradient iterations.  The resulting method is proved to have a condition
number that does not grow with the number of subdomains, and grows at most
polylogarithmically with the number of elements per subdomain.  These optimal
properties hold for numerous plate bending elements that are used in practice
including the HCT, DKT, and a class of non-locking elements for the
Reissner-Mindlin plate models.  Computational experiments are reported and
shown to confirm the theoretical opti mal convergence properties of the new
domain decomposition method.  Computational efficiency is a lso demonstrated
with the numerical solution in 45 iterations and 105 seconds on a 64-processor
IBM SP2 of a plate bending problem with almost one million degrees of freedom.

@unpublished{JMandel_RTezaur_1994unp,
  author =      "J. Mandel and R. Tezaur",
  title =       "On the Convergence of a Substructuring Method
                 with {L}agrange multipliers",
  note =        "Numerische Mathematik, to appear"
  }

We analyze the convergence of a substructuring iterative method with Lagrange
multipliers, proposed recently by Farhat and Roux.  The method decomposes
finite element discretization of an elliptic boundary value problem into
Neumann problems on the subdomains plus a coarse problem for the subdomain
nullspace components.  For linear conforming elements and preconditioning by
the Dirichlet problems on the subdomains, we prove the asymptotic bound on the
condition number $C (1+\log (H/h))^\gamma$, $\gamma=2$ or $3$,where $h$ is the
characteristic element size and $H$ subdomain size.

@incollection{PVanek_RTezaur_MBrezina_JKrizkova_1995a,
  author =      "P. Van{\v e}k and R. Tezaur and M. Brezina
                 and J. K{\v r}{\'i}{\v z}kov{\' a}",
  title =       "Two--level method with coarse space size independent
                 convergence",
  booktitle =   "Domain Decomposition Methods in Sciences and Engineering",
  publisher =   "John Wiley \& Sons Ltd.",
  address =     "New York, N.Y.",
  editor =      "R. Glowinski and J. P{\'e}riaux and Z. Shi and O. Widlund",
  year =        "1995",
  note =        "to appear",
  }

We propose a nontraditional domain decomposition-type iterative method with
the rate of convergence uniform with respect to coarse-space size.  The method
avoids a concept of local subdomain solvers and therefore is significantly
less expensive than classical domain decomposition algorithms.

@unpublished{RTezaur_PVanek_MBrezina_1996unp,
  author =      "R. Tezaur and P. Van{\v e}k and M. Brezina",
  title =       "Two-level method for solids on unstructured meshes",
  note =        "SIAM J. Sci. Comp., submitted",
  year =        "1996"
  }

We propose an abstract two-level algorithm with convergence independent of the
coarse-space size.  The abstract algorithm is applied to problems of solids
discretized on unstructured meshes.  With no regularity assumptions we prove
uniform convergence with respect to coarse-space size, domain, essential
boundary conditions and jumps in Young modulus.  Numerical experiments confirm
the theory and show that the method works well even if some assumptions of the
theory are violated.

@article{SGhosal_PVanek_1995a,
  author =      "S. Ghosal, P. Van{\v e}k",
  title =       "A fast scalable algorithm for discontinuous optical flow
                estimation",
  journal =     "IEEE Trans. Pattern Anal. Mach. Intel.",
  volume =      "18",
  number =      "2",
  year =        "1996",
  pages =       "181-195",
  }

@article{PVanek_SGhosal_1995b,
  author =      "P. Van{\v e}k and S. Ghosal",
  title =       "A new technique for construction of image pyramids",
  journal =     "Asian Conference on Computer Vision",
  volume =      "1",
  year =        "1996",
  pages =       "479--483",
  }

@unpublished{PLeTallec_JMandel_MVidrascu_1995unp,
  author =      "P. {Le Tallec} and J. Mandel and M. Vidrascu",
  title =       "A {N}eumann-{N}eumann domain decomposition
                 algorithm for solving plate and shell problems",
  note =        "SIAM J. Numer. Anal., submitted",
  }

@inproceedings{PLeTallec_JMandel_MVidrascu_1994a,
  author =      "P. {Le Tallec} and J. Mandel and M. Vidrascu",
  title =       "Parallel domain decomposition algorithms for solving plate
                 and shell problems",
  booktitle =   "Advances in Parallel and Vector Processing for
                 Structural Mechanics",
  editors =     "B. H. V. Topping and M. Papadrakakis",
  publisher =   "CIVIL-COMP Ltd",
  address =     "Edinburgh",
  year =        "1994",
  note =        "Proceedings, Athens, 1994",
  }

@unpublished{PVanek_JMandel_MBrezina_1995unp,
  author =      "P. Van{\v e}k and J. Mandel and M. Brezina",
  title =       "Algebraic multigrid based on smoothed aggregation
                 for second and fourth order problems",
  note =        "Computing, to appear",
  }

@article{CFarhat_PSChen_JMandel_1995a,
  author =      "C. Farhat and P. S. Chen and J. Mandel",
  title =       "Scalable {L}agrange multiplier based domain
                 decomposition method for time-dependent problems",
  journal =     "Int. J. Numer. Meth. Engrg.",
  year =        "1995",
  note =        "To appear",
  }

@unpublished{JMandel_1994unp,
  author =      "J. Mandel",
  title =       "Iterative methods for p-version finite elements:
                 {P}reconditioning thin solids",
  institution = "Center for Computational Mathematics,
                 University of Colorado at Denver",
  address =     "Denver, CO",
  type =        "UCD/CCM Report",
  number =      "31",
  year =        "1994",
  note =        "J. Comput. Meth. Appl. Mech. Engrg., submitted",
  }

@unpublished{JMandel_MBrezina_1994unp,
  author =      "J. Mandel and M. Brezina",
  title =       "Balancing Domain Decomposition for Problems with
                 Large Jumps in Coefficients",
  note =        "Mathematics of Computation, to appear",
  }

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

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