NA Digest Sunday, August 11, 1991 Volume 91 : Issue 32

Today's Editor: Cleve Moler

Today's Topics:

Submissions for NA Digest:

Mail to

Information about NA-NET:

Mail to


From: Jens Lorenz <>
Date: Mon, 5 Aug 91 14:19:59 MDT
Subject: Correction to Report on Dundee Conference

I 'd like to thank Andy Wathen for his high-standard remark
about my talk. However, the announced title of my lecture was:
Computation of Invariant Manifolds.
No wonder I did not quite reach the slightly compressible
Navier-Stokes equations.

Jens Lorenz


From: Peter Alfeld <>
Date: Tue, 6 Aug 91 12:57:46 MDT
Subject: Square Roots of Matrices

John Halleck of the local Computer Center is interested in
literature on properties of the square roots of matrices, particularly
on how they relate to the Cholesky decomposition and its cousin, the
LDLT decomposition. If you know of any literature, could you please
send a reference to (John Halleck)

or (peter Alfeld).

Thanks a lot!

Peter Alfeld
Department of Mathematics
University of Utah
Salt Lake City, UT 84112
801-581-6842 or 801-581-6851


Date: Fri, 9 Aug 91 15:00 EDT
Subject: SIAM Manuscript Submittal

TO: All SIAM Book and Journal Authors
FROM: SIAM Publications
RE: Manuscript Submittal

SIAM has a new mailbox for submission of final manuscripts:

Please use this address for submission of all FINAL manuscripts for books
and journals. It will allow us to process your manuscript more efficiently.

Please continue to use: for messages.


From: Cal Ribbens <>
Date: Thu, 8 Aug 91 16:14:07 EDT
Subject: Comments on Parallel Programming

A student and I are surveying recent work on tools for
parallel programming, especially in the domains of
numerical analysis and scientific computation. Since
many of the readers of na-net have had extensive experience
with parallel computing in the last decade, I am soliciting
comments on the following question:

How do you generally "think about" (i.e., design, plan,
outline) your parallel algorithms?

Some possibilities of the kind of thing I mean:

- as a graph (data-dependency, control flow, etc.)

- as some other type of abstraction (monitors, actors, CSP,
tuple-space, ...)

- in very problem specific terms (matrix rows/columns/blocks,
spatial subdomains, particles, intervals, paths, ...)

- in terms of a "traditional" programming language of some kind
("parallel psueducode", if you will)

Do you generally think more in problem specific terms or in terms
of abstractions which apply across many application areas?

If you work in more than one application area, does your
approach to thinking about parallelism change from area to area?
Or from architecture to architecture?

Are there tools that you have found particularly helpful,
and in fact, that have influenced the way you think
about parallelism?

Please send any comments you may have directly to me. Thanks!
If the response justifies it, we will summarize what we learn
in a future note.

Cal Ribbens
Dept. of Computer Science
Virginia Tech
Blacksburg, VA


From: John R. Gilbert <>
Date: Fri, 9 Aug 1991 17:45:15 PDT
Subject: IMA Workshop on Graph Theory and Sparse Matrix Computation

IMA Workshop on
Sparse Matrix Computation:
Graph Theory Issues and Algorithms
October 14-18, 1991
Minneapolis, Minnesota

As part of its Special Year in Applied Linear Algebra, the Institute for
Mathematics and its Applications at the Univeristy of Minnesota is sponsoring
a workshop on graph theory and sparse matrix computation. All interested
researchers are invited to attend the workshop; attendance is open, with no
fees or registration charge. A preliminary list of speakers follows. More
information is available from the workshop organizers or from the special
year organizer, Richard Brualdi (Wisconsin).


Alan George (Waterloo;
John Gilbert (Xerox PARC;
Joseph Liu (York;


Attempts to solve efficiently very large sparse systems
of equations have spawned a multitude of important and
interesting problems. Some of these problems are numerical,
some are combinatorial, some can be phrased in terms of
questions about graphs, and some are "core computer science"
questions, involving the design and implementation of good
(and sometimes provably optimal) data structures. The purpose
of this workshop is to bring together people who work in
sparse matrix computation with those who conduct research in
applied graph theory and graph algorithms.

Speakers (preliminary; this list may be incomplete):

Ajit Agrawal (Brown).
Provably good elimination orderings using nested dissection.
Cleve Ashcraft (Boeing).
The aggregate/element model for column-based parallel sparse Cholesky.
Eleanor Chu (Waterloo).
A robust ICCG algorithm for sparse symmetric positive definite systems.
Stan Eisenstat (Yale).
Structural representations of sparse Schur complements.
Steve Kratzer (Supercomputing Research Center).
Massively parallel sparse matrix computation.
Gary Miller (Carnegie-Mellon).
A geometric approach to graph separators with applications to
sparse matrix computation.
Esmond Ng (Oak Ridge).
On symbolic Cholesky factorization.
Barry Peyton (Oak Ridge).
On finding miminum-diameter clique trees.
Paul Plassman (Argonne).
An efficient parallel iterative solver for large sparse linear systems.
Alex Pothen (Penn State).
Predicting the structure of sparse orthogonal factors.
Don Rose (Duke).
Numerical analysis of circuit simulation: The culture of CAzM.
Rob Schreiber (RIACS).
Are sparse matrices poisonous to highly parallel machines?
Pravin Vaidya (Illinois).
Constructing provably good cheap preconditioners for certain symmetric
positive definite matrices.
Steve Vavasis (Cornell).
Nested dissection for sparse nullspace bases.


Date: Tue, 6 AUG 91 09:55 N
Subject: Research Posts and Collaborations at CRS4, Sardinia

Research posts and collaborations at CRS4.

An international centre for Advanced Studies, Research and Development
(CRS4) is being newly established in Cagliari (Sardinia, Italy).
The operational structure of CRS4 is based on Groups, which are
considered the elements of research continuity, and on Projects,
devoted to specific application areas, including co-operations with
the industry.
Among the Groups, the Applied Mathematics team takes up a very
strategic position.
We foresee that the Applied Mathematics team will have up to about 4
senior members and 6 graduate students by year end 1991 and about a
total of 15 people by year end 1993.
A search committee (J. Argyris, F. Brezzi, C. Cercignani, G.H. Golub,
M.H. Schultz, S. Seatzu) of which I am the coordinator has just been
appointed to select an optimal candidate to head the above team.
The head of the Applied Mathematics team has a double task:
(1) to ensure a proper support to CRS4's research activities with the
most advanced mathematical techniques stressing numerical methods,
computer simulations and parallelism;
(2) to develop relevant projects of industrial mathematics with the
contribution of mathematicians outside CRS4 and of researchers
from advanced industrial establishments.
The candidate is expected to work in Cagliari.
CRS4 will have a program of visitors and various kinds of external
collaboration, but at this time I am not able to be precise about when
this program will start .
If you are personally interested in learning more about CRS4 and the
position of manager or visitor or external collaborator of the Applied
Mathematics team, please send me your curriculum vitae.

Sebastiano Seatzu
Dipartimento di Matematica
viale Merello 92
09123 Cagliari
Electronic mail:,


From: David Walker <walker@rios2.EPM.ORNL.GOV>
Date: Tue, 6 Aug 91 07:57:25 -0400
Subject: Position Available at Oak Ridge




A postdoctoral research position is available at Oak Ridge National
Laboratory in parallel algorithms for linear algebra. The research will
focus initially on the development of a library of portable, efficient
routines for performing dense linear algebra computations on MIMD distributed
memory concurrent computers. A subsequent goal will be the development of
software for sparse matrix computations on these types of computer.
The practical use of the library software will be demonstrated by using it
to build large-scale applications that are transparently portable between
different concurrent computers.

The research to be conducted is part of a program involving Jack Dongarra
and David Walker of Oak Ridge National Laboratory, Jack Demmel of University
of California at Berkeley, Michael Heath of University of Illinois, and
Danny Sorensen of Rice University.

The position requires an in-depth knowledge of linear algebra algorithms
for scientific computation, and practical experience with MIMD distributed
memory concurrent computers. The appointment will be for two years, preferably
beginning October 1, 1991, or shortly thereafter. Benefits of the position
include a competitive salary, travel opportunities, access to state-of-the-art
computational facilities, and collaborative research opportunities in a very
active research program.

Inquiries should be directed to:

David W. Walker
Bldg. 6012 / MS-6367
P. O. Box 2008
Oak Ridge National Laboratory
Oak Ridge, TN 37831-6367


From: Francis Sullivan <>
Date: Fri, 9 Aug 91 14:14:19 EDT
Subject: Request for Papers, Supercomputer Applications


Special issue on non-numeric applications

Joanne Martin has asked me to serve as guest editor for a special issue of
the International Journal of Supercomputer Applications, to appear in the
Fall of 1992. The topic is non-numeric applications of supercomputing.
Since supercomputing has always been closely associated with numerical
applications, some explanation of this choice of topic is in order. We take
a very broad interpretation of the term ``non-numeric applications.'' We're
interested in applications drawing on the methods of discrete mathematics,
geometry, and probability theory, rather than the traditional tools of
numerical computation.

Applications of discrete mathematics, geometry, and probability arise
naturally both in mathematical modeling and in methods for improving
performance of parallel computers. One usually associates mathematical
modeling with approximations of differential equations obtained from
conservation laws. Relevant numerical methods include numerical linear
algebra, numerical optimization, fitting methods, and others. However, even
numerical solution of pde's makes use of discrete mathematics and geometry.
Free Lagrangian methods, for example, are based in part on triangulation. In
3-d, this is a non-trivial geometric computation.

The increasing power and ease-of-use of computers makes direct simulations
from first principles more attractive for some physical models. Most such
simulations rely on a combination of datastructures, probability theory, and
geometry both for performing the calculation and for interpreting the results.
In addition, some of the computationally demanding parts of modeling have to
do with understanding and visualizing numerical solutions. Here again, useful
techniques come from computational geometry and related subjects.

For parallel computers, performance of codes is often determined by
the efficiency of the data motion rather than by the choice of numerical
method. In the case of shared-memory architectures, queueing models
are needed. For local-memory machines, the implementation of all-to-all
communication is crucial. Many data motion algorithms are based on the
clever use of ideas originating in probability theory. There are also many
applications in which the answer to a problem actually is given by a specific
ordering of the data. The ordering is usually determined by a requirement to
traverse a graph. Devising good algorithms for this requires understanding of
graphs and their properties.

Some specific areas of interest are:

Application of discrete mathematics, geometry, and probability
in visualization, modeling, and direct simulation of physical phenomena.

Probabilistic approaches to deterministic problems. Average behavior
of implementations and performance of randomizing algorithms.

Graph theory, especially as it applies to data communication in parallel
machines and, conversely, studies of the relation between data communication
methods and the performance of graph traversal algorithms.

Performance benchmarks for data motion, e.g. performing an all-to-all
move, sorting, determination of global max/min, determination of spanning
trees, determination of connected components.

Submissions should be sent to:

Francis Sullivan
Computing and Applied Mathematics Laboratory
National Institute of Standards and Technology
Gaithersburg, Maryland 20899

Telephone: (301) 975 2732
Fax: (301) 963 9137

In order to meet production schedules, manuscripts MUST be received by
December, 15, 1991.


Date: Mon, 5 Aug 91 09:41 EDT
Subject: Contents, SIAM J. Applied Mathematics

Table of Contents
SIAM Journal on Applied Mathematics
Vol. 51, No. 6, December 1991

Gas Phase Decomposition by the Lindemann Mechanism
S. L. Cole and J. W. Wilder

Dynamics of Director Fields
John K. Hunter and Ralph Saxton

Stress-Assisted Diffusion: A Free Boundary Problem
Robert W. Cox

Time-Dependent Dispersion of Small Particles in Rectangular Conduits
Roberto Mauri and Shimon Haber

Solution to the Scattering of Electromagnetic Waves For a Dielectric
A. K. Gautesen, R. W. Ziolkowski, and R. R. McLeod

Elastodynamic Completeness Relations for Scattered Wavefields
David E. Budreck and James H. Rose

On Exponential Asymptotics for Nonseparable Wave Equations I: Complex
Geometrical Optics and Connection
Richard E. Meyer

On Exponential Asymptotics for Nonseparable Wave Equations II: EBK
Richard E. Meyer

A New Solution for the Nonlinear Diffusion-Convection Equation
Arieh Pistiner, Michael Shapiro, and Hillel Rubin

On the Averaging Method in Nearly Time-Periodic Advection-Diffusion Problems
M. S. Krol

Standard Form and a Method of Averaging for Stronglly Nonlinear Oscillatory
Dispersive Travelling Waves
Richard Haberman

A Computational Quasi-Reversibility Method for Cauchy Problems for Laplace's
Michael V. Klibanov and Fadil Santosa

Identification of Scattering Media from Reflected Flows
Hans Babovsky

Effects of Measurement Precision and Finite Numbers of Electrodes on Linear
Impedance Imaging Algorithms
David Isaacson and Margaret Cheney

Transient and Stationary Distributions for Fluid Queues and Input Processes
with a Density
Alain Simonian and Jorma Virtamo

Heavy Traffic Analysis of the Sojourn Time in Tandem Queues with Overtaking
C. Knessl and J. A. Morrison

Shape Analysis and Reduction of the Morphological Basis for Digital Moving
Average Filters
Edward R. Dougherty and Eugene J. Kraus

Minimal Representation for Translation-Invariant Set Mapping by Mathematical
Gerald Jean Francis Banon and Junior Barrera

For futher information conact Vickie Kearn, Publisher, SIAM, 3600 University
City Science Center, Philadelphia, PA 19104-2688. Phone: (215) 382-9800.


From: Richard Brualdi <>
Date: Wed, 7 Aug 91 06:59:59 cdt
Subject: Linear Algebra and Its Applications

Contents, LAA Volume 157, November 1, 1991

SPECIAL ISSUE: Algebraic Linear Algebra

Special Editors: Robert M. Guralnick,
William H. Gustafson, and Lawrence S. Levy

William H. Gustafson (Lubbock, Texas)
Modules and Matrices

Raymond Heitmann (Austin, Texas) and Roger Wiegand (Lincoln, Nebraska)
Direct Sums of Ideals

Lawrence S. Levy (Madison, Wisconsin)
Direct-Sum Cancellation of Submodule Systems

Wojciech Kucharz (Honolulu, Hawaii)
Simultaneous Diagonalization of an Algebraic Family of Matrices

Robert M. Guralnick (Los Angeles, California)
Similarity of Matrices Over Commutative Rings

David Chillag (Haifa, Israel)
Nonnegative Matrices, Brauer Characters, Normal Subsets,
and Powers of Representation Modules

Donald G. James (University Park, Pennsylvania)
Generators for Orthogonal Groups of Unimodular Lattices

Bostwick F. Wyman (Columbus, Ohio), Michael K. Sain (Notre Dame, Indiana),
Giuseppe Conte (Genoa, Italy), and Anna Maria Perdon (Padua, Italy)
Poles and Zeros of Matrices of Rational Functions

James Brewer and Lee Klingler (Boca Raton, Florida)
The Ring of Integer-Valued Polynomials of a Semi-local Principal-Ideal Domain

James Brewer and Lee Klingler (Boca Raton, Florida)
On the Pole-Shifting Problem for Non-commutative Rings

Dennis R. Estes (Los Angeles, California)
Factorization in Hereditary Orders

William A. Adkins (Baton Rouge, Louisiana)
Normal Matrices over Hermitian Discrete Valuation Rings

James T. Campbell (Memphis, Tennessee) and Elizabeth C. Trouy (Tuscon, Arizona)
When Are Two Elements of GL(2, Z) Similar?

Surjeet Singh and Hassan Al-Zaid (Safat, Kuwait)
On a Canonical Form for Recurring Sequences

K. R. Fuller (Iowa City, Iowa), W. K. Nicholson (Calgary, Alberta,
Canada), and J. F. Watters (Leicester, England)
Universally Reflexive Algebras

Carlos A. Berenstein and Daniele C. Struppa (Fairfax, Virginia)
Recent Improvements in the Complexity of the Effective Nullstellensatz

L. Le Bruyn and M. Van den Bergh (Wilrijk, Belgium)
Algebraic Properties of Linear Cellular Automata

Author Index

Special Issues in Progress

1. Proceedings of the Auburn 1990 Matrix Theory Conference; special
editors are David Carlson and Frank Uhlig. To appear as Volumes 162-163,
February 1992.

2. Proceedings of the Sixth Haifa Conference on Matrix Theory; special
editors are A. Berman, M. Goldberg, and D. Hershkowitz. Submission
deadline: October 1, 1990. Details provided with the conference

3. Proceedings of the International Workshop on Linear Models,
Experimental Designs and Related Matrix Theory, (August 6-8, 1990,
Tampere, Finland); special editors are Jerzy K. Baksalary and George
Styan. Submission deadline: October 31, 1990. Details provided with the
conference announcement.

4. Proceedings of the Second NIU Conference on Linear Algebra, Numerical
Linear Algebra and Applications, (May 3-5, 1991, Northern Illinois
University, DeKalb, Illinois); special editors are Biswa Datta, Robert
Plemmons, and Roger Horn. Submission de adline: August 31, 1991. Details
provided with the conference announcement.

5. Numerical Linear Algebra Methods in Control, Signals and Systems;
special editors are Gregory Ammar, Volker Mehrmann, Nancy K. Nichols,
and Paul Van Dooren. Submission deadline: July 31, 1992. Details in
Volume 157, November 1, 1991.

6. Proceedings of the Workshop on Computational Linear Algebra in
Algebraic and Related Problems (July 27-August 1, 1992, Essen, Germany);
special editors are R. M. Guralnick and G. O. Michler. Submission
deadline: October 30, 1992. Details provided with the workshop

7. Proceedings of the Second Conference of the International Linear
Algebra Society at Lisbon; special editors are J. A. Dias Da Silva, Chi-
Kwong Li, and Graciano de Oliveira. Submission deadline: October 30,
1992. Details provided with the conferenc e announcement.

Special issues are available to individuals at a reduced rate. For
further information, please contact Bob Biederman, Journals Customer
Service, Elsevier Science Publishing Co., 655 Avenue of the Americas,
New York, NY 10010; Tel. 212-633-3955; Fax 2 12-633-3990.

Special Issue of Linear Algebra and Its Applications:

Numerical Linear Algebra Methods in Control, Signals and Systems

In recent years there has been an increased cooperation between
mathematicians and engineers concerning the development and analysis of
fast and reliable numerical linear algebra methods in the areas of
signal processing, system theory and control the ory. This special issue
of Linear Algebra and Its Applications is devoted to research papers in
these areas, particularly the numerical solution of

-- structured eigenvalue problems,
-- structured linear systems,
-- inverse eigenvalue problems (like pole placement or stabilization),
-- generalized eigenvalue problems,
-- special matrix decompositions,
-- linear quadratic control problems,
-- Riccati, Lyapunov, Sylvester or Stein equations.

Deadline for submission is July 31, 1992.

Special editors for the special issue are:

Gregory Ammar, Volker Mehrmann,
Department of Mathematical Sciences, Fakultaet fuer Mathematik,
Northern Illinois University, Universitaet Bielefeld,
De Kalb, Illinois 60115-2888, USA Postfach 8640, D-4800 Bielefeld 1, FRG

Nancy K. Nichols, Paul Van Dooren,
Dept. of Mathematics, Department of Electrical and
University of Reading, Computer Engineering,
Whiteknights Park, University of Illinois
GB-Reading, RG6 2AX, Great Britain at Urbana-Champaign, 1101 West Springfield Av.,
Urbana, Illinois 61801, USA

Papers may be submitted to any of these editors.


End of NA Digest