Send mail to: mgnet@cs.yale.edu for the digests mgnet-requests@cs.yale.edu for comments or help Anonymous ftp repository: www.mgnet.org (128.163.209.19) World Wide Web: http://www.mgnet.org or http://casper.cs.yale.edu/mgnet/www/mgnet.html or http://www.cerfacs.fr/~douglas/mgnet.html or http://www.nchc.gov.tw/RESEARCH/Math/mgnet/www/mgnet.html Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 11, Number 1 (approximately January 31, 2001) Today's topics: Important Date Postdoctoral position at the Weizmann Institute Pieter Wesseling Book(s) Update Dissertation on Cache Aware Multigrid for Unstructured Grids ENUMATH 2001 High Performance Scientific Computing (Conference Call) Some of the new entries in the bibliography ------------------------------------------------------- Date: Wed, 31 Jan 2001 10:15:12 -0500 (EST) From: Craig Douglas Subject: Important Date March 1 Hotel reservations for Copper Mountain Conference on Multigrid Methods. See http://amath.colorado.edu/appm/faculty/copper ------------------------------------------------------- Date: Thu, 28 Dec 2000 14:44:50 +0200 (IST) From: Carol Weintraub Subject: Postdoctoral position at the Weizmann Institute The Gauss Center for Scientific Computation at the Weizmann Institute of Science, Rehovot, Israel, is seeking a qualified candidate for a Post-Doctoral position, to participate in the Center's development of advanced multiscale computational methods. Possible directions include: 1. Multigrid methods, especially in fluid dynamics 2. Data assimilation in atmospheric simulations 3. Wave phenomena 4. Ab-initio quantum chemistry, density functional theory 5. Molecular dynamics 6. Optimal feedback control 7. Computational physics: multiscale Monte-Carlo, Dirac solvers, path integrals 8. Fast medical-imaging and radar reconstruction 9. Multiscale image processing 10. Clustering and multilevel graph algorithms Applicants should have completed their Ph.d. studies between June 1999 and the appointment start date. They should have a strong background and programming experience in scientific computing, preferably in one of the above areas and/or in multiscale computational methods. The post-doc appointment is for a period of one year and may be renewed for a second year. Applications and request for further information should be sent to the Gauss Center Secretary: Mrs. Carol Weintraub Dept. of Computer Science & Applied Mathematics The Weizmann Institute of Science Rehovot 76100, Israel Email: carol@wisdom.weizmann.ac.il Fax: +972-8-9342945 Phone: +972-8-9343545 The application should include a CV, a description of previous experience in scientific computing and the particular areas of interest, and names of two referees, who should separately send their letters of recommendation to the above address. More information on the research at the Gauss Center can be found at our web site: http://www.wisdom.weizmann.ac.il/~achi/gaussctr.html ------------------------------------------------------- Date: Sun, 28 Jan 2001 10:15:12 -0500 (EST) From: Craig Douglas Subject: Pieter Wesseling Book(s) Update Please reference the book through the web page http://www.mgnet.org/mgnet-books-wesseling.html until the project is finished. I changed the names of some of the files and received lots and lots of email letting me know that I broke bookmarks and hyperlinks all over the place. This is a testimonial to the popularity of the book. By the way, Pieter Wesseling's new book on CFD has a web page: http://www.springer.de/cgi-bin/search_book.pl?isbn=3-540-67853-0 and is shipping. ------------------------------------------------------- Date: Mon, 05 Feb 2001 12:45:43 -0800 From: Jonathan Hu Subject: Dissertation on Cache Aware Multigrid for Unstructured Grids Cache Based Multigrid on Unstructured Grids in Two and Three Dimensions Jonathan Hu University of Kentucky Department of Mathematics Lexington, KY 40506-0027, USA Dissertation for a Doctor of Philosophy September, 2000 Abstract A computer's central processing unit (CPU) can perform a mathematical operation much faster than data can be transferred from main memory to the CPU. This disparity in speed continues to grow each year. Thus, scientific codes do not attain speeds which could be possible if the CPU speed were the only factor influencing code performance. The typical hardware solution is to place several layers of small, fast cache between the CPU and main memory. Cache hardware by itself cannot guarantee good scientific code performance. Better algorithms (or restructured forms of standard ones) are necessary to ensure better utilization of the cache hierarchy. In geometric multigrid, the solve time is typically dominated by the smoothing and residual steps. Thus, a speedup in these steps should result in a similar speedup in the entire multigrid code. We consider Gauss-Seidel smoothing in the context of using geometric multigrid to solve a two or three dimensional second order elliptic partial differential equation on an unstructured grid. We present a variant of the Gauss-Seidel method which keeps data in cache memory much longer than a non-cache aware implementation. As a result, this method is faster than non-cache implementations. The cache aware variant returns bitwise the same answer as a standard Gauss-Seidel method on the same grid ordering. Thus, all convergence results that hold for multigrid with standard Gauss-Seidel hold for multigrid with cache aware Gauss-Seidel. The cache aware Gauss-Seidel method relies on information from the underlying problem discretization as well as load balancing ideas from parallel computing. The key step to the cache aware method is an inexpensive one time grid reordering. Upper bounds on the complexity of this reordering phase are derived for triangular, tetrahedral, quadrilateral, and hexahedral grids. A multigrid implementation that uses the grid reordering techniques and cache aware Gauss-Seidel method is described. Code profiling statistics show that the cache aware multigrid method make better use of large cache memory than standard multigrid methods. Numerical experiments demonstrate that the cache aware multigrid code is faster than non-cache aware codes. Editor's Note: See http://www.mgnet.org/mgnet-papers.html or ------------- http://www.mgnet.org/mgnet/papers/Hu/thesis.ps.gz ------------------------------------------------------- Date: Wed, 31 Jan 2000 23:15:12 +0500 From: Craig Douglas Subject: ENUMATH 2001 ENUMATH 2001 The European Conference on Numerical Mathematics and Advanced Applications Date: July 23-28, 2001 Location: Hotel Continental Terme Ischia Porto, ITALY Contact Information : enumath@ian.pv.cnr.it Web page: http://www.ian.pv.cnr.it/~enumath/welcome.html Abstract of contributed papers are required by March 17th, 2001. Proposal for minisymposia should be addressed directly to enumath@ian.pv.cnr.it possibly before March 17th, 2001. The authors will be informed via e-mail about acceptance as soon as possible and in any case not later than April 16th, 2001. Scientific Committee: O. Axelsson (Netherlands) C. Canuto (Italy), M. Griebel (Germany), R. Hoppe (Germany), G. Kobelkov (Russia), U. Langer (Austria), K. Morgan ( UK), A. Murli (Italy), P. Neittaanmaki (Finland), O. Pironneau (France), A. Quarteroni (Italy/Switzerland), C. Schwab (Switzerland), D. Talay (France), W. Wendland (Germany), Program Committee : F. Brezzi (Italy), M. Feistauer (Czech. Rep.), R. Glowinski (France/USA), R. Jeltsch (Switzerland), Yu. Kuznetsov (Russia/USA), J. Periaux (France), R. Rannacher (Germany). Local Organizing Committee: F. Brezzi, A. Buffa, S. Corsaro, A. Murli. ------------------------------------------------------- Date: Thu, 1 Feb 2001 09:14:42 -0500 (EST) From: Jun Zhang Subject: High Performance Scientific Computing (Conference Call) C A L L F O R P A P E R S Technical Session on High Performance Scientific Computation with Applications 2001 The above technical session is organized in "The 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'01)", June 25 - 28, 2001, Monte Carlo Resort, Las Vegas, Nevada, USA. This is the second one following the first one organized in 1999. Today's scientific and engineering problems demand computational power which is far beyond that can be provided by conventional computers. Scientific computations has been one of the most important components of high performance computation. It is the initial and continuous driving force behind the development of high performance computers. The goal of this session is to bring together researchers in various areas of high performance scientific computation and applications to exchange ideas and communicate new developments. The HPSCA01 session focuses on the high performance scientific computation techniques and applications. Anything that is related to this topic is welcome. Please e-mail Jun Zhang at jzhang@cs.uky.edu if you are interested in presenting a paper. A web page for this technical session has been created at http://www.cs.uky.edu/~jzhang/hpsca01.html where various deadlines and a tentative speaker list can also be found. The HPSCA01 technical session is co-organized by: Jun Zhang Jules Kouatchou Laboratory for High Performance Scientific Morgan State University Computing and Computer Simulation School of Engineering Department of Computer Science Baltimore, MD 21239 University of Kentucky and NASA Lexington, KY 40506-0046 E-mail: jzhang@cs.uky.edu kouatchou@gsfc.nasa.gov ------------------------------------------------------- Date: Wed, 31 Jan 2001 14:42:12 +0500 From: Craig Douglas Subject: Some of the new entries in the bibliography The latest version is dated February 3, 2001, has 3521 entries, and is 158 pages long. As usual, please send additions and corrections. Editor's Note: See http://www.mgnet.org/mgnet-bib.html ------------- REFERENCES [1] M. Benzi, W. Joubert, and G. Mateescu, Numerical ex- periments with parallel orderings for ILU preconditioners, Elect. Trans. Numer. Anal., 8 (1998), pp. 88-114. [2] M. Berndt, T. A. Manteuffel, and S. F. McCormick, Local error estimates and adaptive refinement for first-order system least squares (FOSLS), Elect. Trans. Numer. Anal., 6 (1997), pp. 35-43. [3] P. Bochev, Experiences with negative norm least-square meth- ods for the Navier-Stokes equations, Elect. Trans. Numer. Anal., 6 (1997), pp. 44-62. [4] A. Brandt, The Gauss Center research in multiscale scientific computation, Elect. Trans. Numer. Anal., 6 (1997), pp. 1-34. [5] ______, General highly accurate algebraic coarsening, Elect. Trans. Numer. Anal., 10 (2000), pp. 1-20. [6] A. Brandt and I. Livshits, Wave-Ray multigrid method for standing wave equations, Elect. Trans. Numer. Anal., 6 (1997), pp. 162-181. [7] R. Bru, V. Migallon, J. Penades, and D. B. Szyld, Par- allel, synchronous and asynchronous two-stage multisplitting methods, Elect. Trans. Numer. Anal., 3 (1995), pp. 24-38. [8] H.-J. Bungartz, A multigrid algorithm for higher order fi- nite elements on sparse grids, Elect. Trans. Numer. Anal., 6 (1997), pp. 63-77. [9] Z. Cai, T. A. Manteuffel, and S. F. McCormick, First- order system least squares for velocity-vorticity-pressure form of the Stokes equations, Elect. Trans. Numer. Anal., 3 (1995), pp. 150-159. [10] S. S. Capizzano and C. T. Possio, High-order finite differ- ence schemes and Toeplitz based preconditioners for elliptic problems, Elect. Trans. Numer. Anal., 11 (2000), pp. 55-84. [11] M. A. Casarin and O. B. Widlund, A preconditioner for the mortar finite element method, Elect. Trans. Numer. Anal., 4 (1996), pp. 75-88. [12] T. F. Chan and K. R. Jackson, The use of iterative linear equation solvers in codes for systems of stiff IVPs for ODEs, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 378-417. [13] T. F. Chan and B. F. Smith, Domain decomposition and multigrid algorithms for elliptic problems on unstructured meshes, Elect. Trans. Numer. Anal., 2 (1994), pp. 171-182. [14] K. Chen, Efficient iterative solution of linear systems from dis- cretizing singular integral equations, Elect. Trans. Numer. Anal., 2 (1994), pp. 76-91. [15] Z. Chen, The analysis of intergrid transfer operators and multigrid methods for nonconforming finite elements, Elect. Trans. Numer. Anal., 6 (1997), pp. 78-96. [16] J. E. Dendy, Semicoarsening multigrid for systems, Elect. Trans. Numer. Anal., 6 (1997), pp. 97-105. [17] B. Diskin, Multigrid algorithm with conditional coarsening for the non-aligned sonic flow, Elect. Trans. Numer. Anal., 6 (1997), pp. 106-119. [18] M. Dobrowolski, S. Graf, and C. Pflaum, On a posteriori error estimators in the finite element method on anisotropic meshes, Elect. Trans. Numer. Anal., 8 (1998), pp. 36-45. [19] C. C. Douglas, G. Haase, J. Hu, M. Kowarschik, U. R"ude, and C. Weiss, Portable memory hierarchy tech- niques for pde solvers, part i, SIAM News, 33 (2000), pp. 1, 8-9. [20] ______, Portable memory hierarchy techniques for pde solvers, part ii, SIAM News, 33 (2000), pp. 1, 10-11, 16. [21] C. C. Douglas, J. Hu, and M. Iskandarani, Preprocess- ing costs of cache based multigrid, in Proceeding of ENU- MATH99: Third European Conference on Numerical Meth- ods for Advanced Applications, Singapore, 2000, World Sci- entific, pp. 362-370. [22] C. C. Douglas, J. Hu, M. Iskandarani, M. Kowarschik, U. R"ude, and C. Weiss, Maximizing cache memory usage for multigrid algorithms, in Multiphase Flows and Transport in Porous Media: State of the Art, Springer, Berlin, 2000, pp. 124-137. [23] C. C. Douglas, J. Hu, M. Kowarschik, U. R"ude, and C. Weiss, Cache optimization for structured and unstruc- tured grid multigrid, Elect. Trans. Numer. Anal., 10 (2000), pp. 21-40. [24] J. Erhel, A parallel GMRES version for general sparse matri- ces, Elect. Trans. Numer. Anal., 3 (1995), pp. 160-176. [25] A. Frommer, H. Schwandt, and D. B. Szyld, Asyn- chronous weighted additive Schwarz methods, Elect. Trans. Numer. Anal., 5 (1997), pp. 48-62. [26] S. R. Fulton, A comparison of multilevel adaptive methods for hurricane track prediction, Elect. Trans. Numer. Anal., 6 (1997), pp. 120-132. [27] R. Fuster, V. Migallon, and J. Penades, Non-stationary parallel multisplitting AOR methods, Elect. Trans. Numer. Anal., 4 (1996), pp. 1-13. [28] G. Haase, A parallel AMG for overlapping and non- overlapping domain decomposition, Elect. Trans. Numer. Anal., 10 (2000), pp. 41-55. [29] J. Hu, Cache Based Multigrid on Unstructured Grids in Two and Three Dimensions, PhD thesis, University of Kentucky, Deparmtent of Mathematics, Lexington, KY, 2000. [30] C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, vol. 16 of Frontiers in Applied Mathematics, SIAM, Philadelphia, 1995a. [31] ______, Iterative Methods for Optimization, vol. 18 of Frontiers in Applied Mathematics, SIAM, Philadelphia, 1999a. [32] D. A. Knoll and W. J. Rider, A multigrid preconditioned Newton-Krylov method, SIAM J. Sci. Comput., 21 (1999), pp. 692-710. [33] J. Korsawe and G. Starke, Multilevel projection methods for nonlinear least-squares finite element computations, Elect. Trans. Numer. Anal., 10 (2000), pp. 56-73. [34] J. Kouatchou, Asymptotic stability of a 9-point multigrid al- gorithm for convection-diffusion equations, Elect. Trans. Nu- mer. Anal., 6 (1997), pp. 153-161. [35] W. J. Layton, A. J. Meir, and P. G. Schmidt, A two- level discretization method for the stationary MHD equa- tions, Elect. Trans. Numer. Anal., 6 (1997), pp. 198-210. [36] B. Lee and M. R. Trummer, Multigrid conformal mapping via the szeg"o kernel, Elect. Trans. Numer. Anal., 2 (1994), pp. 22-43. [37] I. M. Llorente and N. D. Melson, Behavior of plane relax- ation methods as multigrid smoothers, Elect. Trans. Numer. Anal., 10 (2000), pp. 92-114. [38] S. Malhotra, Topics in Multigrid Methods, PhD thesis, Yale University, Department of Computer Science, New Haven, CT, 1996. [39] T. A. Manteuffel, G. Starke, and R. S. Varga, Adaptive k-step iterative methods for nonsymmetric systems of linear equations, Elect. Trans. Numer. Anal., 3 (1995), pp. 50-65. [40] D. J. Mavriplis, Directional coarsening and smoothing for anisotropic Navier-Stokes problems, Elect. Trans. Numer. Anal., 6 (1997), pp. 182-197. [41] W. F. Mitchell, A parallel multigrid method using the full domain partition, Elect. Trans. Numer. Anal., 6 (1997), pp. 224-233. [42] M. K. Ng and Robert J. Plemmons, LMS-Newton adap- tive filtering using FFT-based conjugate gradient iterations, Elect. Trans. Numer. Anal., 4 (1996), pp. 14-36. [43] A. L. Pardhanani, W. F. Spotz, and G. F. Carey, A stable multigrid strategy for convection-diffusion using high order compact discretization, Elect. Trans. Numer. Anal., 6 (1997), pp. 211-223. [44] L. F. Pavarino, Domain decomposition algorithms for first- order system least squares methods, Elect. Trans. Numer. Anal., 8 (1998), pp. 1-14. [45] M. Pernice, A hybrid multigrid method for the steady-state in- compressible Navier-Stokes equations, Elect. Trans. Numer. Anal., 10 (2000), pp. 74-91. [46] I. Persson, K. Samuelsson, and A. Szepessy, On the convergence of multigrid methods for flow problems, Elect. Trans. Numer. Anal., 8 (1998), pp. 46-87. [47] G. L. G. Sleijpen and D. R. Fokkema, BiCGstab(L) for lin- ear equations involving unsymmetric matrices with complex spectrum, Elect. Trans. Numer. Anal., 1 (1993), pp. 11-32. [48] E. Sterner, A multigrid smoother for high Reynolds number flows, Elect. Trans. Numer. Anal., 6 (1997), pp. 234-245. [49] C. A. Thole, S. Mayer, and A. Supalov, Fast solution of MSC/NASTRAN sparse matrix problems using a multilevel approach, Elect. Trans. Numer. Anal., 6 (1997), pp. 246-254. [50] A. Toselli, Neumann-neumann methods for vector field prob- lems, Elect. Trans. Numer. Anal., 11 (2000), pp. 1-24. [51] P. S. Vassilevski and J. G. Wade, A comparison of multi- level methods for total variation regularization, Elect. Trans. Numer. Anal., 6 (1997), pp. 255-256. [52] E. L. Wachspress, The ADI Model Problem, Wachspress, Windsor, CA, 1995. [53] T. Washio and C. W. Oosterlee, Krylov subspace acceler- ation for nonlinear multigrid schemes, Elect. Trans. Numer. Anal., 6 (1997), pp. 271-290. [54] R. Weiss, Minimization properties and short recurrences for Krylov subspace methods, Elect. Trans. Numer. Anal., 2 (1994), pp. 57-75. [55] B. I. Wohlmuth, A multigrid method for saddle point problems arising from mortar finite element discretizations, Elect. Trans. Numer. Anal., 11 (2000), pp. 43-54. [56] J. Zhang, On preconditioning Schur complement and Schur complement preconditioning, Elect. Trans. Numer. Anal., 10 (2000), pp. 115-130. ------------------------------ End of MGNet Digest **************************