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 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 Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) 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 ToledoSubject: 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 equations. 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 (sibert@hawaii.edu), Dr. Patrick Lehodey at the SPC (PatrickL@spc.int), and from the PFRP website http://www.soest.hawaii.edu/PFRP/ and SPC website http://www.spc.int/OceanFish/ 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 NEW CALEDONIA Tel +687 262000 Fax +687 263818 Email patrickl@spc.int http://www.spc.int/OceanFish/ http://www.spc.int/OceanFish/Html/TEB/index.htm http://www.spc.int/OceanFish/Html/Globec/index.asp ------------------------------------------------------- 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. 1-17. Craig C. Douglas, Gundolf Haase and Mohamed Iskandarani. An additive Schwarz preconditioner for the spectral element ocean model formulation of the shallow water equations. 18-28. Scott R. Fulton. On the accuracy of multigrid truncation error estimates. 29-37. Andrew V. Knyazev and Klaus Neymeyr. Efficient solution of symmetric eigenvalue problems using multigrid preconditioners in the locally optimal block conjugate gradient method. 38-55. Jan Mandel. Local approximation estimators for algebraic multigrid. 56-65. Malik Silva. Cache aware data laying for the Gauss-Seidel smoother. 66-77. Linda Stals. Comparison of non-linear solvers for the solution of radiation transport equations. 78-93. Janne Martikainen, Tuomo Rossi and Jari Toivanen. Multilevel preconditioners for Lagrange multipliers in domain imbedding. 94-15. Gene Poole, Yong-Cheng Liu and Jan Mandel. Advancing analysis capabilities in ANSYS through solver technology. 106-121. Michael Bader and Christoph Zenger. A robust and parallel multigrid method for convection diffusion equations. 122-131. B. Chang and B. Lee. A multigrid algorithm for solving the multi-group, anisotropic scattering Boltzmann equation using first-order system least-squares methodology. 132-151. Sandra Naegele and Gabriel Wittum. Large-eddy simulation and multigrid methods. 152-164. C. W. Oosterlee. On multigrid for linear complementarity problems with application to American-style options. 165-185. 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. 186-210. Paul A. Farrell and Hong Ong. Factors involved in the performance of computations on Beowulf clusters. 211-224. ------------------------------------------------------- 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 Abstract: 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 Tomography Appeared in {\em IEEE Trans. on Image Processing,} pp. 909-922, vol. 10, no. 6, June 2001 Contact: Charles A. Bouman Abstract: 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 imaging. 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 Abstract: 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. Sincerely, 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 Email: ohs@purdue.edu Editor's Note: http://www.mgnet.org/mgnet-papers.html#O (only the real ------------- preprint is there, not the already published ones) ------------------------------ End of MGNet Digest **************************