Send mail to:             for the digests or bakeoff
         for comments or help
Anonymous ftp repository: (
Current editor:  Craig Douglas
the Subject field.  My real e-mail address is in the From field.

Anonymous ftp repository: (

WWW Sites: or

Editor:  Craig Douglas (

Associate editor:  Gundolf Haase (

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 Douglas 
Subject: Important Dates

Feb. 3   Copper Mountain author abstracts
Mar. 3   Copper Mountain early registration and hotel reservations

Apr. 15  European Multigrid Conference abstracts (1 page)


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.


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   

The paper can be downloaded from


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:

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
    - Options (determined at compile time) and parameters
      (determined at run time).

2. Max-Planck Institute Leipzig (

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 (

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 

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

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

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


    - 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 


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