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 the Subject field. My real e-mail address is in the From field. Anonymous ftp repository: www.mgnet.org (128.163.209.19) WWW Sites: 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.jp/mirrors/mgnet or http://www.tat.physik.uni-tuebingen.de/~mgnet Editor: Craig Douglas (douglas-craig@cs.yale.edu) Associate editor: Gundolf Haase (gundolf.haase@uni-graz.at) Volume 15, Number 1 (approximately January 31, 2005) Today's topics: Important Dates Survey Paper on Saddle Point Problems Some Links from the GAMM-Leipzig Workshop Fast, Robust Solvers This is a great place to let the world know about your results. It is highly rated for letting the world know about recent graduates' dissertations and young reserachers' papers... and it is free and open source. ------------------------------------------------------- Date: Mon, 31 Jan 2005 10:22:21 -0400 From: Craig DouglasSubject: Important Dates Feb. 3 Copper Mountain author abstracts Mar. 3 Copper Mountain early registration and hotel reservations See http://amath.colorado.edu/faculty/copper Apr. 15 European Multigrid Conference abstracts (1 page) See http://pcse.tudelft.nl/emg2005/index.php ------------------------------------------------------- Date: Mon, 24 Jan 2005 13:57:55 -0500 (EST) From: Michele Benzi Subject: Survey Paper on Saddle Point Problems "Numerical Solution of Saddle Point Problems" Michele Benzi, Gene H. Golub and Joerg Liesen Abstract: Large linear systems of saddle point type arise in a wide variety of applications throughout computational science and engineering. Due to their indefiniteness and often poor spectral properties, such linear systems represent a significant challenge for solver developers. In recent years there has been a surge of interest in saddle point problems, and numerous solution techniques have been proposed for this type of system. The aim of this paper is to present and discuss a large selection of solution methods for linear systems in saddle point form, with an emphasis on iterative methods for large and sparse problems. CONTENTS 1 Introduction 2 Applications leading to saddle point problems 3 Properties of saddle point matrices 4 Overview of solution algorithms 5 Schur complement reduction 6 Null space methods 7 Coupled direct solvers 8 Stationary iterations 9 Krylov subspace methods 10 Preconditioners 11 Multilevel methods 12 Available software 13 Concluding remarks References The paper can be downloaded from http://www.mathcs.emory.edu/~benzi/Web_papers/bgl04.pdf NOTES: 1. The paper contains an extensive bibliography (537 entries). 2. To be published in Acta Numerica 2005. 3. Dedicated to Prof. Gil Strang on his 70th birthday. ------------------------------------------------------- Date: Sat, 29 Jan 2005 10:22:21 -0400 From: Craig Douglas Subject: Some Links from the GAMM-Leipzig Workshop Fast, Robust Solvers 1. NFFT: http://www.math.mu-luebeck.de/potts/nfft The NFFT is a C subroutine library for computing the non equispaced discrete Fourier transform (NDFT) in one or more dimensions, of arbitrary input size, and of complex data. NFFT is a free software library that is based on FFTW (FFTW 3.x). Features include - Implemented transforms for one and more dimensions. - Iterative solution of the inverse transform. - Arbitrary-size transforms. - Works on any platform with a C compiler and the FFTW package. - Simple and flexible interface, 'type safety' and easy adaptability. - Options (determined at compile time) and parameters (determined at run time). 2. Max-Planck Institute Leipzig (http://www.mis.mpg.de/preprints) There are many, many preprints here for a number of directly related topics to multigrid. There are also many, many interesting papers on topics less related to multigrid. 3. An almost linear time LU solver for second order elliptic operators (http://www.math.uni-leipzig.de/~bebendorf/AHMED.html) Another software library on Hierarchical Matrices for Elliptic Differential equations (AHMED) An approximate LU decomposition canbe computed in the algebra of hierarchical matrices with almost linear time complexity and with the same robustness as the classical LU decomposition method. Software is available at this site. There is a research report (see point 2 above) as well. 4. DUNE, the Distributed and Unified Numerics Environment (http://hal.iwr.uni-heidelberg.de/dune) DUNE aims to reach the following goals: - Distributed development - Unified access to different grid managers (ALBERTA , UG), visualization tools (Grape), solvers, etc. - high level abstraction through Operator concept 5. Generic programming for finite element methods (http://www.math.tu-cottbus.de/~berti/diss/) Gertram Berti Ph.D. dissertation Two problems are considered in Berti's dissertation: - First, how can algorithms operating on grids (or meshes) be implemented in a way that is independent of the concrete representation of a grid, and at the same time, sufficiently efficient? - Second, how can the paradigm of geometric partitioning (domain decomposition) which is used for distributed execution of a certain class of grid algorithms, be formalized and implemented in a reusable way, using the techniques of the first part? 6. Finite element solvers in LISP (http://www.femlisp.org) FEMLISP is a framework for solving partial differential equations with the help of the finite element method (FEM). It is written completely in Common Lisp. In contrast to other approaches this has the following advantages: - Common Lisp is a very expressive programming language which supports a multitude of programming styles: machine-oriented, imperative, functional, object-oriented - whatever you want. Therefore, for large projects, Common Lisp source code is usually much shorter than source code for handling the same problem in another language. - There is no need for a separate scripting language, because Lisp is used anyhow in an interactive environment and is suited very well to the tasks of a scripting language. However, unlike interpreted scripting languages (e.g. Perl, Python, TCL), Common Lisp code can be as efficient as equivalent C code. - Using Emacs with SLIME yields a powerful Common Lisp development environme nt. - Matlisp yields integration of the BLAS and LAPACK libraries. - Some computer algebra systems (Axiom, Maxima) as well as several other AI tools are Common Lisp programs which can be integrated easily. Functionality: - Interactive environment - Unstructured meshes in arbitrary space dimensions - Cells are arbitrary products of simplices - Automatic triangulation of 2D domains (interface to Triangle) - Lagrange finite elements of arbitrary order - Isoparametric and non-parametric cell mappings - Error estimators and adaptive mesh refinement strategies - Interfaces to direct solvers (SuperLU and UMFPACK) - Geometric and algebraic multigrid methods - Equations (diffusion-convection-reaction) - Systems (elasticity, incompressible flow) - Nonlinear problems - Eigenvalue problems - Time-dependent problems - Integrated graphics (interfaces to OpenDX and Gnuplot) - Integrated documentation, demonstrations, and tests 7. ILUPACK (http://www.math.tu-berlin.de/ilupack) ILUPACK provides several multilevel ILU preconditioners for general real and complex matrices as well as real and complex symmetric (Hermitian) positive definite systems. The basic idea of ILUPACK is based on inverse-based ILUs, that are incomplete LU decompositions that control the growth of the inverse triangular factors. New features in ILUPACK V1.1 released on December 3, 2004: * Many more interfaces with respect to existing software packages * interface for AMD from UMFPACK V4.3 * interface for MPS (maximum weight matching) from PARDISO * interface for MeTiS multilevel nested dissection * various combination of maximum weight matching (MC64 and MPS) followed by symmetric reorderings * backward error as stopping criterion * several variants of preconditioning (besides right preconditioning, which is default) ------------------------------ End of MGNet Digest **************************