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://phase.hpcc.gr.jp/mirrors/mgnet http://www.nchc.gov.tw/RESEARCH/Math/mgnet/www/mgnet.html Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 11, Number 4 (approximately April 30, 2001) Today's topics: Mirroring of MGNet Postdoctoral Position at University of Kentucky Release of PETSc 2.1.0 HELP Copper Mountain Virtual Proceedings Tutorial on Cache Based Methods I-III Multigrid and Schwarz Methods for Time-Harmonic Maxwell Equations Enhancing the Cache Performance of Multigrid Codes on Structured Grids Monotonicity Preserving and Total Variation Diminishing ... Comparisons of Unstructured Multigrid... Computational and Numerical Mathematics Opportunities at NSF Multigrid Waveform Relaxation for Anisotropic... LFA00_2D_scalar Code and Talk PRISM'2001: Preconditioned Robust Iterative Solution Methods... Contents Numerical Linear Algebra with Applications Contents, ETNA ------------------------------------------------------- Date: Thu, 05 Apr 2001 04:40:29 +0900 From: NISHIDA AkiraSubject: Mirroring of MGNet I have recently fixed our mirroring configuration of http://phase.hpcc.gr.jp/mirrors/mgnet/ which was formerly http://phase.etl.go.jp/mgnet/. NISHIDA Akira Department of Computer Science, The University of Tokyo 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033 JAPAN TEL +81-3-5841-4076 FAX +81-3-3818-1073 E-mail: nishida@is.s.u-tokyo.ac.jp Editor's Note: This is great news. A Japanese mirror now works again and ------------- is up to date. Thanks! ------------------------------------------------------- Date: Wed, 11 Apr 2001 01:38:26 -0400 (EDT) From: Jun Zhang Subject: Postdoctoral Position at University of Kentucky Postdoctoral Research Associate Position in High Performance Scientific Computing, University of Kentucky A new postdoctoral research associate position is expected to become available in the Laboratory for High Performance Scientific Computing and Computer Simulation (HiPSCCS Lab) at the University of Kentucky. The postdoctoral associate will be working on a collaborative research project between the HiPSCCS Lab and an international research organization, to develop parallel preconditioning techniques and software package for some very large scale scientific applications and computer simulation. The following qualifications are highly desirable: 1.) a PhD in scientific computing or computational sciences; 2.) sound knowledge in modern preconditioning techniques; 3.) good programming skill in Fortran 90 and MPI. The starting date is in early July. Although this is a multi-year research effort, progress is reviewed and contract is renewed annually based on accomplishment and funding availability. More information about research activities in the HiPSCCS Lab can be found at http://www.cs.uky.edu/~hipscns. If you are interested in this position, please e-mail your curriculum vitae (with full publication list and e-mail addresses of three referees) in postscript, pdf or ASCII (no MSWORD, please) to Jun Zhang at jzhang@cs.uky.edu, or fax it to (859)323-1971. A postal mail can be sent to: Professor Jun Zhang, Director Laboratory for High Performance Scientific Computing and Computer Simulation Department of Computer Science University of Kentucky 773 Anderson Hall Lexington, KY 40506-0046 USA Applicants may be asked to show evidences of programming skill. Overseas travel may be required for this position. ------------------------------------------------------- Date: Fri, 13 Apr 2001 15:32:14 -0500 (CDT) From: Barry Smith Subject: Release of PETSc 2.1.0 Portable, Extensible Toolkit for Scientific Computation (PETSc) http://www.mcs.anl.gov/petsc We are pleased to announce the release of the PETSc 2.1.0 parallel software libraries for the implicit solution of PDEs and related problems. New features of this release include: (1) a parallel, sparse, symmetric matrix storage format, this includes support for sequential Cholesky and ICC(k) (2) a complete framework for parallel linear multigrid on structured grids (for both linear and nonlinear problems) (3) Mandel's balancing Neumann-Neumann method for scalar PDEs (4) an interface to the Tufo-Fischer highly efficient parallel coarse grid direct solver library tfs (5) support for managing "composite" vectors consisting of subvectors that represent conceptually different quantities (for example, constraints or Lagrange multipliers) (6) more complete hypertext documentation, including links to hypertext versions of all the examples and source code As always, please send bug reports, questions, and requests for new features to petsc-maint@mcs.anl.gov. Thanks for your continued support. The PETSc developers, Satish, Kris, Bill, Dinesh, Lois, and Barry Why 2.1.0? PETSc 2.1.0 represents the cumulation of several years of effort to convert PETSc 2.0 to use dynamic libraries. Dynamic libraries allow users to delay until runtime the choices of what algorithms and data structures to run without generating enormous executables. ------------------------------------------------------- Date: Wed, 18 Apr 2001 17:30:49 -0400 (EDT) From: mehrez@physics.mcgill.ca Subject: HELP Please I would like to ask for some help and I would appreciate if you can guide me. I am solving Poisson Eq. in 3D using Mutigrid Solver method in a unit cell. Intially I have used Fixed Boundary Conditions and things are fine. Now I would like to use periodic Boundary Conditions in two of the directions and fixed in the third. However, because the total charge in the system is not 0, I run into instability problems. Do you have any idea about a Ref. or a direction that I should follow. Thanks in advance for your help. Hatem HATEM MEHREZ Physics Department, McGill University 3600 University St. 420 Montreal, QP H3A 2T8 Tel:(1-514) 398 8322(W) - 845 9303(H) ------------------------------------------------------- Date: Sun, 01 Apr 2001 17:35:37 -0500 (EST) From: Craig Douglas Subject: Tutorial on Cache Based Methods I-III Cache Based Methods Uli Ruede, Markus Kowarschik, and Craig Douglas Additional contributors: Jonathan Hu and Christian Weiss An introduction to methods for improving locality of data usage in iterative methods will be presented. The emphasis will be for problems related to solving PDE's. Separate methods for structured, unstructured, and quasi-unstructured grids will be given. In some cases, but not all, bitwise identical results are achieved with respect to standard implementations of the algorithms considered. The methods are applicable to almost any compiled language. No background in machine architectures will be assumed or needed. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Fri, 6 Apr 2001 15:24:05 -0500 (CDT) From: Jay Gopalakrishnan Subject: Multigrid and Schwarz Methods for Time-Harmonic Maxwell Equations Jayadeep Gopalakrishnan Institute for Mathematics and its Applications 514 Vincent Hall, 206 Church St SE Minneapolis, MN 55414 Abstract Time-harmonic Maxwell equations in a lossless cavity lead to a second order differential equation for electric field involving a differential operator that is neither elliptic nor definite. A Galerkin method using Nedelec's curl-conforming finite elements can be employed to get approximate solutions numerically. In this talk, results of [4, 5] on the suitability of multigrid and Schwarz methods for efficiently solving the resulting indefinite linear system will be presented. The analysis of the present work builds on techniques in [1, 6] to overcome the difficulties caused by the non-ellipticity of the operator. As in their analysis, discrete Helmholtz decompositions play a crucial role. A new and critical ingredient of our analysis is an estimate on discrete solution operators of Maxwell equations. This estimate allows analysis of overlapping Schwarz methods in the spirit of perturbation arguments in [3], even though our operator is not elliptic. It also allows analysis of a `\' multigrid cycle using techniques of [2], although prima facie it may appear that ellipticity is required for application of these techniques. In both cases, the analysis involves comparison of operators with their analogues in positive definite case. Of practical importance is the fact that some algorithms that work well in the elliptic case, fails in our application. It has now been known for some time that a multigrid V-cycle with a point-Jacobi smoother is not appropriate for our problem. However, we show that a multigrid algorithm with block Jacobi or block Gauss-Seidel smoother, if the blocks are chosen as in [1], leads to good convergence rates, provided the coarse mesh used is sufficiently fine. Our results also indicate that, in contrast to the elliptic case, replacing subdomain solves by equivalent operations in overlapping Schwarz methods does not lead to good results. References: [1] D. N. Arnold, R. S. Falk and R. Winther. Multigrid in H(div) and H(curl). Numer. Math., 85(2):197-217, 2000. [2] J. H. Bramble, D. Y. Kwak, and J. E. Pasciak. Uniform convergence of multigrid V-cycle iterations for indefinite and nonsymmetric problems. SIAM J. Numer. Anal., 31(6):1746-1763, 1994. [3] X.-C. Cai and O. B. Widlund. Domain decomposition algorithms for indefinite elliptic problems. SIAM J. Sci. Stat. Comput., 13(1):243-258, 1992. [5] J. Gopalakrishnan and J. E. Pasciak. Overlapping Schwarz preconditioners for indefinite time harmonic Maxwell equations. Submitted. Available as IMA Preprint 1711, June 2000. [6] J. Gopalakrishnan, J. E. Pasciak and L. Demkowicz. A multigrid algorithm for time harmonic Maxwell equations. In preparation. [4] R. Hiptmair. Multigrid method for Maxwell's equations. SIAM J. Numer. Anal., 36(1):204-225, 1999. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Mon, 9 Apr 2001 14:09:55 +0200 From: Markus Kowarschik Subject: Enhancing the Cache Performance of Multigrid Codes on Structured Grids Enhancing the Cache Performance of Multigrid Codes on Structured Grids Markus Kowarschik System Simulation Group Department of Computer Science University of Erlangen-Nuremberg Germany markus.kowarschik@cs.fau.de Abstract Modern computer architectures use hierarchical memory designs in order to hide the latencies of accesses to main memory components, which are dramatically slow in contrast to the floating-point performance of the CPUs. Current memory designscommonly involve several levelsof cache memories, which can be accessed up to a hundred times faster than main memory. It is well-known that efflcient program execution can merely be achieved, if the codes respect the hierarchical memory design. However, iterative methods are characterized by successive sweeps over data sets, which -- for representative problems in science and engineering -- are much too large to fit in cache. In this paper we present techniques in order to enhance the cache efflciency of multigrid methods for variable-coefficient problems on regular mesh structures. A variety of performance results are provided, showing both profiling data and the speedups which can be achieved by applying our optimizations. Key words. Computer architecture, high performance computing, cache, iterative algorithms, multigrid methods AMS subject classifications. 65N55, 65F10, 65-04 ------------------------------------------------------- Date: Fri, 13 Apr 2001 13:31:48 -0400 From: Dimitri Mavriplis Subject: Comparisons of Unstructured Multigrid... Here are my viewgraphs for Copper Mtn. I now also have a paper to put there, it is the ICASE report that is due to come out soon, and also submitted to JCP. Dimitri Mavriplis - ICASE MS 132C NASA Langley Research Center Hampton, VA 23681 (757)-864-2213 (Voice) (757)-864-6134 (FAX) dimitri@icase.edu http://www.icase.edu/~dimitri Comparisons of Unstructured Multigrid as a Non-linear Solver, a Linear Solver, or a Pre-Conditioner Dimitri Mavriplis ICASE MS 132C NASA Langley Research Center Hampton, VA 23681 Abstract The relative efficiency of an unstructured multigrid algorithm used as a non-linear solver (FAS) is compared with the efficiency of the equivalent multigrid algorithm used as a linear solver on a Newton linearization of the non-linear problem, and with the efficiency obtained using either approach as a preconditioner for a non-linear GMRES method. Two types of problems are examined, the solution of a transient radiation diffusion problem, and the solution of the Navier-Stokes equations. In the first case, the discretization employs a nearest neighbor stencil and the linearized scheme operates on an exact Newton linearization. In the second case, the discretization is based on a second-order form which involves neighbors of neighbors while the linearization employed is based on a first-order accurate nearest-neighbor stencil. For the radiation diffusion case, the linear multigrid approach is more efficient than the FAS approach, mainly due to the expense involved in the more frequent computation of the highly non-linear residuals required in the non-linear multigrid case. When the linear system is solved to sufficient tolerance, quadratic convergence of the non-linear problem is observed. For the Navier-Stokes equations, quadratic convergence of the non-linear problem is not possible, since an inexact linearization is employed. While a linear multigrid iteration is shown to be substantially cheaper than the corresponding non-linear multigrid iteration, the relative performance of both methods depends largely on the tolerance to which the linear system is solved, and the achievable non-linear convergence rate. Using either method as a preconditioner rather than as a solver is also shown to provide additional convergence acceleration. Other issues such as memory requirements and robustness of the various schemes will also be discussed. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html for both. ------------- ------------------------------------------------------- Date: Fri, 13 Apr 2001 17:17:17 -0400 From: "Mavriplis, Catherine" Subject: Computational and Numerical Mathematics Opportunities at NSF As a program officer in Applied Mathematics and Computational Mathematics, the speaker will give an overview of avenues for requesting funding and discuss new directions in the mathematical sciences funding landscape. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Mon, 16 Apr 2001 09:47:02 -0400 (EDT) From: "Justin W.L. Wan" Subject: Monotonicity Preserving and Total Variation Diminishing ... Monotonicity Preserving and Total Variation Diminishing Multigrid Time Stepping Methods Antony Jameson Departmentof Aeronautics and Astronautics Stanford University Stanford, CA 94305-4035 jameson@baboon.stanford.edu Justin Wan Department of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1, Canada jwlwan@bryce1.uwaterloo.ca Abstract We propose a fast multiplicative and additive multigrid time stepping schemes for solving linear and nonlinear wave equations in one dimension. The idea is based on an upwind biased interpolationand residual restriction operators, and a nonstandard coarse grid update formula for linear equations. We prove that the two-level schemes preserve monotonicity and are total variation diminishing, and the same results hold for the multilevel additive scheme. We generalize the idea to nonlinear equations by solving local Riemann problems. We demonstrate numerically that these schemes are essentially nonoscillatory, and that the optimal speed of wave propagation of 2 ^{M}-1 is achieved, where M is the number of grids. Keywords. monotonicity preserving, total variation diminishing, multigrid time stepping AMS subject classifications. 65M12, 65M25, 65M55, 65F10 Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Tue, 17 Apr 2001 18:10:22 +0200 From: Jan Van LentSubject: Multigrid Waveform Relaxation for Anisotropic... Multigrid Waveform Relaxation for Anisotropic Partial Differential Equations Jan Van lent and Stefan Vandewalle Abstract Multigrid waveform relaxation provides fast iterative methods for the solution of time-dependent partial differential equations. In this paper we consider anisotropic problems and extend multigrid methods developed for the stationary elliptic case to waveform relaxation methods for the time-dependent parabolic case. We study line-relaxation, semicoarsening and multiple semicoarsening multilevel methods. A two-grid Fourier-Laplace analysis is used to estimate the convergence of these methods for the rotated anisotropic diffusion equation. We treat both continuous time and discrete time algorithms. The results of the analysis are confirmed by numerical experiments. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Tue, 24 Apr 2001 12:29:55 +0200 From: Roman Wienands Subject: LFA00_2D_scalar Code and Talk LFA00_2D_scalar is a Fourier analysis program written in Fortran-77. Both two and three grid analysis (LFA) for 2D scalar partial differential equations is included. The code supports many variants of coarsening strategies, coarse grid discretization, prolongation, restriction, and relaxation methods. This is copyrighted by Roman Wienands, 2000. Roman Wienands GMD - Institute for Algorithms and Scientific Computing (SCAI) D-53754 Sankt Augustin, Germany email: wienands@gmd.de Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html or ------------- http://www.mgnet.org/mgnet-codes.html ------------------------------------------------------- Date: Thu, 12 Apr 2001 17:42:09 +0200 From: Maya Neytcheva Subject: PRISM'2001: Preconditioned Robust Iterative Solution Methods... CONFERENCE ON Preconditioned Robust Iterative Solution Methods for Problems with Singularities (PRISM'2001) University of Nijmegen, May 21-23, 2001 Special issue of NLA An issue of the journal ``Numerical Linear Algebra with Applications'' will be devoted to papers presented at the conference. A preliminary program can be found at the conference web-page. Contact address: PRISM'2001, Department of Mathematics, University of Nijmegen Toernooiveld 1, 6525 ED Nijmegen, NL e-mail: prism01@sci.kun.nl URL:http://www.sci.kun.nl/math/prism01 ------------------------------------------------------- Date: Thu, 12 Apr 2001 17:49:01 +0200 From: Maya Neytcheva Subject: Contents Numerical Linear Algebra with Applications NLA web-page http: //www.interscience.wiley.com/jpages/1070-5325 Numerical Linear Algebra with Applications Volume 8, Issues 1-3, 2001 Reversing the row order for the row-by-row frontal method J.K. Reid and J.A. Scott (pp. 1-6) Fast and stable two-way algorithm for diagonal plus semi-separable systems of linear equations N. Mastronardi, S. Chandrasekaran and S. Van Huffel (pp. 7-12) Iterative solution of a coupled mixed and standard Galerkin discretization method for elliptic problems R. Lazarov, J. Pasciak and P. Vassilevski (pp. 13-31) Changing poles in the rational Lanczos method for the Hermitian eigenvalue problem K. Meerbergen (pp. 33-52) Nonequivalence transformation of $\lambda$-matrix eigenproblems and model embedding approach to model tuning W.R. Ferng, Wen-Wei Lin, D.J. Pierce and Chern-Shuh Wang (pp. 53-70) On the Odir iterative method for nonsymmetric indefinite linear systems A. Chronopoulos and D. Kincaid (pp. 71-82) Preconditioners for non-Hermitian Toeplitz systems R.H. Chan, D. Potts and G. Steidl (pp. 83-98) Superconvergence of finite difference approximations for convection-diffusion problems Q. Fang and T. Yamamoto (pp. 99-110) Reliable preconditioned iterative linear solvers for some numerical integrators D. Bertaccini (pp. 111-125) A note on hyperbolic transformations D. Janovska and G. Opfer (pp. 127-146) Minimum residual iteration for a dual-dual mixed formulation of exterior transmission problems G. Gatica and N. Heuer (pp. 147-164) A robust AINV-type preconditioning method for constructing sparse approximate inverse preconditioners in factored form S.A. Kharchenko, L.Yu. Kolotilina, A.A. Nikishin, A.Yu. Yeremin (pp. 165-179) Parallel multisplitting iterative methods for singular M-matrices Wen Li, Weiwei Sun, K. Liu (pp. 181-190) ------------------------------------------------------- Date: Sun, 29 Apr 2001 01:53:30 -0400 (EDT) From: Lothar Reichel Subject: Contents, ETNA Table of Contents, Electronic Transactions on Numerical Analysis (ETNA), vol. 11, 2000. ETNA is available at http://etna.mcs.kent.edu and several mirror sites as well as on CDROM. A. Toselli, Neumann-Neumann methods for vector field problems, pp. 1-24. M. A. Cawood and C. L. Cox, Perturbation analysis for eigenstructure assignment of linear multi-input systems, pp. 25-42. B. I. Wohlmuth, A multigrid method for saddle point problems arising from mortar finite element discretizations, pp. 43-54. S. Serra Capizzano and C. Tablino Possio, High-order finite difference schemes and Toeplitz based preconditioners for elliptic problems, pp. 55-84. P. Benner, R. Byers, H. Fassbender, V. Mehrmann, and D. Watkins, Cholesky-like factorizations of skew-symmetric matrices, pp. 85-93. K. Atkinson, D. D.-K. Chien and J. Seol, Numerical analysis of the radiosity equation using the collocation method, pp. 94-120. R. Gutie'rrez J. Rodriguez, and A. J. Sa'ez, Approximation of hypergeometric functions with matricial argument through their development in series of zonal polynomials, pp. 121-130. C. T. H. Baker and E. Buckwar, Continuous Theta-methods for the stochastic pantograph equation, pp. 131-151. Publication of volume 12 of ETNA is in progress. Presently the following papers are available: G. Meurant, Numerical experiments with algebraic multilevel preconditioners, pp. 1-65. H. Zhang, Numerical condition of polynomials in different forms, pp. 66-87. M. J. Castel, V. Migallo'n, and J. Penade's, On parallel two-stage methods for Hermitian positive definite matrices with applications to preconditioning, pp. 88-112. ------------------------------ End of MGNet Digest **************************