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://www.cerfacs.fr/~douglas/mgnet.html or
http://phase.etl.go.jp/mgnet or
http://www.ccs.uky.edu/mgnet
Today's editor: Craig Douglas (douglas-craig@cs.yale.edu)
Volume 8, Number 2 (approximately February 28, 1998)
Today's topics:
Preprint from Y. Saad and J. Zhang
Graduate Research Assistantship at Clarkson University
Preliminary Program for 5th Copper Mountain Conference on Iterative Methods
Some of the new entries in the bibliography
Editor's Note:
-------------
-------------------------------------------------------
Date: Mon, 23 Feb 1998 17:34:24 -0600 (CST)
From: Jun Zhang
Subject: Preprint from Y. Saad and J. Zhang
We wish to announce of availability of the following preprint.
Diagonal Threshold Techniques in Robust Multi-Level ILU
Preconditioners for General Sparse Linear Systems
Yousef Saad and Jun Zhang
E-mail: saad@cs.umn.edu, jzhang@cs.umn.edu
URL: http://www.cs.umn.edu/~saad http://www.cs.umn.edu/~jzhang
ABSTRACT
This paper introduces techniques based on diagonal threshold tolerance when
developing multi-elimination and multi-level incomplete LU (ILUM)
factorization preconditioners for solving general sparse linear systems.
Existing heuristics solely based on the adjacency graph of the matrices have
been used to find independent sets and are not robust for matrices arising
from certain applications in which the matrices may have small or zero
diagonals. New heuristic strategies based on the adjacency graph and the
diagonal values of the matrices for finding independent sets are introduced.
Analytical bounds for the factorization and preconditioned errors are obtained
for the case of a two-level analysis. These bounds provide useful information
in designing robust ILUM preconditioners. Extensive numerical experiments are
conducted in order to compare robustness and efficiency of various heuristic
strategies.
Key Words: Incomplete LU factorization, reordering techniques, multi-level
preconditioner, Krylov subspace methods, multi-elimination ILU factorization.
PostScript file of the above preprint may be downloaded from either
authors' home page as listed above.
For those who do not have access to web facility, send an e-mail to
jzhang@cs.umn.edu for a PostScript file or a hard copy.
-------------------------------------------------------
Date: Fri, 27 Feb 98 17:11:56 EST
From: fulton@sun.mcs.clarkson.edu (Scott Fulton)
Subject: Graduate Research Assistantship at Clarkson University
Clarkson University anticipates an opening in Fall 1998 for a
Graduate Research Assistantship in Mathematics at the M.S. or
Ph.D. level. This student will join an active group working
on multigrid methods and their application to modeling hurricane
dynamics and motion. Several Teaching Assistantships will also
be available.
For information see our web page (http://www.clarkson.edu/~mcs/)
or contact Scott Fulton (fulton@clarkson.edu).
-------------------------------------------------------
Date: Sat, 28 Feb 1998 14:42:12 -0400
From: Craig Douglas
Subject: Preliminary Program for 5th Copper Mountain Conference on Iterative Methods
The abstracts can be found through
http://amath-www.colorado.edu/appm/faculty/copper
The virtual proceedings will be on MGNet later this month.
Sunday, March 29
7:00-9:00 PM Reception
Monday, March 30
Room A B
Session I
Topic Preconditioning Multilevel Methods
Chair Steve McCormick
8:00 K. Vuik I.Yavneh
8:25 M. Drexler D. Melson
8:50am R. Bridson C. Pflaum
9:15am W. Joubert M. Holst
9:40am Coffee Break
Session II
Topic Preconditioning Algebraic Multigrid
Chair Steve McCormick
10:10am S. Brenner V. Henson
10:35am T. Dayar J. Ruge
11:00am J. Zhang A. Cleary
11:25am M. Lambert R. Falgout
11:50am F. Wang M. Brezina
12:15pm Lunch
Session III
Topic Preconditioning Multigrid
Chair S. McCormick
4:30pm D. Szyld C. Greif
4:55pm S. Toledo S. Sokal
5:20pm A. Pothen J. Moulton
5:45pm V. Pan Y. Shapira
6:10pm Dinner
Tuesday, March 31
Room A B
Session I
Topic Eigenvalue Methods Parallel Methods
Chair Henk van der Vorst
8:00 R. Lehoucq J. Jones
8:25 Open C. Tong
8:50am W. Gansterer S. Oliveira
9:15am K. Wu D. Quinlan
9:40am Coffee Break
Session II
Topic Eigenvalue Methods Parallel Methods
Chair Henk van der Vorst
10:10am Z. Bai R. Clay
10:35am A. Edelman N. Jovanovic
11:00am Y. Saad A. Krommer
11:25am D. Sorrenson J. Malard
11:50am H. Van der Vorst P. Rucho
12:15pm Lunch
Session III
Topic Eigenvalue Methods Applications
Chair Henk van der Vorst
4:30pm A. Knyazev V. Howle
4:55pm W. Demeo M. Huhtanen
5:20pm E. Gallopoulos P. Saylor
5:45pm M. Tocci A. Slavova
6:10pm Dinner
Wednesday, April 1
Room A B
Session I
Topic First Order Systems Least-Squares Nonlinear Solvers
Chair Tom Manteuffel Homer Walker
8:00 S. McCormick C. Kelley
8:25 M. Berndt D. Knoll
8:50am G. Starke R. Freund
9:15am D. Chan H. Walker
9:40am Coffee Break
Session II
Topic First-Order Systems Least-Squares Nonlinear Solvers
Chair Tom Manteuffel Homer Walker
10:10am P. Bochev C. Woodward
10:35am T. Sun E. Bowman
11:00am Z. Cai F. Meier
11:25am J. Pasciak J. Meulman
11:50am B. Lee M. Seaid
12:15pm Lunch
Session III
Topic Misc. Krylov Subspace Methods
Chair
4:30pm J. Hennart L. Bergamaschi
4:55pm A. Stathopoulos J. Cullum
5:20pm D. Daoud A. Wathen
5:45pm A. Williams M Yeung
6:10pm Dinner
Thursday, April 2
Room A B
Session I
Topic Applications Multigrid Methods
Chair
8:00 M. Tretter R. Bermejo
8:25 S. Vandewalle R. Menikoff
8:50am J. Marin J. Gopalakrishnan
9:15am W. Spotz V. Sarin
9:40am Coffee Break
Session II
Topic ASCI Applications Discretization Methods
Chair
10:10am C. Aro C. Romine
10:35am W. Rider V. Druskin
11:00am J. Shadid H. Bungartz
11:25am F. Graziani D. Smolarski
11:50am A. Robertson M. Shashkov
12:15pm Lunch
Session III
Topic Applications Student Papers
Chair
4:30pm T. Tamarchenko M. Adams
4:55pm H. Jang W. Ching
5:20pm G. Newman D. Loghlin
5:45pm J. Rahola C. Lin
6:10pm Break
Banquet 6:30 to 9:30 pm
Friday, April 3
Room A B
Session I
Topic Krylov Subspace Methods Preconditioning
Chair
8:00 O. Ernst A. Ramage
8:25 R. Morgan M. Trummer
8:50am E. Ng C. Oosterlee
9:15am E. de Sturler V. Delafosse
9:40am Coffee Break
Session II
Topic Domain Decomposition/MG Preconditioning
Chair
10:10am D. Day P. Farrell
10:35am B. Lally H. Elman
11:00am G. Mateescu Y. Shih
11:25am R. Renaut J. Simoens
11:50am M. Sosonkina G. Wade
12:15pm Lunch
Session III
Topic Krylov Subspace Methods Preconditioning
Chair
4:30pm D. Kincaid A. Grama
4:55pm W. Luk Open
5:20pm S. Goossens N. Nguyen
5:45pm M. Buecker A. Nishida
6:10pm Close of Meeting
-------------------------------------------------------
Date: Sat, 28 Feb 1998 14:42:12 -0400
From: Craig Douglas
Subject: Some of the new entries in the bibliography
Here is a large set of publications. They will be reformatted and the ones
that have appeared will be entered into the MGNet bibliography over the next
few weeks.
As usual, please send additions and corrections.
REFERENCES
[1] I. Babu~ska, F. Ihlenburg, E.T. Paik, and S.A. Sauter, A
generalized finite element method for solving the Helmholtz
equation in two dimensions with minimal pollution, Comp.
Meth. Appl. Mech. Eng., 128 (1995), pp. 325-359.
[2] I. Babu~ska, F. Ihlenburg, and S.A. Sauter, Reliabil-
ity of finite element methods for the numerical computa-
tion of waves, Advances in Engineering Software, 28 (1997),
pp. 417-424.
[3] I. Babu~ska and S.A. Sauter, Is the pollution effect of the
FEM avoidable for the Helmholtz equation considering high
wave numbers., SIAM, J. Numer. Anal., 34 (1997), pp. 2392
- 2423.
[4] Randy Bank and Sabine Gutsch, The generalized hierarchi-
cal basis two-level method for the convection-diffusion equa-
tion on a regular grid, in Proceedings of the EMG 1996,
Stuttgart, 1996. to appear.
[5] ______, Hierarchical basis for the convection-diffusion equation
on unstructured meshes, in Ninth International Symposium
on Domain Decomposition Methods for Partial Differential
Equations, D.Keyes P.Bjorstadt, M.Espedal, ed., J. Wiley
and Sons, New York, 1996.
[6] ______, An algebraic approach to the hbmg method for unstruc-
tured grids, in ZAMM, 1997. to appear.
[7] Jens Burmeister and Wolfgang Hackbusch, On a time
and space multi-grid method including remarks on filtering
techniques, in Flow Simulation with High-Performance Com-
puters, E. Hirschel, ed., no. 52-2 in NNFM, Vieweg, 1996,
pp. 5-19.
[8] Jens Burmeister and Graham Horton, Time-parallel
multigrid solution of the Navier-Stokes equations, in Multi-
grid Methods III, Wolfgang Hackbusch and Ulrich Trot-
tenberg, eds., vol. 98 of International Series of Numerical
Mathematics, Basel, 1991, Birkh"auser Verlag, pp. 155-166.
Proceedings of the 3rd European Conference on Multigrid
Methods, Bo nn, October 1-4, 1990.
[9] Jens Burmeister and Rainer Paul, Time-adaptive solution
of discrete parabolic problems with time-parallel multigrid
methods, in Computational Fluid Dynamics on Parallel Sys-
tems, Siegfried Wagner, ed., vol. 50 of NNFM, Vieweg, 1995,
pp. 49-58.
[10] W. Busch, R. Esser, and W. Hackbusch, Extrapolation
applied to the method of characteristics for a first order sys-
tem of two partial differential equations, Numer. Math., 24
(1975), pp. 331-353.
[11] S. Dittrich and W. Hackbusch, A method of characteristics
solving the initial-boundary value problem of a hyperbolic dif-
ferential equation of second order, Numer. Math., 34 (1980),
pp. 217-234.
[12] M. Dryja and W. Hackbusch, On the nonlinear domain
decomposition method, BIT, 37 (1997), pp. 296-311.
[13] Birgit Faermann, Lokale a-posteriori Fehlersch"atzer bei der
Diskretisierung von Randintegralgleichungen, PhD thesis,
Universit"at Kiel, 1993.
[14] ______, Lokale a-posteriori-Fehlersch"atzer
bei der Diskretisierung von Randintegralgleichungen, ZAMM
(Z. angw. Math. Mech), 75 (1995), pp. S 681-682.
[15] ______, Local a-posteriori error estimators for the discretization
of boundary integral equations, in Boundary Elements: Im-
plementation and Analysis of Advanced Algorithms, Pro-
ceedings of the 12th Kieler GAMM-Seminar, vol. 54 of Notes
on Numerical Fluid Mechanics, Braunschweig, 1996, Vieweg,
pp. 68-81.
[16] ______, Adaptive Galerkin boundary element methods, in ZAMM
(Z. angw. Math. Mech), 1997.
[17] B. Faermann, Efficient and reliable a-posteriori error esti-
mates for boundary element methods, in Analysis, Numer-
ics and Applications of Differential and Integral Equations,
C. Constanda, M. Bach, A.M. Saendig, P. Werner, and G.C.
Hsiao, eds., London, 1997, Addison Wesley Longman. (to
appear).
[18] I.G. Graham, W. Hackbusch, and S. Sauter, The hybrid
galerkin boundary element method, in Proceedings of the first
UK conference on Boundary Integral Methods, L. Elliot,
D.B. Ingham, and D. Lesnic, eds., Leeds University Press,
1997, pp. 98-107. submitted to Numer. Math.
[19] W. Hackbusch, Extrapolation applied to certain discretization
methods solving the initial value problem for hyperbolic dif-
ferential equations, Numer. Math., 28 (1977), pp. 121-142.
[20] ______, Extrapolation to the limit for numerical solutions of
hyperbolic differential equations, Numer. Math, 28 (1977),
pp. 455-474.
[21] ______, A numerical method for solving parabolic equations with
opposite orientations, Computing, 20 (1978), pp. 229-240.
[22] ______, On a method of characteristics for solving a hyperbolic
equation of second order, Computing, 20 (1978), pp. 47-60.
[23] ______, A note on the penalty correction method, Zeitschrift f"ur
Analysis und ihre Anwendungen, 2 (1982), pp. 59-69.
[24] ______, Schnelle L"oser f"ur partielle Differentialgleichungen, PM
Mathematik, 27 (1985), pp. 478-501.
[25] ______, Theorie und Numerik elliptischer Differentialgleichungen,
Teubner, 1986.
[26] ______, Multi-grid methods and applications, Springer, 1988. Chi-
nese translation.
[27] ______, Integralgleichungen. Theorie und Numerik, Teubner,
1989.
[28] ______, Iterative L"osung grosser schwachbesetzter Gleichungssys-
teme, Teubner, 1991.
[29] ______, Comparison of different multi-grid variants for nonlinear
equations, ZAMM, 72 (1992), pp. 148-151.
[30] ______, Elliptic Differential Equations, Springer, 1992. English
translation.
[31] ______, A parallel conjugate gradient method, J. of Numerical
Linear Algebra with Applications, 1 (1992), pp. 133-147.
[32] ______, Iterative solution of large sparse systems, Springer, 1994.
English translation.
[33] ______, Integral Equations. Theory and Aplication, vol. 120 of
ISNM, Birkh"auser, 1995. English translation.
[34] ______, A note on Reusken's lemma, Computing, 55 (1995),
pp. 181-189.
[35] ______, Numerische Mathematik und ihre Wechselwirkung
mit der gegenw"artigen Rechnerentwicklung, in Berlin-
Brandenburgische Akademie der Wissenschaften, Bericht
und Abhandlungen, vol. 4, Berlin, 1997, Akademie-Verlag,
pp. 55-67.
[36] Wolfgang Hackbusch, On the feedback vertex set problem
for a planar graph, Computing, 58 (1997), pp. 129-155.
[37] W. Hackbusch and G. Hofmann, Results of the eigenvalue
problem for the plate equation, Z. Angew. Math. Phys., 31
(1980), pp. 730-739.
[38] W. Hackbusch, C. Lage, and S.A. Sauter, On the efficient
realization of sparse matrix techniques for integral equations
with focus on panel clustering, cubature and software design
aspects, in Boundary Element Topics, W.L. Wendland, ed.,
Springer, 1997, pp. 51-76.
[39] Wolfgang Hackbusch and Rainer Paul, Kopplung von
Finite-Element- und Randelementmethoden f"ur die nu-
merische Simulation von piezokeramischen Strukturen, in
Mathematik: Schl"usseltechnologie f"ur die Zukunft; Ver-
bundprojekte zwischen Universit"at und Industrie, Karl-
Heinz Hoffmann, Willi J"ager, Thomas Lohmann, and Her-
mann Schunk, eds., Berlin Heidelberg New York, 1997,
Springer-Verlag, pp. 151-160.
[40] Wolfgang Hackbusch and Thomas Probst, Downwind
gauss-seidel smoothing for convection dominated problems,
in ZAMM, 1997. to appear.
[41] W. Hackbusch and T. Probst, Downwind Gauss-Seidel
smoothing for convection dominated problems, Numerical
Linear Algebra with Applications, 4 (1997), pp. 85-102.
[42] W. Hackbusch and S.A. Sauter, On the efficient use of
the Galerkin method to solve Fredholm integral equations,
Applications of Mathematics, 38 (1993), pp. 301-322.
[43] ______, On numerical cubatures of nearly singular surface inte-
grals arising in BEM Collocation, Computing, 52 (1994),
pp. 139-159.
[44] ______, A new finite element approach for problems containing
small geometric details, in Proceedings of the ENUMATH
'95-Konferenz, Paris, 1995.
[45] ______, Adaptive Composite Finite Elements for the solution
of PDEs containing non-uniformly distributed micro-scales,
Matematicheskoe modelirovanie, 8 (1996), pp. 31-43.
[46] ______, Composite Finite Elements for problems containing small
geometric details. Part II: Implementation and numerical
results, Computing and Visualization in Science, 1 (1997),
pp. 15-25.
[47] ______, Composite Finite Elements for the approximation of
PDEs on domains with complicated micro-structures, Nu-
mer. Math., 75 (1997), pp. 447-472.
[48] Wolfgang Hackbusch and Jens Uwe Wappler, Remarks
on error estimation in the presence of iteration errors, sub-
mitted to Computing, (1996).
[49] K. Hayami and S.A. Sauter, A formulation of the panel clus-
tering method for the three-dimensional elastostatic problem,
in Proceedings of the JASCOME 13th symposium on BEM,
Tokyo, 1996, pp. 125-130.
[50] ______, A formulation of the Panel-Clustering Method for three-
dimensional elastostatics, in Proceedings of the Annual
Meeting of the Japanese Society for Industrial and Applied
Mathematics (JSIAM), Tokyo, 1996, pp. 218-219.
[51] ______, Application of the panel clustering method for the three-
dimensional elastostatic problem, in Boundary Elements
XIX, Proceedings of the 19th International Conference on
the Boundary Element Method, C.A. Brebbia M. Marchetti
and M.H.Aliabadi, eds., Rome, 1997, Computational Me-
chanics Publications, pp. 625-634.
[52] ______, Cost estimation of the panel clustering method applied
to 3-d elastostatcs, in Proceedings of the EUROBEM `98
conference, Paris, 1998.
[53] Peter Kosmol and Ivor Nissen, A minimal residual class
of algorithms for linear systems, Computing, 51 (1993),
pp. 335-343.
[54] S. Lorenz, C. Solterbeck, W. Schattke, J. Burmeister,
and W. Hackbusch, Electron scattering states at solid sur-
faces calculated with realistic potentials, Phys. Rev. B, 55
(1997), p. R13432.
[55] J"org-Peter Mayer, Zur L"osung von geod"atischen
Randwertproblemen durch einen hypersingul"aren Potential-
Ansatz, PhD thesis, Universit"at Kiel, 1997.
[56] Rainer Paul, Eigenwertprobleme bei der Simulation piezok-
eramischer Strukturen, PhD thesis, Universit"at Kiel, 1997.
[57] S.A. Sauter, Ein Mehrgitterverfahren zur Berechnung
der Eigenschwingungen von abgeschlossenen Wasserbecken,
Master's thesis, Universit"at Heidelberg, 1989.
[58] ______, The ILU method for finite element discretizations, J.
Comp. Appl. Math., 36 (1991), pp. 91-106.
[59] ______, "Uber die effiziente Verwendung des Galerkinverfahrens
zur L"osung Fredholmscher Integralgleichungen, PhD thesis,
Universit"at Kiel, 1992.
[60] ______, On the stability of the ILU method for singular per-
turbed finite element problems, in Incomplete Decomposi-
tions (ILU), Theory, Technique and Applications, Proceed-
ings of the 8th Kieler GAMM-Seminar, W. Hackbusch and
G. Wittum, eds., Vieweg, Notes on Numerical Fluid Me-
chanics, 1993, pp. 139-149.
[61] ______, On the efficient implementation of Galerkin-BEM,
ZAMM, 74 (1994), pp. T 516-518.
[62] ______, On the stability of the incomplete Cholesky decomposition
for a singular perturbed problem, where the coefficient matrix
is not an M-matrix, J. Numer. Lin. Alg. Appl., 2 (1995),
pp. 17-28.
[63] ______, Cubature techniques for 3-d Galerkin BEM, in Boundary
Elements: Implementation and Analysis of Advanced Algo-
rithms, W. Hackbusch and G. Wittum, eds., Vieweg, Notes
on Numerical Fluid Mechanics, 1996, pp. 29-44.
[64] ______, Composite finite elements for problems with complicated
boundary. part iii: Essential boundary conditions, submit-
ted to: Computing and Visualization in Sciences, (1997).
Institutsbericht, Nr. 97-16.
[65] ______, Vergr"oberung von Finite-Elemente-R"aumen, Habilita-
tionsschrift, Universit"at Kiel, 1997.
[66] ______, The Panel Clustering Method in 3-d BEM, in Wave Prop-
agation in Complex Media, G. Papanicolau, ed., no. 96 in
IMA-Volumes in Mathematics and Applications, Springer,
1998, pp. 199-224.
[67] S.A. Sauter and A. Krapp, On the effect of numerical in-
tegration in the Galerkin boundary element method, Numer.
Math., 74 (1996), pp. 337-360.
[68] S.A. Sauter and C. Lage, On the efficient computation of
singular and nearly singular surface integrals arising in 3D-
Galerkin BEM, ZAMM, 76 (1996), pp. 273-275.
[69] ______, Transformation of hypersingular integrals and black-box
cubature, Math. Comp, (1997). submitted.
[70] S.A. Sauter and C. Schwab, Realization of hp-Galerkin
BEM in 3-d, in Boundary Elements: Implementation
and Analysis of Advanced Algorithms, W. Hackbusch and
G. Wittum, eds., Vieweg, Notes on Numerical Fluid Me-
chanics, 1996, pp. 194-206.
[71] ______, Quadrature for hp-Galerkin BEM in 3-d, Numer. Math.,
(to appear).
[72] S.A. Sauter and G. Wittum, On the computation of the
eigenmodes of Lake Constance by means of a multi-grid
method, in GMD-Studien of the 3rd European Conference
of Multigrid Methods, W. Hackbusch and U. Trottenberg,
eds., Bonn, 1991.
[73] ______, A multigrid method for the computation of eigenmodes
of closed water basins, Impact of Computing in Science and
Engineering, 4 (1992), pp. 124-152.
------------------------------
End of MGNet Digest
**************************