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.etl.go.jp/mgnet or http://www.nchc.gov.tw/RESEARCH/Math/mgnet/www/mgnet.html Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 10, Number 8 (approximately August 31, 2000) Today's topics: Maxwell Equations' Paper by Gopalakrishnan and Pasciak AMG paper by Beck New book available AMG Presentation at Strobl - Bayreuther and Miehe AMG Presentation at Strobl - Beck AMG Presentation at Strobl - Bollhoefer AMG Presentation at Strobl - Douglas and Iskandarani AMG Presentation at Strobl - Henson and Vassilevski Contents of Numerical Linear Algebra with Applications ------------------------------------------------------- From: Joe PasciakSubject: Maxwell Equations' Paper Overlapping Schwarz Preconditioners for Indefinite Time Harmonic Maxwell Equations Jayadeep Gopalakrishnan and Joseph E. Pasciak Department of Mathematics Texas A&M College Station, Texas Abstract. Time harmonic Maxwell equations in lossless media 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 spaces can be employed to get approximate solutions numerically . The problem of preconditioning the indefinite matrix arising from this method is discussed here. Specifically , two overlapping Schwarz methods will be shown to yield uniform preconditioners. Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html ------------- for the hyperlinks. ------------------------------------------------------- From: Craig Douglas Subject: AMG paper by Beck Algebraic Multigrid by Component Splitting for Edge Elements on Simplicial Triangulations Rudolf Beck Konrad-Zuse-Zentrum fur Informationstechnik Berlin Takustrasse 7 D-14195 Berlin-Dahlem Germany Preprint SC 99-40 (December 1999) Abstract Our focus is on Maxwell's equations in the low frequency range; two specic applications we aim at are time-stepping schemes for eddy current computations and the stationary double-curl equation for time-harmonic fields. We assume that the computational domain is discretized by triangles or tetrahedrons; for the nite element approximation we choose Nedelec's H(curl)-conforming edge elements of the lowest order . For the solution of the arising linear equation systems we devise an algebraic multi-grid preconditioner based on a spatial component splitting of the field. Mesh coarsening takes place in an auxiliary subspace, which is constructed with the aid of a nodal vector basis. Within this subspace coarse grids are created by exploiting the matrix graphs. Additionally , we have to cope with the kernel of the curl-operator, which comprises a considerable part of the spectral modes on the grid. Fortunately, the kernel modes are accessible via a discrete Helmholtz decomposition of the fields; they are smoothed by additional algebraic multigrid cycles. Numerical experiments are included in order to assess the efcacy of the proposed algorithms. Key words: Algebraic multigrid, mesh coarsening, edge elements, Nedelec spaces, Maxwell's equations AMS(MOS) subject classications: 65N55, 65N30, 65F10, 35Q60 Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html ------------- for the hyperlinks. ------------------------------------------------------- Date: Mon, 28 Aug 2000 12:51:04 -0500 (CDT) From: Zhangxin Chen Subject: New book available Numerical Treatment of Multiphase Flows in Porous Media, Zhangxin Chen, Richard E. Ewing, and Z.-C. Shi, Eds. http://www.springer.de/cgi-bin/search_book.pl?isbn=3-540-67566-3 e-mails: orders@springer-ny.com or orders@springer.de Lecture Notes in Physics, Vol. 552, Springer-Verlag 2000. XXI, 445 pages, 3-540-67566-3, Hardcover DM 164; US$ 92.64 This book describes in detail the current, state-of-the-art numerical treatment and simulation of multiphase flows in porous media. The porous media considered range from ordinary to fractured and deformable media, the models treated from single-phase compressible flow to multiphase multicomponent flow with mass interchange, the numerical methods studied from standard finite difference and finite element methods to nonstandard mixed finite element and characteristics-based techniques, and the computational algorithms encompass everything from classical iterative solvers to modern multigrid and domain decomposition approaches. Addressing many problems originating from the applied geosciences, the book focuses on their common mathematical and computational aspects. It will serve as an excellent research reference for all geoscientists, mathematicians, physicists, and engineers who work in the mathematical modeling and numerical simulation of multiphase flows in porous media. Contents Introduction--Mathematical and Numerical Techniques in Energy and Environmental Modeling, Zhangxin Chen and Richard E. Ewing, 1--21 Domain Decomposition for Some Transmission Problems in Flow in Porous Media, Clarisse Alboin, Jerome Jaffre, Jean E. Roberts, Xuewen Wang, and Christophe Serres, 22--34 Numerical Subgrid Upscaling of Two-Phase Flow in Porous Media, Todd Arbogast, 35--49 Numerical Simulation of Multiphase Flow in Fractured Porous Media, Peter Bastian, Zhangxin Chen, Richard E. Ewing, Rainer Helmig, Hartmut Jakobs, and Volker Reichenberger, 50--68 The Modified Method of Characteristics for Compressible Flow in Porous Media, Aijie Cheng and Gaohong Wang, 69--79 A Numerical Algorithm for Single Phase Fluid Flow in Elastic Porous Media, Hongsen Chen, Richard E. Ewing, Stephen L. Lyons, Guan Qin, Tong Sun, and David P. Yale, 80--92 On the Discretization of Interface Problems with Perfect and Imperfect Contact, Tatiana Chernogorova, Richard E. Ewing, Oleg Iliev, and Raytcho~Lazarov, 93--103 Finite Element Analysis for Pseudo-Hyperbolic Integral-Differential Equations, Xia Cui, 104--115 A CFL-Free Explicit Scheme with Compression for Linear Hyperbolic Equations, Ronald A. DeVore, Hong Wang, Jiang Guo Liu, and Hong Xu, 116--123 Maximizing Cache Memory Usage for Multigrid Algorithms for Applications of Fluid Flow in Porous Media, Craig C. Douglas, Jonathan Hu, Mohamed Iskandarani, Markus Kowarschik, Ulrich Rude, and Christian Weiss, 124--137 A Locally Conservative Eulerian-Lagrangian Method for Flow in a Porous Medium of a Mixture of Two Components Having Different Densities, Jim Douglas, Jr., Felipe Pereira, and Li Ming Yeh, 138--155 Validation of Non-Darcy Well Models Using Direct Numerical Simulation, Vladimir A. Garanzha, Vladimir N. Konshin, Stephen L. Lyons, Dimitrios V. Papavassiliou, and Guan Qin, 156--169 Mathematical Treatment of Diffusion Processes of Gases and Fluids in Porous Media, Norbert Herrmann, 170--178 Implementation of a Locally Conservative Eulerian-Lagrangian Method Applied to Nuclear Contaminant Transport, Chieh Sen Huang and Anna M. Spagnuolo, 179--189 Application of a Class of Nonstationary Iterative Methods to Flow Problems, Xiuren Lei and Hong Peng, 190--194 Reservoir Thermal Recover Simulation on Parallel Computers, Baoyan Li and Yuanle Ma, 195--207 A Class of Lattice Boltzmann Models with the Energy Equation, Yuanxiang Li, Shengwu Xiong, and Xiufen Zou, 208--215 Block Implicit Computation of Flow Field in Solid Rocket Ramjets, Zhibo Ma and Jianshi Zhu, 216-221 Stable Conforming and Nonconforming Finite Element Methods for the Non-Newtonian Flow Pingbing Ming and Zhong Ci Shi, 222--232 Numerical Simulation of Compositional Fluid Flow in Porous Media, Guan Qin, Hong Wang, Richard E. Ewing, and Magne S. Espedal, 232--243 Parallelization of a Compositional Reservoir Simulator, Hilde Reme, Geirge Oye, Magne S. Espedal, and Gunnar E. Fladmark, 244--266 Relationships Among Some Conservative Discretization Methods, Thomas F. Russell, 267--282 Parallel Methods for Solving Time-Dependent Problems Using the Fourier-Laplace Transformation, Dongwoo Sheen, 283--291 Cascadic Multigrid Methods for Parabolic Pressure Problems Zhong Ci Shi and Xuejun Xu, 292--298 Estimation in the Presence of Outliers: The Capillary Pressure Case, Sam Subbey and Jan Erik Nordtvedt, 299--310 A Comparison of ELLAM with ENO/WENO Schemes for Linear Transport Equations, Hong Wang and Mohamed Al Lawatia, 311--323 An Accurate Approximation to Compressible Flow in Porous Media with Wells, Hong Wang, Dong Liang, Richard E. Ewing, Stephen L. Lyons, and Guan Qin, 324--323 Fast Convergent Algorithms for Solving 2-D Integral Equations of the First Kind, Yan Fei Wang and Ting Yan Xiao, 333--345 A Two-Grid Finite Difference Method for Nonlinear Parabolic Equations, Ziting Wang and Xianggui Li, 345--350 A Compact Operator Method for the Omega Equation, Francisco R. Villatoro and Jesus Garci a-Lafuente, 351--361 Domain Decomposition Algorithm for a New Characteristic Mixed Finite Element Method for Compressible Miscible Displacement Danping Yang, 362--372 A Boundary Element Method for Viscous Flow on Multi-Connected Domains, Dequan Yang, Tigui Fan, and Xinyu Yang, 373--377 A Characteristic Difference Method for 2D Nonlinear Convection-Diffusion Problems, Xi Jun Yu and Yonghong Wu, 378--389 Fractional Step Methods for Compressible Multicomponent Flow in Porous Media, Yirang Yuan, 390--403 A Model and Its Solution Method for a Generalized Unsteady Seepage Flow Problem, Guoyou Zhang, Tigui Fan, Zhongsheng Zhao, and Dequan Yang, 404--408 Domain Decomposition Preconditioners for Non-selfconjugate Second-Order Elliptic Problems, Huaiyu Zhang and Jiachang Sun, 409--418 Performance of MOL for Surface Motion Driven by a Laplacian of Curvature, Wen Zhang and Ian Gladwell, 419--429 A High-Order Upwind Method for Convection-Diffusion Equations with the Newmann Boundary Condition, Weidong Zhao, 430--441 ------------------------------------------------------- Date: Thu, 31 Aug 2000 11:12:07 -0400 From: Craig Douglas Subject: AMG Presentation at Strobl - Bayreuther and Miehe Construction of homogenization based transfer operators Claus Bayreuther and Christian Miehe Abstract This talk deals with an application of homogenization techniques to the construction of intergrid transfer operators in the case of linear elastic heterogeneous materials. So far, this strategy can only be accomplished to regular meshes. However, we will discuss an extension to irregular meshes which represents an alternative to algebraic transfer operators. Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html ------------- for the hyperlinks. ------------------------------------------------------- Date: Thu, 31 Aug 2000 11:12:07 -0400 From: Craig Douglas Subject: AMG Presentation at Strobl - Beck Algebraic Multigrid for Edge Elements by Component Splitting Rudolf Beck Abstract This talk is about the solution of Maxwell's equations in the low frequency range; the applications we aim at are implicit time-stepping schemes for eddy current computations and the stationary double-curl equation for time-harmonic fields. We assume that the computational domain is discretized by Nedelec's H(curl)-conforming edge elements of the lowest order. Algebraic coarsening strategies for such finite element spaces are harder to devise than in the case of Lagrange-type elements. The difficulties are basically due to the geometric structure of the vectorial shape functions. The solution presented here relies on a spatial component splitting of the fields, where mesh coarsening takes place in an auxiliary subspace constructed with the aid of Lagrange-type basis functions. Within this subspace coarse grids are created recursively by an advancing-front algorithm, which merely exploits the matrix graphs. Unfortunately, the non-trivial kernel of the curl-operator cannot be tackled within this setting. Thus we resort to a discrete Helmholtz decomposition of the fields, allowing an efficient smoothing of the kernel modes by a separate algebraic multigrid cycle. Some numerical experiments will be presented in order to assess the efficacy of the proposed algorithms. Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html ------------- for the hyperlinks. ------------------------------------------------------- Date: Thu, 31 Aug 2000 11:12:07 -0400 From: Craig Douglas Subject: AMG Presentation at Strobl - Bollhoefer AMG Preconditioners for Sparse Approximate Inverse Matrices Matthias Bollhoefer Dep. of Mathematics Chemnitz University of Technology D-09107 Chemnitz Germany Abstract In this talk we discuss the construction of an algebraic multilevel method which is adapted to a given sparse approximate inverse of a symmetric positive definite matrix. The idea behind this construction is a heuristic observation, that sparse approximate inverse preconditioners often approximate the large eigenvalues of the given matrix quite well, while the smaller ones are only fairly poor approximated. The AMG consists of a strategy that uses suitably selected columns of the scaled residual matrix to construct the restriction/prolongation operator. Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html ------------- for the hyperlinks. ------------------------------------------------------- Date: Thu, 31 Aug 2000 11:12:07 -0400 From: Craig Douglas Subject: AMG Presentation at Strobl - Douglas and Iskandarani Using a Multilayer Ocean Model on Clusters versus a Traditional Supercomputer Craig C. Douglas Department of Computer Science University of Kentucky 325 McVey Hall - CCS Lexington, KY 40506-0045, USA douglas@ccs.uky.edu Mohamed Iskandarani Institute of Marine and Coastal Sciences Rutgers University P.O. Box 231 New Brunswick, NJ 08903-0231, USA mohamed@ahab.rutgers.edu Abstract We simulate oceanic overflow problems. The long term goal of this research is to understand both the local dynamics of downslope flows in the ocean and their role in the Earth's global thermohaline circulation. The modeling of these flows and their climatic impact is complicated by the inherent range of spatial scales involved, which extend from the global scale [O(10,000) km] down to the local scale of the overflows themselves [O(1) km], and by the intrinsic three dimensionality of the overflow dynamics. The Spectral Element Ocean Model (SEOM) offers an elegant solution to these difficulties. It features advanced algorithms, based on h-p type finite element methods, allowing accurate representation of complex coastline and oceanic bathymetry, variable lateral resolution, and high order solution of the three dimensional oceanic equations of motion. SEOM's geometrical flexibility permits highly inhomogeneous horizontal grids. An added advantage of the technique is its scalability. Most of the computations are carried out at the element level; only interface information needs to be exchanged between elements. The dual characteristic of dense and structured local computations, and sparse and unstructured communication enhances the locality of the computations. The dual characteristic of dense and structured local computations, and sparse and unstructured communication enhances the locality of the computations, and makes SEOM ideally suited for parallel computers. In this talk we demonstrate what types of cluster machine characteristics are suitable for solving our problems, how much they cost at what point in time, and how they compare to a traditional RISC based supercomputer solution. Our comparisions will note time, money, and aggrevation factors. Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html ------------- for the hyperlinks. ------------------------------------------------------- Date: Thu, 31 Aug 2000 11:12:07 -0400 From: Craig Douglas Subject: AMG Presentation at Strobl - Henson and Vassilevski AMGe and Element-free AMGe: General algorithms for computing interpolation weights Van Emden Henson (speaker) and Panayot S. Vassilevski Center for Applied Scientific Computing Lawrence Livermore National Laboratory Box 808, L-560 Livermore CA 94551 Abstract We propose a new algorithm for constructing the interpolation weights in algebraic multigrid (AMG). The rule we propose is related to the interpolation described in [1] for AMGe, an element-based algebraic multigrid. There, the interpolation is based on an energy-minimization principle for finite element applications. We first review the classical algorithm for constructing interpolation weights in AMG, examining it from an energy-minimization perspective. Our purpose is to extend the classical algorithm in a more general setting than is possible for the traditional M-matrix applications of classical AMG. Next we examine the interpolation rule for AMGe, describing how it is related to the AMG rule and how it is derived as an energy minimization. However, in the AMGe method, as outlined in [1], applying the interpolation rule requires access to the entries of the individual element stiffness matrices. Further, these element matrices must be built on all coarse levels, which is a non-trivial and expensive task [2]. We propose an approach that does not require access to the element matrices even on the fine-grid. However, the additional information we require instead is knowledge of the so-called rigid body modes, that is, the vectors that span the null-space of the global (assembled) Neumann-type matrix. In the simplest case of scalar elliptic PDE discretization matrices, this is just the constant vector. For the elasticity problem, this comprises certain linear functions, which, in practice, means that one needs the coordinates of the fine-grid nodes. In some cases this information may not be available; we use only constant vectors for these cases. Based on the rigid body modes, we specify appropriate boundary conditions which are imposed on a local neighborhood matrix associated with a fine degree of freedom. This produces a sort of Neumann-type local (or element) matrix. Finally, we can simply apply the rule from the AMGe methods based on the Neumann local matrix. Some numerical results are given, illustrating the application of the method on discretized elliptic problems. References 1. M. Brezina, A. J. Cleary, R. D. Falgout, V. E. Henson, J. E. Jones, T. A. Manteuffel, S. F. McCormick, and J. W. Ruge, Algebraic multigrid based on element interpolation (AMGe), SIAM J. Sci. Comput. (submitted), 1998. 2. J. E. Jones and P. S. Vassilevski, AMGe based on element agglomeration, (1999) submitted. This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48. Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html ------------- for the hyperlinks. ------------------------------------------------------- Date: Sun, 03 Sep 2000 17:00:26 +0200 From: Maya Neytcheva Subject: Contents of Numerical Linear Algebra with Applications Numerical Linear Algebra with Applications Volume 7, Issue 1, 2000 A comparison of overlapping Schwarz methods and block preconditioners for saddle point problems A. Klawonn and L. Pavarino (pp.1-25) Efficient computation of the exponential operator for large, sparse, symmetric matrices L. Bergamaschi and M. Vianello (pp. 27-45) Numerical Linear Algebra with Applications Volume 7, Issue 2, 2000 Matrix stretching for sparse least squares problems M. Adlers and \AA. Bj\"{o}rck (pp. 51-65) Further Analysis of Minimum Residual Iterations Y. Saad (pp. 67-93) Numerical Linear Algebra with Applications Volume 7, Issue 3, 2000 Approximate inverse preconditioning in the parallel solution of sparse eigenproblems L. Bergamaschi, G. Pini and F. Sartoretto (pp. 99-116) Generalization of convergence conditions for restarted GMRES J. Zitko (pp. 117-131) A Newton-type algorithm for solving an extremal constrained interpolation problem K. Vlachkova (pp. 133-164) Numerical Linear Algebra with Applications Volume 7, Issue 4, 2000 Iterative computation of derivatives of repeated eigenvalues and the corresponding eigenvectors A. Andrew and R. Tan (pp. 151-167) Comparison between the convergence rates of the Chebyshev method and the related (2,2)-step methods X. Li (pp. 169-180) Perturbation theory and condition numbers for generalized and constrained linear least squares M. Gulliksson and P. Wedin (pp. 181-195) Real valued iterative methods for solving complex symmetric linear systems O. Axelsson and A. Kucherov (pp. 197-218) An accurate parallel block Gram-Schmidt algorithm without reorthogonalization D. Vanderstraeten (pp. 219-236) Numerical Linear Algebra with Applications Volume 7, Issue 5, 2000 A robust algebraic multilevel preconditioner for nonsymmetric M-matrices Y. Notay (pp. 243-267) Bounding the growth factor in Gaussian elimination for Buckley's class of complex symmetric matrices K. Ikramov and A. Kucherov (pp. 269-274) Almost block diagonal linear systems: sequential and parallel solution techniques, and applications P.Amodio, J,R,Cash, G.Roussos, R.W.Wright, G.Fairweather, I.Gladwell G.L.Kraut and M.Paprzycki (pp. 275-317) Efficient and stable solution of structured Hessenberg linear systems arising from difference equations L. Gemignani (pp. 319-335) On the condition numbers associated with the polar factorization of a matrix F. Chaitin-Chatelin and S. Gratton (pp. 337-354) Maya Neytcheva Department of Mathematics, University of Nijmegen Toernooiveld 1, 6525 ED Nijmegen, The Netherlands tel: +31-24-3652365 __fax: +31-24-3652140 e-mail: neytchev@sci.kun.nl ------------------------------ End of MGNet Digest **************************