Send mail to: mgnet@cs.yale.edu for the digests or bakeoff
mgnet-requests@cs.yale.edu for comments or help
Anonymous ftp repository: www.mgnet.org (128.163.209.19)
Current editor: Craig Douglas douglas-craig@cs.yale.edu
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
**************************