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