Send mail to: mgnet@cs.yale.edu for the digests or bakeoff
mgnet-requests@cs.yale.edu for comments or help
Current editor: Craig Douglas douglas-craig@cs.yale.edu
Anonymous ftp repository: ftp.ccs.uky.edu (128.163.209.106)
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://phase.etl.go.jp/mgnet or
http://www.nchc.gov.tw/RESEARCH/Math/mgnet/www/mgnet.html
Today's editor: Craig Douglas (douglas-craig@cs.yale.edu)
Volume 9, Number 5 (approximately May 31, 1999)
Today's topics:
Links in this Issue
Ask for help
Job Opening
Copper 99 paper (Muller)
Copper 1999 Paper (Brandt)
Copper Mountain 1999 Paper (Hu, Kowarschik, et al)
Copper 1999 Paper (Zhang)
Copper 1999 Paper (Douglas, Malhotra, & Schultz)
Three technical reports from Ge and Zhang
New Book
-------------------------------------------------------
Date: Sun, 06 May 1999 11:59:61 +0500
From: Craig Douglas
Subject: Links in this Issue
I am very far, far away. Pinging the MGNet system and its mirrors has been
taking up to 21 seconds. The links in this issue hopefully are correct. I
will be able to verify them all this week when I am again within a reasonable
distance of the office. If I missed a message, please let me know. I have
not been able to read my mail since the 2nd, however.
-------------------------------------------------------
Date: Tue, 18 May 1999 08:44:24 +0800
From: tc2
Subject: Ask for help
Dear Sir/Madams,
I am a PhD student at Dept. of Engr. Mechnics, Tsinghua University, PRC.
The main goal of my research is Seismic Inverse Problem. I am interested in
seismic simulation using multiscale techniques, and I have tried some methods
on multigrid.
I wonder if you have any new method or software on solving wave equations
(acoutic or elastic) using multiscale techniques such as wavelet analysis.
Can you give me some advices? Thank you very much.
Zhu Yaping
Lab of Seismic Exploration
Department of Engineering Mechanics
Tsinghua University
Beijing, 100084
P.R. China
e-mail: zyphq@mailserver.cic.tsinghua.edu.cn
-------------------------------------------------------
Date: Wed, 26 May 1999 14:11:13 -0700 (PDT)
From: Jon Dym
Subject: Job Opening
Hi Craig,
Interesting that I'm sending this to Yale (responding to an MGNet posting sent
to USC) and neither of us are at either of these places. I'm now working for
Unigraphics Solutions, a CAD/CAM/CAE company in Southern Cal. The CAE guys
here have some positions open for which MG background is very suitable. I
would be obliged if you could post this in the next MGNet issue. If you have
any students, or know of someone who may have students who qualify, feel free
to forward (they're looking for someone to start yesterday....).
Thanks,
Jon Dym
Editor's Note: Ahem... I was at Yale when this arrived. I have to keep
------------- up my miles/kilometers per hour average :-)
Industrial Position - Southern California
The opportunities at Unigraphics Solutions are "in-finite". The CAE group is
working on automatic finite-element mesh generation for real life large scale
industrial problems.
Candidates interested in participating in the development should be of
practical bent, with strong programming background in C or C++. Knowledge of
CAD geometry, topology and numerical methods is required. Also, candidates
must have experience in at least one of the following areas: free form
surface modeling, solid modeling, meshing, or some complex geometry and
topology based application. Good oral and written communication skill in
English is an absolute necessity.
Pluses:
+ Experience developing or using CAD or CAE software.
+ Knowledge or experience in applying FEA to automobile design or
manufacture (major plus).
+ Object Oriented methodology and Windows experience.
+ Experience in rigorous software development methodology.
+ Ability and desire to grow into leadership positions.
We offer an excellent salary, excellent benefits and future opportunities
based on our dramatic growth. Please send your resume and salary history to:
Dave Williams, Email: davew@ugsolutions.com
We are proud to be an equal opportunity employer.
UNIGRAPHICS SOLUTIONS
www.ugsolutions.com
-------------------------------------------------------
Date: Fri, 14 May 1999 14:17:31 GMT
From: Jens-Dominik Muller
Subject: Copper 99 paper (Muller)
Coarsening 3-D Hybrid Meshes for Multigrid Methods
Jens-Dominik Muller
Oxford University Computing Laboratory
Wolfson Building
Parks Road, Oxford, OX1 3QD, England
Abstract
An element-collapsing algorithm for hybrid meshes is presented that allows one
to generate a sequence of coarser meshes for multilevel methods given a finest
mesh. The coarser meshes consist of primitive elements such as tetrahedra,
prisms, pyramids and hexahedra. The algorithm does not triangulate the
primitives but preserves them as much as possible. Directional coarsening can
be achieved in regions of stretched meshes.
Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or access it at
------------- http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Papers/mueller.ps.gz
Jens-Dominik Mueller, OUCL, Oxford, muller@comlab.ox.ac.uk
Oxford University Computing Lab
Wolfson Building tel: 01865/273.860
Parks Road fax: 01865/273.839
Oxford, OX1 3QD
UK
-------------------------------------------------------
Date: Fri, 28 May 99 21:53:02 +0300
From: "Prof. Achi Brandt"
Subject: Copper 1999 Paper (Brandt)
General Highly Accurate Algebraic Coarsening Schemes
Achi Brandt
Department of Computer Science and Applied Mathematics
The Weizmann Institute of Science
Rehovot 76100, Israel
Abstract
General purely algebraic approaches for repeated coarsening of deterministic
or statistical field equations are presented. They apply to the equations
arising from variational as well as non-variational discretizations of
general, elliptic as well as non-elliptic, partial differential systems, on
structured or unstructured grids. They apply to many types of disordered
systems, such as those arising in composite materials, inhomogeneous ground
flows, twisted geometry discretizations and Dirac equations in disordered
gauge fields, and also to non-PDE systems, like those encountered in elastic
structures made of discrete components and in molecular mechanics. The
coarsening can be inexpensive with low accuracy, as needed for multigrid
solvers, or more expensive and highly accurate, as needed for other
applications (e.g., once-for-all derivation of macroscopic equations).
Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or access it at
------------- http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Papers/brandt2.ps.gz
-------------------------------------------------------
Date: Mon, 17 May 1999 12:22:10 -0400 (EDT)
From: Jonathan Hu
Subject: Copper Mountain 1999 Paper (Hu, Kowarschik, et al)
Cache Optimization for Structured and Unstructured Grid Multigrid
Craig C. Douglas
University of Kentucky,
325 McVey Hall - CCS,
Lexington, KY 40506-0045, USA.
douglas@ccs.uky.edu
Jonathan Hu
University of Kentucky,
Department of Mathematics,
715 Patterson Hall,
Lexington, KY 40506-0027, USA.
jhu@ms.uky.edu
Markus Kowarschik
Lehrstuhl für Systemsimulation (IMMD 10),
Institut für Informatik,
Universität Erlangen-Nürnberg,
Martensstrasse 3, D-91058 Erlangen, Germany.
kowarschik@informatik.uni-erlangen.de
Ulrich Rüde
Lehrstuhl für Systemsimulation (IMMD 10),
Institut für Informatik,
Universität Erlangen-Nürnberg,
Martensstrasse 3, D-91058 Erlangen, Germany.
ruede@informatik.uni-erlangen.de
Christian Weiss
Lehrstuhl für Rechnertechnik und Rechnerorganisation (LRR-TUM),
Institut für Informatik,
Technische Universität München,
D-80290 München, Germany.
weissc@in.tum.de
Abstract (finally)
Many current computer designs employ caches and a hierarchical memory
architecture. The speed of a code depends on how well the cache structure is
exploited. The number of cache misses provides a better measure for comparing
algorithms than the number of multiplies.
In this paper, suitable blocking strategies for both structured and
unstructured grids will be introduced. They improve the cache usage without
changing the underlying algorithm. In particular, bitwise compatibility is
guaranteed between the standard and the high performance implementations of
the algorithms. This is illustrated by comparisons for various multigrid
algorithms on a selection of different computers for problems in two and three
dimensions.
The code restructuring can yield performance improvements of factors of 2-5.
This allows the modified codes to achieve a much higher percentage of the peak
performance of the CPU than is usually observed with standard implementations.
Key words: Computer architectures, iterative algorithms, multigrid, high
performance computing, cache.
AMS Classification: 65M55, 65N55, 65F10, 68-04, 65Y99
Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or access it at
------------- http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Papers/hu-kowarschik.ps.gz
-------------------------------------------------------
Date: Thu, 20 May 1999 15:41:05 -0400 (EDT)
From: Craig Douglas
Subject: Copper 1999 Paper (Douglas, Malhotra, & Schultz)
Fast Alternating Direction Implicit Methods and Parallel Multigrid
Craig C. Douglas
University of Kentucky,
325 McVey Hall - CCS,
Lexington, KY 40506-0045, USA.
douglas@ccs.uky.edu
S. Malhotra
107 Bloomfield Avenue, Apt. 1,
Hoboken, NJ 07030, USA.
sachitm@bellatlantic.net
M. H. Schultz
Yale University,
Department of Computer Science,
P.O. Box 208285,
New Haven, CT 06520-8285, USA.
schultz-martin@cs.yale.edu
Abstract
Alternating Direction Implicit (ADI) methods have been in use for a long time
for the solution of both parabolic and elliptic partial differential
equations. In the case where good estimates of the eigenvalues of the
operator are available, the convergence of these methods can be dramatically
accelerated.
However, in the case of computation on parallel computers, the solution of the
tridiagonal system can impose an unreasonable overhead. We discuss methods to
lower the overhead imposed by the solution of the corresponding tridiagonal
systems. The proposed method has the same convergence properties as a
standard ADI method, but all of the solves run in approximately the same time
as the ``fast'' direction. Hence, this acts like a "transpose-free" method
while still maintaining the smoothing properties of ADI.
Algorithms are derived and convergence theory is provided. Numerical examples
on serial, parallel, and clusters of processors are provided showing how much
of a speed up can be gained by the new method.
Key words: multigrid, parallel computing, iterative algorithms
AMS Classification: 65N55, 65Y05, 65N15, 65F10, 65N22
Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or access it at
------------- http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Papers/douglas.ps.gz
-------------------------------------------------------
Date: Wed, 2 Jun 1999 15:13:26 -0400 (EDT)
From: Jun Zhang
Subject: Copper 1999 Paper (Zhang)
On Preconditioning Schur Complement
and Schur Complement Preconditioning
Jun Zhang
Department of Computer Science
University of Kentucky
773 Anderson Hall
Lexington, KY 40506-0046, USA
Abstract
We study two implementation strategies to utilize Schur complement technique
in multilevel recursive incomplete LU preconditioning techniques (RILUM) for
solving general sparse matrices. The first strategy constructs a RILUM to
precondition the original matrix. The second strategy solves the first Schur
complement matrix using the lower level parts of the RILUM as the
preconditioner. We discuss computational and memory costs of both strategies
and the potential effect on grid independent convergence rate of RILUM with
different implementation strategies.
Key words: Sparse matrices, Schur complement, RILUM, preconditioning
techniques
Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or access it at
------------- http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Papers/zhang.ps.gz
-------------------------------------------------------
Date: Sun, 23 May 1999 11:54:10 -0400 (EDT)
From: Jun Zhang
Subject: Three technical reports from Ge and Zhang
The following technical reports can be downloaded from
http://www.cs.uky.edu/~jzhang
If you need a hard copy, please send an e-mail request to jzhang@cs.uky.edu
Thank you!
Jun Zhang
* * * * * * * * * *
A Multilevel Dual Reordering Strategy for Robust
Incomplete LU Factorization of Indefinite Matrices
Jun Zhang
Department of Computer Science, University of Kentucky
773 Anderson Hall, Lexington, KY 40506-0046, USA
Abstract
A dual reordering strategy based on both threshold and graph reorderings is
introduced to construct robust incomplete LU (ILU) factorization of indefinite
matrices. The ILU matrix is constructed as a preconditioner for the original
matrix to be used in a preconditioned iterative scheme. The matrix is first
divided into two parts according to a threshold parameter to control diagonal
dominance. The first part with large diagonal dominance is reordered using a
graph based strategy, followed by an ILU factorization. A partial ILU
factorization is applied to the second part to yield an approximate Schur
complement matrices. The whole process is repeated on the Schur complement
matrix and continues for a few times to yield a multilevel ILU factorization.
Analyses are conducted to show how the Schur complement approach removes small
diagonal elements of indefinite matrices and how the stability of the LU
factor affects the quality of the preconditioner. Numerical results are used
to compare the new preconditioning strategy with two popular ILU
preconditioning techniques.
Key words: Reordering strategies, sparse matrices, incomplete LU
factorization, multilevel ILU preconditioner.
Technical Report 285-99, Department of Computer Science, University of
Kentucky, Lexington, KY, 1999. This research was supported in part by the
University of Kentucky Center for Computational Sciences.
* * * * * * * * * *
On Preconditioning Schur Complemenmt
and Schur Complement Preconditioning
Jun Zhang
Department of Computer Science, University of Kentucky
773 Anderson Hall, Lexington, KY 40506-0046, USA
Abstract
We study two implementation strategies to utilize Schur complement technique
in multilevel recursive incomplete LU preconditioning techniques (RILUM) for
solving general sparse matrices. The first strategy constructs a RILUM to
precondition the original matrix. The second strategy solves the first Schur
complement matrix using the lower level parts of the RILUM as the
preconditioner. We discuss computational and memory costs of both strategies
and the potential effect on grid independent convergence rate of RILUM with
different implementation strategies.
Key words: Sparse matrices, Schur complement, RILUM, preconditioning
techniques
Technical Report 287-99, Department of Computer Science, University of
Kentucky, Lexington, KY, 1999. This research was supported in part by the
University of Kentucky Center for Computational Sciences.
* * * * * * * * * *
High Accuracy Iterative Solution of Convection Diffusion
Equation with Boundary Layers on Nonuniform Grids
Lixin Ge and Jun Zhang
Department of Computer Science, University of Kentucky
773 Anderson Hall, Lexington, KY 40506-0046, USA
Abstract
A fourth order compact finite difference scheme and a multigrid method are
employed to solve the two dimensional convection diffusion equations with
boundary layers. The computational domain is first discretized on a
nonuniform (stretched) grid to resolve the boundary layers. A grid
transformation technique is used to map the nonuniform grid to a uniform one.
The fourth order compact scheme is applied to the transformed uniform grid. A
multigrid method is used to solve the resulting linear system. We show how
the grid stretching affects the computed accuracy of the solutions from the
fourth order compact scheme and how the grid stretching influences the
convergence rate of the multigrid method. Numerical experiments are used to
show that a graded mesh and a grid transformation are necessary to compute
high accuracy solutions for the convection diffusion problems with boundary
layers and discretized by the fourth order compact scheme.
Key words: convection diffusion equation, boundary layer, grid stretching,
grid transformation, multigrid method
Technical Report 288-99, Department of Computer Science, University of
Kentucky, Lexington, KY, 1999. This research was supported in part by the
University of Kentucky Center for Computational Sciences and in part by the
University of Kentucky College of Engineering.
Jun Zhang * E-mail: jzhang@cs.uky.edu
Department of Computer Science * URL:http://www.cs.uky.edu/~jzhang
University of Kentucky * Tel:(606)257-3892
773 Anderson Hall * Fax:(606)323-1971
Lexington, Kentucky 40506-0046 *
-------------------------------------------------------
Date: Mon, 3 May 1999 09:49:53 -0500
From: Zhangxin CHEN
Subject: New Book
New Book, Bifurcation Theory & its Numerical Analysis
Edited by: Zhangxin Chen, Shui-Nee Chow, and Kaitai Li
Springer-Verlag Singapore
ISBN: 981-4021-58-X
TABLE OF CONTENTS:
Peter Bates, Kening Lu, and Chongchun Zeng,
Invariant foliations of overflowing manifolds
for semiflows in Banach space
Pietro-Luciano Buono, Martin Golubitsky, and Antonio Palacios,
Heteroclinic cycles in systems with D_n symmetry
Zhangxin Chen,
Some problems in mathematical modeling and simulation
for applications of fluid flows in porous media
Natalia L. Khlopina,
Numerical experiments for a finite element approximation
of two-phase flow in porous media
Giampaolo Cicogna,
Resonant bifurcations and normal forms
Zhilan Feng,
Stability of periodic solutions in an epidemiological model
William F. Langford and Kaijun Zhan,
Hopf Bifurcations Near 0:1 Resonance
Alain Leger,
On the bifurcation diagram of the equilibrium
problem of elastic-plastic solids
Dongsheng Li and Kaitai Li,
Global bifurcation of nonlinear eigenvalue problems in cones
Mingjun Li,
Sensitive dependence on initial conditions
and topological transitivity
Yi Li,
Exact multiplicity of positive solutions of some elliptic problems
Liquan Mei and Aixiang Huang,
The coupling method of spectral method and streamline diffusion
FEM for neutron transport equations
George W. Reddien,
Applications of implicit Liapunov-Schmidt reductions
Masaharu Taniguchi,
Multiple existence and classification of
equilibrium balls in a free boundary problem
Lizhou Wang and Kaitai Li,
Existence of positive solutions of some systems of elliptic equations
Wei Wu,
Heteroclinic and Hopf points bifurcating from local singular points
Chunshan Zhao,
The asymptotic behavior of the non-autonomous sine-Gordon equation
Qingsong Zou and Jingan Lei,
Bifurcation for subdifferential operator equations
------------------------------
End of MGNet Digest
**************************