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
**************************