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 3 (approximately March 31, 2001) Today's topics: Pieter Wesseling Multigrid Book Project Finished ETH Domain Decomposition Workshop Announcement Copper Mountain Virtual Proceedings A Robust and Parallel Multigrid Method for Convection Diffusion Multiscale Scientific Computation: Review 2000 A Two-Level Preconditioner for Anisotropic Mixed Finite Elements Achieving Textbook Multigrid Efficiency (2 papers) Comparisons of Unstructured Multigrid A Hierarchical Domain Decomposition Method A Multigrid Approach for Fast Geodesic Active Contours Toward the Optimal Preconditioned Eigensolver Considerations for Parallel CFD Enhancements A Multilevel Preconditioner for Field-Circuit Coupled Problems An Optimal Iterative Method for the Time-Dependent Stokes Problem SIAM/EMS Conference Berlin, Sept. 2-6, 2001 CFP: ICPP-HPSECA01 2nd Announcement Meshfree Methods ------------------------------------------------------- Date: Sun, 25 Mar 2001 10:15:12 -0500 (EST) From: Craig DouglasSubject: Pieter Wesseling Multigrid Book Project Finished The book scanning is complete. Please reference the book through the web page http://www.mgnet.org/mgnet-books-wesseling.html ------------------------------------------------------- Date: Sat, 17 Mar 2001 07:35:44 +0100 (MET) From: Luca Pavarino Subject: ETH Domain Decomposition Workshop Announcement Two-day workshop on DOMAIN DECOMPOSITION METHODS June 7-8, 2001 ETH Zurich, Switzerland. Sponsors Department of Mathematics, University of Milan (www.mat.unimi.it) Seminar for Applied Mathematics, ETH Zurich (www.sam.math.ethz.ch) Organizers: L. Pavarino, University of Milan Ch. Schwab, ETH Zurich A. Toselli, ETH Zurich O. Widlund, Courant Institute The following speakers have confirmed their participation: Y. Achdou (Paris VII) A. Alonso (University of Milan) Ch. Bernardi (Université Pierre et Marie Curie, Paris) A. Buffa (Istituto di Analisi Numerica, Pavia) M. Dryja (Warsaw University) V. Heuveline (University of Heidelberg) R. Hoppe (University of Augsburg) A. Klawonn (GMD, St. Augustine) C. Lasser (Technical University of Munchen) Y. Maday (Université Pierre et Marie Curie, Paris) F. Nataf (Ecole Polythecnique, Paris) A. Patra (SUNY, Buffalo) L. Pavarino (University of Milan) A. Quarteroni (EPFL and Politecnico di Milano) F. Rapetti (Laboratoires ASCI, Paris) A. Valli (University of Trento) O. Widlund (Courant Institute, New York) B. Wohlmuth (University of Augsburg) The main purpose of this workshop is to give an overview of some of the most recent developments in the field of Domain Decomposition. We understand Domain Decomposition in a broad sense as relating to the construction of preconditioners for the large algebraic systems of equations which often arise in applications, by solving smaller instances of the same problem. We also, most certainly, wish to include studies of methods built from different discretizations in different subdomains such as in multi-physics models, mortar finite elements, etc. The workshop will also allow the participants to meet informally and give opportunities for people to make new acquaintances. If you are interested in participating please contact the organizers. For further information, such as program, hotel, and travel information, please see http://www.sam.math.ethz.ch/~toselli/DDW2001/main.html ------------------------------------------------------- Date: Sat, 31 Mar 2001 23:32:55 -0500 (EST) From: Craig Douglas Subject: Copper Mountain Virtual Proceedings In this issue are the first set of contributions to the Virtual Proceedings: http://www.mgnet.org/mgnet-cm2001.html There are more that will be in the April newsletter (it is already online and still growing), which will be mailed April 30th or so. Participants are still welcome and encouraged to contribute to the virtual proceedings. There are no size (other than my disk drive) or page constraints on the contributions. Achi's is 96 pages. Anyone for 100+? ------------------------------------------------------- Date: Wed, 28 Mar 2001 11:00:49 +0200 From: Michael Bader Subject: Paper on A Robust and Parallel Multigrid Method for Convection Diffusion A Robust and Parallel Multigrid Method for Convection Diffusion Equations Michael Bader and Christoph Zenger, Lehrstuhl fuer Informatik V der TU Muenchen, 80290 Muenchen, Germany bader@in.tum.de Abstract We present a multigrid method for the solution of convection diffusion equations that is based on the combination of recursive substructuring techniques and the discretization on hierarchical bases and generating systems. Robustness of the resulting method, at least for a variety of benchmark problems, is achieved by a partial elimination between certain "coarse grid unknowns." The choice of these coarse grid unknowns is motivated by the physical properties of the convection diffusion equation, but is independent of the actual discretized operator. The resulting algorithm has a memory requirement that grows linearly with the number of unknowns. This also holds for the computational cost of the setup and the individual relaxation cycles. We present numerical examples that indicate that the number of iterations needed to solve a convection diffusion equation is widely independent of the number of unknowns and of the type and strength of the convection field. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Thu, 22 Mar 2001 14:39:01 +0200 From: sarah fliegelmann Subject: Paper on Multiscale Scientific Computation: Review 2000 Multiscale Scientific Computation: Review 2000 Achi Brandt The Weizmann Institute of Science Rehovot 76100, Israel Abstract Most of the fundamental problems in physics, chemistryand engineering involve computation too hard even for future supercomputers, if conventional mathematical approaches are used. The reason is always a product of several complexity factors associated with the wide range of space and time scales characteristic to such problems. Each of these complexity factors can in principle be removed by various multiscale algorithms, i.e., employing separate processing at each scale of the problem, combined with interscale iterative interactions. A wide range of multiscale computational methods is described, emphasizing main ideas and interrelations between various fields. The reported areas include: top-efflciency multigrid methods in fluid dynamics; inverse PDE problems and data assimilation; feedback optimal control; PDE solvers on unbounded domains and on adaptable grids; wave/ray methods for highly indefinite equations; rigorous quantitative analysis of multigrid; many-eigenfunction problems and ab-initio quantum chemistry; fast evaluation of integral transforms on adaptive grids; multigrid Dirac solvers; fast inverse-matrix and determinant calculations and updates; multiscale Monte-Carlo methods in statistical physics, including the renormalization multigrid (RMG) methods; molecular mechanics (including fast force summation, fast macromolecular energy minimization, and Monte-Carlo methods at equilibrium, both for macromolecules and for large ensembles of small molecules); combination of small-scale equilibrium with large-scale dynamics; image processing (edge detection and picture segmentation); tomography (medical imaging and radar reconstruction); efflcient, general and highly accurate algebraic multigrid (AMG) schemes; fast practical graph algorithms; data clustering; and multiscale approaches to global optimization. Research supported by AFOSR and the Materials and Manufacturing Directorate, AFRL, Wright-Patterson Base, contract No. F33615-97-D-5405, by the European Offlce of Aerospace Research and Development (EOARD) of the US Air Force, Contract F61775-00-WE067, by Israel Ministry of Science, Cultureand Sport grant 9680, by Israel Absorption Ministry, Project No. 6682, by Israel Science Foundation grant No. 696/97, and by the Carl F. Gauss Minerva Center for Scientific Computation at the Weizmann Institute of Science. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Mon, 19 Mar 2001 11:01:30 -0600 (CST) From: Chisup Kim Subject: Paper on A Two-Level Preconditioner for Anisotropic Mixed Finite Elements A Two-Level Preconditioner for an Anisotropic Mixed Finite Element Problem Chisup Kim Texas A&M Department of Methematics College Station, TX Abstract We study a multilevel preconditioner for the linear system arising from a mixed finite element approximation of a second order anisotropic elliptic problem on uniform rectangular and triangular meshes. This preconditioner involves smoothing on the mixed problem and the preconditioning of an auxiliary problem, namely the corresponding finite element problem on the same mesh. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Fri, 30 Mar 2001 18:36:43 -0500 From: Boris Diskin Subject: Papers on Achieving Textbook Multigrid Efficiency General Framework for Achieving Textbook Multigrid Efficiency: One-dimensional Euler Example James L. Thomas Computational Modeling and Simulation Branch Mail Stop 128 NASA Langley Research Center Hampton, Virginia 23681 j.l.thomas@larc.nasa.gov Boris Diskin Institute for Computer Applications in Science and Engineering Mail Stop 132C NASA Langley Research Center Hampton, Virginia 23681 bdiskin@icase.edu Achi Brandt The Weizmann Institute of Science Rehovot 76100, Israel achi@wisdom.weizmann.ac.il Jerry C. South, Jr. Williamsburg, Virginia 23185 Abstract A general multigrid framework is discussed for obtaining textbook efficiency to solutions of the compressible Euler and Navier-Stokes equations in conservation law form. The general methodology relies on a distributed relaxation procedure to reduce errors in regular (smoothly varying) flow regions; separate and distinct treatments for each of the factors (elliptic and/or hyperbolic) are used to attain optimal reductions of errors. Near boundaries and discontinuities (shocks), additional local relaxations of the conservative equations are necessary . Example calculations are made for the quasi-one-dimensional Euler equations; the calculations illustrate the general procedure. Key words. textbook multigrid efficiency, distributed relaxation, Euler equations Subject classification. Applied and Numerical Mathematics * * * * * Textbook Multigrid Efficiency for the Incompressible Navier-Stokes Equations: High Reynolds Number Wakes and Boundary Layers James L. Thomas Computational Modeling and Simulation Branch Mail Stop 128 NASA Langley Research Center Hampton, Virginia 23681 j.l.thomas@larc.nasa.gov Boris Diskin Institute for Computer Applications in Science and Engineering Mail Stop 132C NASA Langley Research Center Hampton, Virginia 23681 bdiskin@icase.edu Achi Brandt The Weizmann Institute of Science Rehovot 76100, Israel achi@wisdom.weizmann.ac.il Abstract Textbook multigrid efficiencies for high Reynolds number simulations based on the incompressible Navier-Stokes equations are atained for a model problem of flow past a finiter rate plate. Elements of the Full Approximation Scheme multigrid algorithm, including distributed relaxation, defect correction, and boundary treatment, are presented for the three main physical aspects encountered: entering flow, wake flow, and boundary layer flow. Textbook efficiencies, i.e., reduction of algebraic errors below discetization errors in one full multigrid cycle, are attained for second order accurate simulations at a laminar Reynods number of 10,000. Keywords. incompressible Navier-Stokes equations, textbook multigrid efficiency, distributiverelaxation, defect-correction iteration Subject classification. Applied and Numerical Mathematics Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Mon, 02 Apr 2001 13:31:48 -0400 From: Dimitri Mavriplis Subject: Slides on Comparisons of Unstructured Multigrid 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 ------------- ------------------------------------------------------- Date: Thu, 29 Mar 2001 08:06:09 +0200 (IST) From: Elena Braverman Subject: Paper on A Hierarchical Domain Decomposition Method A Hierarchical Domain Decomposition Method for the Solution of Helmholtz and Biharmonic Equations Moshe Israeli and Elena Braverman Technion, Computer Science Department, Haifa 32000, Israel Amir Averbuch School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel Abstract Implicit discretization of time dependent problems in computational physics, semiconductor device simulation, electromigration and fluid dynamics often gives rise to elliptic equations. Helmholtz type equations usually appear in acoustics or electromagnetics and also as a result of time discretization of the Navier-Stokes equations. Biharmonic problems appear in elasticity and viscous flows. We solve the Helmholtz and the biharmonic equation by the Domain Decomposition (DD) methods. Previously [1] we adopted a DD method where the equation was solved in each subdomain with assumed boundary conditions, resulting in jumps in function or derivative on subdomain boundaries. These jumps were removed by the introduction of singularity layers. In order to account for the global effect of the layers we computed first the influence of each layer on each subdomain boundary, taking into account the decay or smoothing out of the influence as a function of the distance from the layer. To reduce the communication load, compression in a multiwavelet basis was applied. Nevertheless, this part of the procedure can become expensive as the number of subdomains grows considerably. An algorithm for a fast solution of the Poisson equation by decomposition of the domain into square domains and the subsequent matching of these solutions by the fast multipole method was developed in [2]. The algorithm developed in [1] incorporates the following steps: 1. In each subdomain a particular solution of the non-homogeneous equation with arbitrary Neumann (Dirichlet) boundary conditions is found. 2. The collection of particular solutions usually has discontinuities (or discontinuities in the derivatives) on the boundaries of the subdomains. We introduce double (single) layers on the boundaries to match the solutions from different domains to have continuous global solution. The effect of these layers on other boundaries is calculated. 3. The solutions obtained at the first step are patched by adding the solutions of the Laplace equation with the boundary conditions that were computed in the previous step. 4. An additional solution of the corresponding homogeneous equation is added to satisfy the global boundary conditions. Considerable improvement in the efficiency of the interface jump removal step can be achieved if at each step only adjacent boxes are matched. This is the basis of the hierarchical approach which was proposed in [4]. The "elementary step" of the hierarchical algorithm is the following. 1. First, for each two adjacent subdomains some boundary conditions are defined. These conditions should not contradict the given right hand side at the junctions (see [4]). The Poisson equation is solved with these boundary conditions by a fast spectral algorithm [3]. 2. The solutions have a discontinuity in the first derivative. We match the subdomains by adding certain discontinuous functions. In fact we only evaluate these functions at the boundaries of two adjacent subdomains and then solve the homogeneous equation in each subdomain with the cumulative boundary conditions. 3. The global homogeneous equation is solved in such a way that it satisfies the assumed conditions at the ``global boundaries" of the merged subdomains. The solution of the non-homogeneous equation is expensive if compared to the homogeneous equation where efficient algorithms are available [3]. This step is repeated hierarchically. For example, first the smallest adjacent domains are matched: box 1 with box 2, box 3 with box 4, then the merged box 1,2 is matched with 3,4, afterwards the box which is a union of boxes 1,2,3,4 is patched with the adjacent merged box etc. Here we extend the results of [1,4] in the following directions. 1. In addition to the Poisson equation, we solve the Helmholtz or modified Helmholtz equation. One of the problems that arise is resonance and non-resonance situations for Dirichlet and Neumann boundary conditions. This can be avoided by introducing "transparent" boundary conditions which are approximations to the Sommerfeld radiation boundary condition. This means that the scattered wave behaves asymptotically like a diverging spherical wave. Some modifications of the non-reflecting conditions were considered in [5]. 2. We solve the biharmonic equation with either a free boundary as in [2] or boundary conditions of one type only (Dirichlet or Neumann). The biharmonic equation is split into a coupled system of the Poisson equations. The unknown function satisfies the Poisson equation with a certain right hand side which will be called a vorticity function. The solution is also performed by DD. Here the matching algorithm which was developed in [1,4] is applied to find the smooth vorticity function which matches the given right hand side. Then we obtain a solution of the biharmonic equation. The global boundary conditions of either Dirichlet or Neumann type can be satisfied by the addition of an appropriate harmonic function, as was done for the solution of the Poisson equation. References 1. A. Averbuch, E. Braverman and M. Israeli, Parallel adaptive solution of a Poisson equation with multiwavelets, SIAM J. Sci. Comput. 22 (2000), 1053-1086. 2. L. Greengard and J.-Y. Lee, A direct adaptive Poisson solver of arbitrary order accuracy, J. Comput. Phys. 125 (1996), 415-424. 3. A. Averbuch, M. Israeli, L. Vozovoi, A fast Poisson solver of arbitrary order accuracy in rectangular regions, SIAM J. of Sci. Comput. 19 (1998), 933-952. 4. M. Israeli, E. Braverman and A. Averbuch, A Hierarchical domain decomposition method with low communication overhead, submitted to Proceedings of the 13th Domain Decomposition Conference, Lyon, 2000. 5. A. Bamberger, P. Joly and J.E. Roberts, Second-order absorbing boundary conditions for the wave equation: a solution for the corner, SIAM J. Numer. Anal. 27 (1990), 323-352. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Wed, 14 Mar 2001 12:03:38 +0200 (IST) From: Avraham Kenigsberg Subject: Paper on A Multigrid Approach for Fast Geodesic Active Contours A Multigrid Approach for Fast Geodesic Active Contours Avraham Kenigsberg Department of Computer Science Technion, Haifa 32000, Israel Abstract Image segmentation is a basic and important problem in the field of computer vision. A recent geometric approach for image segmentation is the geodesic active contour based on the level-set method. One drawback of the method, is the extended numerical support that makes its solution time consuming. We propose to solve an implicit system of the geodesic active contour model using the computationally efflcient multigrid method. Key words. Level set, geodesic active contour, multigrid, segmentation. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Thu, 29 Mar 2001 12:48:50 -0700 From: Andrew Knyazev Subject: Paper on Toward the Optimal Preconditioned Eigensolver Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method Andrew V. Knyazev Departmentof Mathematics University of Colorado at Denver P .O. Box 173364, CampusBox 170 Denver, CO 80217-3364 andrew.knyazev@cudenver.edu http://www-math.cudenver.edu/~aknyazev Abstract We describe new algorithms of the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) Method for symmetric eigenvalueproblems, based on a local optimization of a three-term recurrence, and suggest several other new methods. To be able to compare numerically different methods in the class, with different preconditioners, we propose a common system of model tests, using random preconditioners and initial guesses. As the "ideal" control algorithm, we advocate the standard preconditioned conjugate gradient method for finding an eigenvector as an element of the nullspace of the corresponding homogeneous system of linear equations under the assumption that the eigenvalue is known. We recommend that every new preconditioned eigensolver be compared with this "ideal" algorithm on our model test problems in terms of the speed of convergence, costs of every iterations and memory requirements. We provide such comparison for our LOBPCG method. Numerical results establish that our algorithm is practically as efficient as the "ideal" algorithm when the same preconditioner is used in both methods. We also show numerically that the LOBPCG method provides approximations to first eigenpairs of about the same quality as those by the much more expensive global optimization method on the same generalized block Krylov subspace. We propose a new version of block Davidson's method as a generalization of the LOBPCG method. Finally , direct numerical comparisons with the Jacobi-Davidson method show that our method is more robust and converges almost two times faster. Key words. symmetric eigenvalueproblems, preconditioning, conjugate gradient methods, the Lanczos method AMS(MOS) subject classifications. 65F15, 65N25 Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Tue, 13 Mar 2001 10:45:23 -0800 From: Mark Kremenetsky Subject: Paper on Considerations for Parallel CFD Enhancements Considerations for Parallel CFD Enhancements on SGI ccNUMA and Cluster Architectures Mark Kremenetsky, PhD, Principal Scientist, CFD Applications SGI Mountain View, CA, mdk@sgi.com, 650.933.2304 Tom Tysinger, PhD, Principal Engineer Fluent Inc, Lebanon, NH, tlt@fluent.com, 603.643.2600 Stan Posey, HPC Applications Market Development SGI Mountain View, CA, sposey@sgi.com, 650.933.1689 Abstract The maturity of Computational Fluid Dynamics (CFD) methods and the increasing computational power of contemporary computers has enabled industry to incorporate CFD technology in several stages of design processes. As the application of the CFD technology grows from component level analysis to system level, the complexity and the size of models increase continuously. Successful simulation requires synergy between CAD, grid generation and solvers. The requirement for shorter design cycles has put severe limitations on the turnaround time of the numerical simulations. The time required for (1) mesh generation for computational domains of complex geometry and (2) obtaining numerical solutions for flows with complex physics has traditionally been the pacing item for CFD applications. Unstructured grid generation techniques and parallel algorithms have been instrumental in making such calculations affordable. Availability of these algorithms in commercial packages has grown in the last few years and parallel performance has become a very important factor in the selection of such methods for production work. Although extensive research has been devoted in determining the optimum parallel paradigm, in practice the best parallel performance can be obtained only when algorithm and paradigms take into consideration the architectural design of the target computer system they are intended for. This paper addresses the issues related to efficient performance of the commercial CFD software FLUENT on a cache coherent Non Uniform Memory (ccNUMA) Architecture. Also presented are results from implementation of FLUENT on cluster systems of workstation for both the Linux and SGI IRIX operating systems. Issues related to performance of the message passing system and memory-processor affinity are investigated for efficient scalability of FLUENT when applied to a variety of industrial problems. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Fri, 30 Mar 2001 13:47:33 +0200 (MET DST) From: Domenico Lahaye Subject: Paper on A Multilevel Preconditioner for Field-Circuit Coupled Problems A Multilevel Preconditioner for Field-Circuit Coupled Problems Domenico Lahaye Dept. of Computer Science, Celestijnenlaan 200A, B-3001 Heverlee Belgium Abstract In simulating time-varrying magnetic fields in electromagnetic devices like motors and transformers, it is often necessary to couple the partial differential equation for the magnetic field with a model for the external electrical circuit connections. The electrical circuit is a system of linear equations relating the unknown currents and voltages of the electrical conductors present in the device to known voltage and current sources. Time-varrying sources give rise to magnetically induced currents and voltages in the conductors. The partial differential equation and the circuit are coupled by these magnetically induces quantities. In low-frequent time-harmonic Maxwell formulations in two dimensions, the partial differential governing the magnetic vector potential is the Helmholtz equation with a complex shift. The finite element discretization of this equation results in sparse, complex symmetric system matrices. Discretized field-circuit coupled problems yield two by two block structured matrices whose diagonal is formed by the discretized partial differential equation and the electrical circuit matrix. The size of the second diagonal block is typically several orders of magnitude smaller than that of the first. The coupling is performed in such a way that no fill-in occurs in the discritized differential equation matrix and that the two by two block matrices are again complex symmetric. Solving the linear system is the computational bottleneck in simulating technically relevant engineering problems. Motivated by previous experience [1,2], we want to alleviate this bottleneck by the application of algebraic multigrid (AMG) techniques. The straightforward application of AMG is hampered by the presence of the electrical circuit. We develloped a multigrid cycle that takes the circuit into account. Our multigrid technique is a generalization of a method by Hackbush for solving an elliptic problem augmented by an algebraic equation. We base the AMG setup on the differential equation block of the matrix. The electrical circuit is taking into account in the cycling phase. The resulting algorithm is a black-box solver for general field-circuit coupled problems. For the implementation of our multigrid technique, we develloped an interface between the GMD-AMG-code by Stueben and PETSc. This interace allows to call the AMG setup on the differential equation block of the system matrix. After the setup, the AMG coarser grid and interpolation operators are available as PETSc matrices. The multigrid cycling is done by PETSc's multigrid components that we extended to be able to treat the electrical circuit. Our algorithm has been tested on a variety of engineering problems. It has proven to be stable and to deliver a speedup by a factor between five and ten compared to previously existing solvers. References 1. R. Mertens, H. De Gersem, R. Belmans, K. Hameyer, D. Lahaye, S. Vandewalle and D. Roose, "An Algebraic Multigrid Method for Solving Very Large Electromagnetic Systems", IEEE Trans. on Magn., Vol 34 (5), 3327-3330 (1999). 2. D. Lahaye, H. De Gersem, S. Vandewalle and K. Hameyer, "Algebraic Multigrid for Complex Symmetric Systems", IEEE Trans. on Magn., Vol 36 (4), 1535-1538 (2000). Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Thu, 22 Mar 2001 10:47:40 +0100 From: Kent-Andre Mardal Subject: Paper on An Optimal Iterative Method for the Time-Dependent Stokes Problem An Optimal Iterative Method for the Time-Dependent Stokes Problem K. A. Mardal, R. Winther, and H. P. Langtangen Department of Informatics University of Oslo P.O. Box 1080 Blindern 0316 Oslo, Norway kent-and@ifi.uio.no, rwinther@ifi.uio.no, and hpl@ifi.uio.no Abstract In this paper we consider an optimal multigrid/domain decomposition preconditioner for the time-dependent Stokes problem. Preconditioners for this problem arise when using fully implicit time stepping schemes for the Navier-Stokes equations. However, as the time stepping parameter decreases towards 0, the problem to be solved at each time step changes from the Stokes problem to the mixed formulation of the Poisson equation. The same preconditioning techniques do not work in both cases, even the finite elements typically used for Stokes are not considered stable for the mixed Poisson equation. We will show that some typical Stokes elements are in fact stable also for the Poisson equation in another norm, this leads us to a proper preconditioner working uniformly in the time stepping parameter. The efficiency of this preconditioner will be demonstrated by numerical experiments done in with Diffpack, a C++ toolbox for finite element simulations. It is established that the preconditioner works well for the Mini element. Numerical experiments indicate that this preconditioner also works for the Q _{2}-Q_{1}and P_{2}-P_{1}elements. Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Wed, 14 Mar 2001 13:33:12 +0100 From: Kees OosterleeSubject: Paper on On Multigrid for Linear Complementarity Problems with Application to American-style Options C. W. Oosterlee GMD, Institute for Algorithms and Scientific Computing D-53754 Sankt Augustin, Germany oosterlee@gmd.de Abstract. We discuss a nonlinear multigrid methodfor a linear complementarity problem. The convergence is improved by a recombination of iterants. The problem under consideration deals with option pricing from mathematical finance. Linear complementarity problems arise from so-called American-style options. A 2D convection-diffusion type operator is discretized with the help of second order upwind discretizations. The properties of smoothers are analyzed with Fourier two-grid analysis. Numerical solutions obtained for the option pricing problem are compared with reference results. Key words. linear complementarity problems, American-style options, nonlinear multigrid, projected Gauss-Seidel, iterant recombination, second-order upwind discretization, Fourier analysis AMS subject classifications. 65M55, 65F99, 90A09 Editor's Note: See http://www.mgnet.org/mgnet-cm2001.html ------------- ------------------------------------------------------- Date: Thu, 8 Mar 2001 09:37:42 +0100 From: Peter Deuflhard Subject: SIAM/EMS Conference Berlin, Sept. 2-6, 2001 The Society for Industrial and Applied Mathematics (SIAM) and the European Mathematics Society (EMS) are jointly organizing the First SIAM/EMS Conference on APPLIED MATHEMATICS IN OUR CHANGING WORLD, to be held in Berlin, Sept. 2 - 6, 2001, on the attractive Dahlem campus, where also ZIB is situated. The list of TOPICS and CONFIRMED INVITED SPEAKERS is 1. Medicine: Alfio Quarteroni (I) 2. Biotechnology: Michael Waterman (USA) 3. Materials Science: Jon Chapman (UK) 4. Environmental Science: Andrew Majda (USA) 5. Nanoscale Technology: Michael Griebel (D) 6. Communication: Martin Groetschel (D) 7. Traffic: Kai Nagel (CH) 8. Market and Finance: Benoit Mandelbrot (USA) 9. Speech and Image Recognition: Pietro Perona (USA) 10.Engineering Design: Thomas Y. Hou (USA) For more information please check http://www.zib.de/amcw01 The International Program Committee is now encouraging the organization of MINISYMPOSIA within the frame of the 10 main topics above. MINISYMPOSIA SCHEME =================== The scheme of the minisymposia follows the tradition of the ones within SIAM meetings. Typically a minisymposium is organized by two organizers and consists of four invited talks of half an hour each. The organizers and the speakers should be spread internationally. Two of the talks may well be given by the two organizers. I am sorry to say that neither registration fees will be waived nor will travel or local costs be covered for organizers or invited speakers of minisymposia. Organizers may, of course, try to raise funds from any other sources. We might help with material about the conference, if needed. THE SUBMISSION OF MINISYMPOSIA CAN BE DONE FULLY ELECTRONICALLY, WHICH IS ALSO DEFINITELY PREFERRED BY THE ORGANIZERS -- just look up "HOW TO CONTRIBUTE" on our website. DEADLINE ======== The official deadline for submission of minisymposia is April 15, 2001. But I urge anyone interested to make up their mind as soon as possible. Take into account that Berlin is also an attractive tourist city! Peter Deuflhard Chair of Program Committee Register NOW NOW NOW NOW NOW NOW NOW for: First SIAM/EMS Conference APPLIED MATHEMATICS IN OUR CHANGING WORLD to be held in Berlin, Sept. 2-6, 2001. Web: http://www.zib.de/amcw01 ------------------------------------------------------- Date: Tue, 13 Mar 2001 06:55:54 -0400 From: "Laurence T. Yang" Subject: CFP: ICPP-HPSECA01 The 3rd Workshop on High Performance Scientific and Engineering Computing with Applications (HPSECA-01) Valencia, Spain, September 3-7, 2001 in conjunction with 2001 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING (ICPP-2001) Scope and Interests: Parallel and distributed scientific and engineering computing has become a key technology which will play an important part in determining, or at least shaping, future research and development activities in many academic and industrial branches. This special workshop is to bring together computer scientists, applied mathematicians and researchers to present, discuss and exchange idea, results, work in progress and experience of research in the area of parallel and distributed computing for problems in science and engineering applications. Among the main topics (but not limited to) are: * development of advanced parallel and distributed methods, * parallel and distributed computing techniques and codes, * practical experiences using various supercomputers with software such as MPI, PVM, and High Performance Fortran, OpenMP, etc. * applications to numerical fluid mechanics and material sciences, * applications to signal and image processing, dynamic systems, semiconductor technology, and electronic circuits and system design etc. Submission Information: Authors should send one copy of paper in either PS or PDF format at most 15 pages to the workshop organizers (lyang@stfx.ca or pan@cs.gsu.edu ) via electronic mail or three copies via postal mail. Contributions will be reviewed by at least three reviewers from both Program Committee and external reviewers for relevance and technical contents on basis of papers. Accepted papers with at most 8 pages will be published by IEEE Computer Society Press as proceedings of the ICPP 2001 workshops. A special issue of International Journal of Supercomputer Applications and High Performance Computing is scheduled. Further information about the conference proceedings and registration fee can be found by web sites: http://www.stfx.ca/people/lyang/activities/icpp01-hpseca.html http://www.cis.ohio-state.edu/~panda/icpp01/workshops.html Important Deadlines: Paper submission Due (April 1, 2001!!) Notification of Acceptance May 1, 2001 Final camera-ready paper June 1, 2001 Workshop Organizers: Prof. Laurence T. Yang (chair) Department of Computer Science PO Box 5000, St. Francis Xavier University Antigonish, B2G 2W5, Nova Scotia, Canada lyang@stfx.ca Prof. Yi Pan (Co-Chair) Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA Email: pan@cs.gsu.edu ------------------------------------------------------- Date: Mon, 26 Mar 2001 17:16:50 +0200 From: Gerhard Zumbusch Subject: 2nd Announcement Meshfree Methods SECOND ANNOUNCEMENT AND CALL FOR PAPERS International Workshop Meshfree Methods for Partial Differential Equations Bonn, Germany September 11 - 14, 2001 http://wissrech.iam.uni-bonn.de/meshfree Organizers: Ivo Babuska (University of Texas, Austin, USA) Michael Griebel (Universitaet Bonn, Germany) Wing Kam Liu (Northwestern University, USA) Helmut Neunzert (Fraunhofer-Institut ITWM, Germany) Harry Yserentant (Universitaet Tuebingen, Germany) Invited Speakers: Satya Atluri (University of California, Los Angeles, USA) Ted Belytschko (Northwestern University, USA) Jiun-Shyan Chen (University of Iowa, USA) Gary Dilts (Los Alamos National Laboratory, USA) Weimin Han (University of Iowa, USA) Michael Junk (Universitaet Kaiserslautern, Germany) Petros Koumoutsakos (ETH Zuerich, Switzerland) Joe Monaghan (Monash University, Australia) Koji Morinishi (Kyoto Institute of Technology, Japan) Joseph Morris (Lawrence Livermore National Laboratory, USA) Bernard Nayroles (INSA Rouen, France) Jens Struckmeier (Universitaet Hamburg, Germany) Jean Paul Vila (Universite Paul Sabatier, Toulouse III, France) Jinchao Xu (Penn State University, USA) Important Dates and Deadlines: May 1, 2001 Early Registration and Abstract submission August 1, 2001 Confirmation and Program ======================================================================== Meshfree methods for the solution of partial differential equations gained much attention in recent years, not only in the engineering but also in the mathematics community. One of the reasons for this development is the fact that meshfree discretizations and particle models are often better suited to cope with geometric changes of the domain of interest, e.g. free surfaces and large deformations, than classical discretization techniques such as finite differences, finite elements or finite volumes. Another obvious advantage of meshfree discretizations is of course their independence of a mesh. Mesh generation is still the most time consuming part of any mesh based numerical simulation. Since meshfree discretization techniques are based only on a set of independent points these costs of mesh generation are eliminated. Finally, the coupling of particle models to continuous models gained enormous interest in recent years from a theoretical as well as from a practical point of view. Among the most prominent meshfree discretization techniques are: stochastic particle models, smoothed particle hydrodynamics, reproducing kernel particle methods, partition of unity methods, element free Galerkin methods, radial basis functions, vortex methods. The aim of the workshop is to bring together european and american researchers from different fields-inside and outside mathematics-not only to strengthen the mathematical understanding and analysis of meshfree discretizations but also to promote the exchange of ideas on their implementation and application. Topics of interest in the workshop are: analysis of meshfree methods, implementational issues of meshfree methods, coupling of particle models to continuous models, industrial applications of meshfree methods. The four day workshop program will consist of invited lectures, contributed papers and poster sessions. If you are interested in contributing to this workshop, please submit an abstract of about 300 words by e-mail to the contact address mailto:meshfree@iam.uni-bonn.de by May 1, 2001. International Workshop Meshfree Methods for Partial Differential Equations Rheinische Friedrich Wilhelms Universitaet Bonn Institut fuer Angewandte Mathematik Abteilung Wissenschaftliches Rechnen und Numerische Simulation Wegelerstrasse 6 D-53115 Bonn fax: +49 228 737527 mailto:meshfree@iam.uni-bonn.de http://wissrech.iam.uni-bonn.de/meshfree ------------------------------ End of MGNet Digest **************************