NA Digest Monday, October 27, 1991 Volume 91 : Issue 43

Today's Editor: Cleve Moler

Today's Topics:

Submissions for NA Digest:

Mail to na.digest@na-net.ornl.gov.

Mail to na.help@na-net.ornl.gov.

-------------------------------------------------------

From: Alan Edelman <edelman@math.berkeley.edu>
Date: Fri, 25 Oct 91 16:07:34 PDT
Subject: Complete Pivoting Conjecture Rumors

Those Complete Pivoting Conjecture Rumors

It has been brought to my attention that erroneous rumors concerning
the complete pivoting conjecture have been circulating. The bottom
line is that Wilkinson's conjecture is false, here is the story:

Wilkinson's complete pivoting conjecture states that the maximum
growth factor for Gaussian elimination on a real n by n matrix
is equal to n. In [1] Gould publishes a 13 by 13 matrix that
appears to have growth factor bigger than 13, but in fact
in exact arithmetic the growth factor is smaller than 8.

This is a wonderful example of the difference between floating
point arithmetic and exact arithmetic which some of you may wish
to play with and mention in your classrooms.

I received a letter from Day and Peterson who suggested I try
to scale rows to obtain a growth factor of bigger than 13. Their
suggestion turned out to be overkill. I discovered that by modifying
Gould's matrix so that the entry in the 11th row and 10th column
is .9999999 exactly, a growth factor bigger than 13 was obtained.
I also found a way to modify Gould's 16 by 16 matrix so that a growth
factor bigger than 18 was obtained in exact arithmetic.

Mathematica and Maple programs were developed with the aid
of Miles Ohlrich and Su-Lin Wu (students at Berkeley) to verify
these growth factors. I have made these programs available
by anonymous ftp from math.berkeley.edu in the directory
pub/edelman. You can run these programs both with the (11,10)th
entry modified or unmodified.

Thus, the conjecture is false, Gould's matrix as published
is nearly but not exactly a counterexample, and still nobody
knows much about the maximum growth factors under complete
pivoting.

References
[1] N. Gould, SIAM J. Matrix Anal. Appl., 12 (1991), 354--361.
[2] Edelman: Note to Editor, SIAM J. Matrix Anal. Appl., 12 ( July 1991)

Alan Edelman
Department of Mathematics
UC Berkeley

------------------------------

From: David G. Hough <dgh@validgh.com>
Date: Sun, 20 Oct 91 20:30:10 PDT
Subject: Who's Got the Best Arithmetic?

Ever since it was first formulated in 1977, what became IEEE 754
arithmetic has been variously criticized for being too complicated, or
not exact enough, or too limited in range, in comparison with various
alternative proposals.

Underlying each of the criticisms are alternative paradigms of various
sorts, some simplifying error analysis by reducing the applicable
domain, others simplifying error analysis but at uncertain cost, and
others introducing interesting new ways of thinking about arithmetic
errors.

Skilled analysts can construct plausible examples that seem to make one
approach look better than another. What's harder to answer are
questions like

* Which methods have the widest domains over which they provide
reasonable results at acceptable costs?

* Which methods produce satisfactory results for realistic problems at
least cost, given comparable investments in hardware, compilers,
libraries, and algorithms?

Such questions seem refractory at first but perhaps that's overly
pessimistic. Although ten years ago some people began to believe that
by 1991 anybody who wanted could, with almost no experience, design his
own custom semiconductors, it hasn't worked out quite that way. What
has changed, however, is that it is now relatively easy for graduate
students and professors to obtain GCC, an optimizing C compiler of adequate
quality, with public source code, that can be readily extended to new
language features and ported at least to most common workstation
platforms. And compilers for other languages are in the works.

This means that it is possible for advocates of almost any language
extension to try implementing it and its supporting libraries, code
their algorithms, and determine the domain of applicability
themselves.

So one could try implementing two flavors of arithmetic entirely in
fixed-point software, or even in AND and OR instructions, then
comparing their performance empirically at least over the domain of
small to medium-size realistic applications.

Naturally every arithmetic scheme will run faster with appropriate
hardware support than without, and it's well known that in pipelined
high performance systems, which nowadays include systems costing less
than \$5000, performance on scientific problems is affected as much by
memory bandwidth issues as by raw floating-point hardware speed. Even
so, gross differences in attainable hardware performance should be
evident from software simulations.

Computer instruction set architecture has been revolutionized by
widespread application of quantitative empirical methods. It seems
appropriate to apply similar methods to arithmetic systems
themselves. There seems to be room for many thesis projects here.

------------------------------

From: Daniel B. Szyld <szyld@euclid.math.temple.edu>
Date: Thu, 24 Oct 91 14:54:21 EDT
Subject: Special Sessions at AMS Meetings

Organize a Special Session!

On Oct 12-13 an AMS regional meeting took place in Philadelphia.
Within the meeting, we had a Special Session on Numerical
Linear Algebra, with 16 speakers and a good attendance.
I am writing this note to let people know that Special Sessions
within the AMS meetings (regional, national or international)
are easier to organize than a whole meeting (this should be obvious).
Therefore I would encourage members of the Numerical Analysis
community to organize such sessions, since this creates added
activities in different geographical locations, often with very
good results.
I am aware of two other occasions where special sessions of this
kind were organized, once in Tennessee, on Sparse matrices, and
once in Kansas. I attended the latter and it was very successful.
Check the Notices for upcoming meetings near you! (but you do not need
to be based near the meeting location to organize a session).
Special Sessions are proposed about a year before the meeting.

Daniel B Szyld
Temple University

------------------------------

From: Tony Chan <chan@math.ucla.edu>
Date: Thu, 24 Oct 91 14:50:08 -0700
Subject: Magnus Hestenes Memorial Symposium

THIRD ANNOUNCEMENT
MAGNUS HESTENES MEMORIAL SYMPOSIUM
November 23, 1991
Department of Mathematics
University of California, Los Angeles

The UCLA Department of Mathematics will host a memorial symposium in
honor of Professor Magnus Hestenes on Saturday, November 23, 1991. Professor
Hestenes passed away on May 31, 1991. He had been a faculty member in the
UCLA's Math Dept. since 1947 until his retirement in 1973. At this symposium,
the speakers will pay both personal and technical tribute to Professor
Hestenes. He contributed to many areas of mathematics, including conjugate
gradient methods, calculus of variations, optimization theory and optimal
control. He also played an active role in leading UCLA's Department of
Mathematics and the National Bureau of Standards Institute for Numerical
Analysis at UCLA.

There will be no registration fees. A banquet will be organized the same
evening at the UCLA Faculty Center (cost \$32.00 per person all inclusive).
825-9036; e-mail: babette@math.ucla.edu. Please let us know if you
have any relevant memorabilia that you can bring.

Please register asap and reserve seats for the banquet before November 8, 1991.
Please make checks payable to: Mathematics Department Welfare Fund.

The conference will be held at MS 4000 in the Math Science Building,
beginning at 9:00 AM.

"The Impact of the Conjugate Gradient Method"
Gene Golub, Stanford Univ.
"Augmented Lagrangian in Computational Physics and Mechanics"
Roland Glowinski, Univ. of Houston,
"The influence of the Chicago School of Bliss and Hestenes
on Numerical Optimization", Richard Tapia, Rice Univ.
"Magnus Hestenes's contributions to optimal control theory"
Len Berkovitz, Purdue Univ./UCLA.
"NBS, INA and Magnus Hestenes", John Todd, Caltech.
"Recollectioins of the role of Magnus Hestenes in the UCLA
Math Dept from 1950 to 1964", Angus Taylor, UC Berkeley
"Early Days at UCLA and INA", Marvin Stein, U. of Minnesota.
"Father and Son as Mathematicians",
David Hestenes, U. of Arizona,
Ivie Stein, Jr. (U. of Toledo)/John Gregory (So. Ill. U.)
"Some Reflections on Working with Magnus Hestenes"
Ed Landesman, UC Santa Cruz
Banquet speech: "Reflections", John Hestenes, NSF/Drexel U.

------------------------------

From: Anthony Skjellum <tony@helios.llnl.gov>
Date: Fri, 25 Oct 91 09:37:57 PDT
Subject: SIAM Activity Group on Supercomputing

The SIAM Activity Group on Supercomputing publishes a quarterly
Newsletter including but not limited to short articles on benchmarks
and standards, conference announcements and calls for papers, reviews
of past conferences, and job openings (particularly for new graduates

Volume 4, #2 (October) will be on display at the SIAM booth at
Supercomputing '91... to get the Newsletter, you must belong to SIAM
and join the SIAG/SC as well.

To contribute to the Newsletter (highly encouraged for everyone), send
e-mail to A. Skjellum:
tony@lll-crg.llnl.gov or tony@helios.llnl.gov. I prefer Mac
RTF or ASCII text. FAX is also acceptable: (510)423-2993.

The deadline for upcoming issues is as follows:
Volume 4, #3,4: December 10, 1991.
Volume 5, #1: March 10, 1992.

- Tony Skjellum

------------------------------

From: Richard C. Allen <rcallen@cs.sandia.gov>
Date: Sat, 26 Oct 91 10:03:51 MDT
Subject: Student Volunteers for SUPERCOMPUTING '91

There are still openings for Student Volunteers at SUPERCOMPUTING '91.
Some information and an application form are included below. You may
respond by e-mail; send a copy of your student identification card by
regular mail.

Student volunteers are needed for the SUPERCOMPUTING '91 Conference to
be held in Albuquerque, New Mexico in November, 1991. The '91
volunteer program will reward you with an enriching conference
positions do not require any special experience, but it is important
that volunteers be reliable and conscientious.

Volunteer positions will require from 20 to 30 hours of duty during
the conference from Sunday, November 17, to Friday, November 22.

Every effort will be made to design your duty schedule so that you can
attend some conference activities of your choice, including technical
sessions, minisymposia, workshops, etc. The SUPERCOMPUTING '91
registration fee (which includes a lunch and the banquet) will be
waived and hotel accommodations (shared with up to three students of
the same sex) will be provided for student volunteers.

by completing the enclosed application form and returning it as soon as
possible. Applicants will be accepted as they are received.

rcallen@cs.sandia.gov.

------------------------------

From: Diethelm Wuertz <wuertz@ips.id.ethz.ch>
Date: Wed, 23 Oct 91 14:51:25 +0000
Subject: Parallel Problem Solving from Nature

CALL FOR PARTICIPATION
International Workshop on
PARALLEL PROBLEM SOLVING FROM NATURE
- Applications in Statistics and Economics -
December 9-10, 1991, ETH Zurich

OBJECTIVE OF THE WORKSHOP

Information processing systems for optimization and forecasting are
mathematical and computational challenges. Only new algorithmic concepts
paired with numerically intensive computing are able to solve the
problems in many fields of statistics and economics. These new methods
lead to decision support systems which will become more and more
invaluable tools in finding the best solutions to statistical and
economical problems. The range and variety of the underlying information
processing technologies go far beyond traditional techniques. The new
aids to making better decisions are based on techniques as diverse as
parallel algorithms, neural networks and optimization concepts like
simulated annealing and genetic algorithms. In addition the rapid
evolution of these algorithmic concepts goes hand in hand with recent
developments in parallel computer hardware creating a favorable synergy.

The Workshop seeks to bring together those working towards applications
of these new information processing systems and those concerned with
regularities in statistical and economic data. A number of experts in
relevant, closely-related domains will also attend. On both Workshop
days there will be a series of tutorial presentations by invited speakers.
In addition there will be a number of contributed presentations on work
in progress.

ORGANISATION

The Workshop is scientifically supported by the DOSES programme
(Development of Statistical Expert Systems) of EUROSTAT (Statistical
Office of the European Communities) and organized by the IPS
(Interdisciplinary Project Center for Supercomputing) at ETH Zurich.

o IPS, ETH Zurich
o Konjunkturforschungsstelle an der ETH Zurich
o MasPar Distributor AG, Zurich
o PAR, Schweizerische Informatiker Gesellschaft
o Parsytec GmbH, Aachen and TNT AG Bern
o QT optec AG, Zug
o Schweizerischer Bankverein, Basel

PROGRAM COMMITTEE

J. Frain, Central Bank of Ireland, Dublin
K. Kirchmayr, Schweizerischer Bankverein, Basel
F. Murtagh, Munotec Systems, Dublin and Munich
P. van Nypelseer, DOSES, eurostat, Luxemburg
U. Reimer, Rentenanstalt Zurich
M.M. Richter, DFKI, Kaiserslautern, Germany
W. Roth, Konjunkturforschungsstelle ETH Zurich
D. Wurtz, IPS, ETH Zurich
H.G. Zimmermann, Siemens AG, Munchen

SPEAKERS

J. Bernasconi, ABB Corporate Research, Baden
A. Colin, Citicorp Inv. Bank, London
F. Fogelman Soulie, MIMETICS, Chatenay Malabry
J. Frain, Central Bank of Ireland, Dublin
H. Horner, Universitaet Heidelberg
H. Muehlenbein, GMD, St. Augustin - Bonn
F. Murtagh, Munotec Systems Ltd., Dublin
P.M. Perremans, DOSES - EUROSTAT, Luxemburg
M.B. Priestley, UMIST Manchester
R. Rohwer, CSTR University of Edinburgh
C. Schaefer, Rowland Inst. of Science, Cambridge, USA
P. Treleaven, University College, London
A. Varfis, Joint Research Center, Ispra
H-M. Wallmeier, IBM Scientific Center, Heidelberg
D. Weers, Aspen Intellect AG, Zug
A. S. Weigend, Stanford University, Stanford
D. Wuertz, IPS, ETH Zurich
H.G. Zimmermann, Siemens AG, Munich

Dr. Diethelm Wuertz
IPS ETH-Zurich
ETH Zentrum, CLU B3
CH-8092 ZURICH

phone: 0041-1-256.5567
fax no: 0041-1-252.0185
e-mail: wuertz@ips.ethz.ch

------------------------------

From: E. Gallopoulos <stratis@csrd.uiuc.edu>
Date: Wed, 23 Oct 91 21:35:07 CDT
Subject: ACM Conference on Supercomputing

CALL FOR PAPERS
6th ACM International Conference on Supercomputing
July 19-23, 1992
Hyatt Crystal City Hotel, Washington D.C

General Chair
Ken Kennedy, Center for Research on Parallel Comp., Rice University

Program Chair
C. D. Polychronopoulos, CSRD, University of Illinois

The 6th ACM International Conference on Supercomputing
is soliciting papers on significant new research results
and experience in the development and use of supercomputing systems.
Topics of interest include, but are not limited to
parallel and high-performance computer architectures,
parallelizing compilers and programming environments,
operating systems and performance evaluation,
large-scale applications and algorithms,
technologies, new experimental and commercial systems.

Program Committee

F. Allen (IBM, T.J. Watson), R. Allen (Kubota Pacific),
Arvind (MIT), J. L. Baer (U. Washington), D. Bailey (NASA Ames),
J. C. Browne (U. Texas-Austin), R. Cytron (Washington U.),
D. DeGroot (Texas Inst.), R. Esser (KFA), E. Gallopoulos (CSRD),
J. R. Gurd (U. Manchester), F. Hossfeld (KFA), E. Houstis (Purdue U.),
W. Jalby (U. Rennes), Y. Jegou (INRIA-IRISA), C. Koelbel (Rice U.),
J. McGraw (LLNL), Y. Muraoka (Waseda U.), A. Nicolau (UC Irvine),
T. Papatheodorou (U. Patras), J. Riganati (SRC), A. J. Smith (UC Berkeley),
H. Terada (Osaka U.), A. Veidenbaum (CSRD), S. Wallach (Convex).

Local Arrangements Chair: Duncan Buell, SRC
Finance Chair: A. Veidenbaum, CSRD
Publicity Chair: E. Gallopoulos. CSRD

Paper Submissions

Authors should submit five copies of the full manuscript
to the program chairman or the appropriate regional chairman
as follows:

NORTH & SOUTH AMERICA EUROPE & AFRICA JAPAN & FAR EAST
Constantine Polychronopoulos Harry Wijshoff Toshitugu Yuba
Program Chairman Region Chairman Region Chairman
CSRD Dept. Computer Sci. Electrotechnical Lab.
University of Illinois Utrecht University 1-1-4 Umezono, Tsukuba
104 S. Wright St. Padualaan 14 Ibaraki 305
Urbana, Illinois 61801, USA 3584 CH Utrecht Japan
(cdp@csrd.uiuc.edu) The Netherlands (yuba@etl.go.jp)
(harryw@cs.ruu.nl)

DEADLINE for Submissions is December 10, 1991.
Authors will be notified about the outcome of
the paper selection by March 7, 1992.

Proposals for Tutorials

The conference also solicits proposals for half and full-day
tutorials which will be offered before and after the conference.
Proposals for tutorials on topics of wide interest to the
supercomputing and parallel processing community should be
submitted by December 10, 1991 to:

George Paul
Tutorials Chairman
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598, USA
(gp1@watson.ibm.com)

Tutorial topics of particular interest include, but are not
limited to large-scale applications, numeric and symbolic
computing, applications of supercomputing to engineering,
physical and biological sciences, programming environments
and visualization tools, architectures, compilers and languages
and operating systems.

Conference Announcement

The conference announcement is available in ASCII and
PostScript via anonymous ftp from sp2.csrd.uiuc.edu
(128.174.162.51) in pub/ics-an and pub/ics-an.ps;
or write to the publicity chairman: stratis@csrd.uiuc.edu.

Program Chairman, CSRD, University of Illinois,
104 S. Wright St., Urbana, Illinois 61801-2932, USA.
Tel. (217) 333-6773. FAX (217) 244-1351. E-mail: cdp@csrd.uiuc.edu.

------------------------------

From: SIAM Publications Department <SIAMPUBS@WILMA.WHARTON.UPENN.EDU>
Date: Mon, 21 Oct 91 11:00 EDT

SIAM Journal on Scientific and Statistical Computing

January 1992 Volume 13, Number 1

CONTENTS

Special Issue Devoted to the Copper Mountain Conference on Iterative Methods,
April 1--6, 1990

Introduction

A Comparison of Adaptive Chebyshev and Least Squares Polynomial Preconditioning
for Hermitian Positive Definite Linear Systems
Steven F. Ashby, Thomas A. Manteuffel, and James S. Otto

Preconditioned Iterative Methods for Homotopy Curve Tracking
Colin Desa, Kashmira M. Irani, Calvin J. Ribbens, Layne T. Watson, and Homer F.
Walker

A Block Projection Method for Sparse Matrices
Mario Arioli, Iain S. Duff, Joseph Noailles, and Daniel Ruiz

Sparse Approximation for Solving Integral Equations with Oscillatory Kernels
Francis X. Canning

A Highly Parallel Multigrid-Like Method for the Solution of the Euler Equations
Ray S. Tuminaro

Fast Parallel Iterative Solution of Poisson's and the Biharmonic Equations on
Irregular Regions
A. Mayo and A. Greenbaum

Compact Multigrid
Victor Pan and John Reif

Parallel Performance of Domain-Decomposed Preconditioned Krylov Methods for PDEs
with Locally Uniform Refinement
William D. Gropp and David E. Keyes

Optimal Multilevel Iterative Methods for Adaptive Grids
William F. Mitchell

Row Projection Methods for Large Nonsymmetric Linear Systems
R. Bramley and A. Sameh

A set of New Mapping and Coloring Heuristics for Distributed-Memory Parallel
Processors
Claude Pommerell, Marco Annaratone and Wolfgang Fichtner

Multilevel Filtering Preconditioners: Extensions to More General Elliptic
Problems
Charles H. Tong, Tony F. Chan, and C.C. Jay Kuo

Domain Decomposition Algorithms for Indefinite Elliptic Problems
Xiao-Chuan Cai and Olof B. Widlund

Preconditioning Second-Order Elliptic Operators: Experiment and Theory
Wayne Joubert, Thomas Manteuffel, Seymour Parter, and Sze-Ping Wong

Fast Iterative Solution of Carrier Continuity Equations for Three-Dimensional
Device
Simulation
O. Heinreichsberger, S. Selberherr, M. Stiftinger, and K.P. Traar

The Hierarchical Basis Extrapolation Method
U. Rude

Fourier Analysis of Incomplete Factorization Preconditioners for
Three-Dimensional
Anisotropic Problems
June M. Donato and Tony F. Chan

Line Iterative Methods for Cyclically Reduced Discrete Convection-Diffusion
Problems
Howard C. Elman and Gene H. Golub

An Optimal Domain Decomposition Preconditioner for the Finite Element Solution
of
Linear Elasticity Problems
Barry F. Smith

An Unconventional Domain Decomposition Method for an Efficient Parallel
Solution of Large-scale Finite Element Systems
Charbel Farhat and Francois-Xavier Roux

Domain Decomposition Methods for Problems with Partial Refinement
James H. Bramble, Richard E. Ewing, Rossen R. Parashkevov, and Joseph E. Pasciak

A Large, Sparse, and Indefinite Generalized Eigenvalue Problem from Fluid
Mechanics
Hans D. Mittlemann, Cindy C. Law, Daniel F. Jankowski, and G. Paul Neitzel

Conjugate Gradient-Type Methods for Linear Systems with Complex Symmetric
Coefficient Matrices
Roland W. Freund

------------------------------

End of NA Digest

**************************
-------