Send mail to:             for the digests or bakeoff
         for comments or help
Anonymous ftp repository: (
Current editor:  Craig Douglas

WWW Sites: or

Today's editor:  Craig Douglas (

Volume 13, Number 3 (approximately March 31, 2003)

Today's topics:

     Algebraic Multigrid Codes?
     Post doc announcement
     Changing Boundary Condition Request for Information
     ETNA Volume 15
     Submission to MGNet (Oh et al)


Date: Sun, 23 Mar 2003 12:04:10 +0200
From: Sivan Toledo 
Subject: Algebraic Multigrid Codes?

I am looking for AMG codes to solve a certain system of equations.  The system
is the Laplacian of a graph that represents a 2D surface in 3D.  The graph
represents the surface of a 3D model in computer graphics.  The matrix is
exactly the laplacian of the graph:  Aij=-1 iff i and j are neighbors,
Aii=degree of node i.  The graph is irregular.

We make the system nonsignular by adding constraints that specify the value of
the unknown vector at certain nodes.  One is theoretically sufficient but we
add several to get a reasonable condition number.  Also, we solve it as a
rectangular system, rather than eliminate the constrained vertices
symmetrically.  (You could think about this as keeping the constraints that
specify the BC explicitly).  We know that the recrangular system is always
well-conditioned, so now we solve using a direct solver on the normal

Is there an AMG code that will handle this problem?  It seems to me like a a
pretty easy problem for AMG, being a discrete Laplacian.  I came across one
possible code, BoomerAMG, and sent the link to the students working on this,
but I wonder if there are other codes worth trying.  In particular, we are
only interested in sequential codes, not parallel, so perhaps using BoomerAMG
will be more difficult than necessary for us.  I didnt find anything that
seemed appropriate on the mgnet web site.

Thanks, Sivan Toledo, Tel-Aviv University.


Date: Tue, 8 Apr 2003 11:29:50 +1100 
From: Patrick Lehodey 
Subject: Post doc announcement

We have funding for two post-doc scientists for two years with a project
funded by the Pelagic Fisheries Research Program from University of Hawaii.  I
would be grateful if you can include this post -doc announcement in your next
newsletter /or and on your website.

Oceanic Fisheries and Climate Change Project (OFCCP GLOBEC)
Grants for Postdoctoral scientists - mixed resolution models for individual
to population scale spatial dynamics 

The University of Hawaii (Honolulu, HI) and the Secretariat of the Pacific
Community (SPC, Noumea, New Caledonia) seek 2 postdoctoral scientists for a 2
yr project funded by the University's Pelagic Fisheries Research Program.  The
project addresses ways to improve upon two classes of models:  Advection
Diffusion Reaction Models (ADRMs) and Individual Based Models (IBMs) in
modelling the spatial dynamics of tunas and other large pelagics from
individual to ocean basin scales.  Mixed resolution models use a stretched
grid system with greater resolution at particular locations in the model
domain.  One position will work on adapting finite difference solutions of
ADRMs to the new grid and the other position will help develop the IBM
methodology.  Candidates must have completed a PhD in oceanography, marine
ecology, fisheries science or other relevant subject with a strong
computational/mathematical emphasis and possess good computer programming
skills, preferably in C++ and/or FORTRAN.  Further details may be obtained
from PFRP Program Manager Dr.  John Sibert (, Dr.  Patrick
Lehodey at the SPC (, and from the PFRP website and SPC website

Thank you very much in advance,
Patrick Lehodey
Principal Fisheries Scientist (Biology / Ecology)
Oceanic Fisheries Programme
Secretariat of the Pacific Community
BP D5, 98848 Noumea
Tel  +687 262000
Fax +687 263818


Date: Tue, 29 Apr 2003 12:08:14 -0400
From: Wengai Yang 
Subject: Changing Boundary Condition Request for Information

I am Wengai Yang from Mcmaster University in Canada, using multigrid method to
solve elliptic equations with boundary condition updated frequenty.  Now I am
stuck in the boundary area, I mean the result in boundary carea is not right,
could you please give me some suggestions or advice or introduce me to some
experts in this area?

Thanks and have a nice day.
Wengai Yang


Date: Mon, 31 Mar 2003 10:22:21 -0400
From: Craig Douglas 
Subject: ETNA Volume 15

U. M. Ascher and E. Haber.
A multigrid method for distributed parameter estimation problems.

Craig C. Douglas, Gundolf Haase and Mohamed Iskandarani.
An additive Schwarz preconditioner for the spectral element ocean model
formulation of the shallow water equations.

Scott R. Fulton.
On the accuracy of multigrid truncation error estimates.

Andrew V. Knyazev and Klaus Neymeyr. 
Efficient solution of symmetric eigenvalue problems using multigrid
preconditioners in the locally optimal block conjugate gradient method.

Jan Mandel.
Local approximation estimators for algebraic multigrid.

Malik Silva.
Cache aware data laying for the Gauss-Seidel smoother.

Linda Stals.
Comparison of non-linear solvers for the solution of radiation transport

Janne Martikainen, Tuomo Rossi and Jari Toivanen.
Multilevel preconditioners for Lagrange multipliers in domain imbedding.

Gene Poole, Yong-Cheng Liu and Jan Mandel.
Advancing analysis capabilities in ANSYS through solver technology.

Michael Bader and Christoph Zenger.
A robust and parallel multigrid method for convection diffusion equations.

B. Chang and B. Lee.
A multigrid algorithm for solving the multi-group, anisotropic scattering
Boltzmann equation using first-order system least-squares methodology.

Sandra Naegele and Gabriel Wittum.
Large-eddy simulation and multigrid methods.

C. W. Oosterlee.
On multigrid for linear complementarity problems with application to
American-style options.

Pavel B. Bochev, Jonathan J. Hu, Allen C. Robinson and Raymond S. Tuminaro.
Towards robust 3D Z-pinch simulations:  discretization and fast solvers for
magnetic diffusion in heterogeneous conductors.

Paul A. Farrell and Hong Ong.
Factors involved in the performance of computations on Beowulf clusters.


Date: Tue, 15 Apr 2003 16:08:43 -0500
From: Seungseok Oh 
Subject: Submission to MGNet (Oh et al)

Attached are our papers which our research group wish to submit for posting in
the MGNet 'papers' (or 'preprints') section.  These three papers present
multigrid algorithms for inverse problems which are especially arising from
image reconstruction applications.  The followings are brief descriptions of
the papers.

                             * * * * * * * * * *

Author: Charles Bouman and Ken Sauer
Title: Nonlinear Multigrid Methods of Optimization in Bayesian 
Tomographic Image Reconstruction
Appeared in {\em Proc. of SPIE Conf. on Neural and Stochastic Methods in 
Image and Signal Processing}, vol. 1766, pp. 296-306, San Diego, 
California, July 19-24, 1992.
Contact: Charles A. Bouman 

Bayesian estimation of transmission tomographic images presents formidable
optimization tasks.  Numerical solutions of this problem are limited in speed
of convergence by the number of iterations required for the propagation of
information across the grid.  Edge-preserving prior models for tomographic
images inject a nonlinear element into the Bayesian cost function, which
limits the effectiveness of algorithms such as conjugate gradient, intended
for linear problems.  In this paper, we apply nonlinear multigrid optimization
to Bayesian reconstruction of a two-dimensional function from integral
projections.  At each resolution, we apply Gauss-Seidel type iterations, which
optimize locally with respect to individual pixel values.  If the cost
function is differentiable, the algorithm speeds convergence; if it is
nonconvex and/or nondifferentiable, multigrid yield improved estimates.

                             * * * * * * * * * *

Author: Jong Chul Ye, Charles A. Bouman, Kevin J. Webb, and Rick P. Millane
Title : Nonlinear Multigrid Algorithms for Bayesian Optical Diffusion 
Appeared in {\em IEEE Trans. on Image Processing,} pp. 909-922, vol. 10, 
no. 6, June 2001
Contact: Charles A. Bouman 

Optical diffusion tomography is a technique for imaging a highly scattering
medium using measurements of the transmitted modulated light.  Reconstruction
of the spatial distribution of the optical properties of the medium from such
data is a very difficult nonlinear inverse problem.  Bayesian approaches are
effective, but are computationally expensive, especially for three-dimensional

This paper presents a general nonlinear multigrid optimization technique
suitable for reducing the computational burden in a range of non-quadratic
optimization problems.  This multigrid methods is applied to compute the
maximum a posteriori (MAP) estimate of the reconstructed image in the optical
diffusion tomography problem.  The proposed multigrid approach both
dramatically reduces the required computation and improves the reconstructed
image quality.

                             * * * * * * * * * *

Author: Seungseok Oh, Adam B. Milstein, Charles A. Bouman, and Kevin J. Webb
Title: A General Framework for Nonlinear Multigrid Inversion
Appeared in Technical Report TR-ECE 03-04, School of Electrical and 
Computer Engineering, Purdue University, March 2003.
Contact: Charles A. Bouman 

A variety of new imaging modalities, such as optical diffusion tomography,
require the inversion of a forward problem that is modeled by the solution to
a 3-D partial differential equation.  For these applications, image
reconstruction is particularly difficult because the forward problem is both
nonlinear and computationally expensive to evaluate.

In this paper, we propose a general framework for nonlinear multigrid
inversion that is applicable to a wide variety of inverse problems.  The
multigrid inversion algorithm results from the application of recursive
multigrid techniques to the solution of optimization problems arising from
inverse problems.  The method works by dynamically adjusting the cost
functionals at different scales so that they are consistent with, and
ultimately reduce, the finest scale cost functional.  In this way, the
multigrid inversion algorithm efficiently computes the solution to the desired
fine scale inversion problem.  Importantly, the new algorithm can greatly
reduce computation because both the forward and inverse problems are more
coarsely discretized at lower resolutions.  An application of our method to
optical diffusion tomography shows the potential for very large computational
savings.  Numerical data also indicates robust convergence with a range of
initialization conditions for this non-convex optimization problem.

Seungseok Oh
Ph.D. Candidate
School of Electrical and Computer Engineering
Mbox 457, 1285 EE Building
Purdue University
West Lafayette, IN 47907, USA
Ph: 765-494-6553

    Editor's Note: (only the real
    -------------  preprint is there, not the already published ones)


End of MGNet Digest