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