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