NA Digest Tuesday, August 14, 1990 Volume 90 : Issue 28
Today's Editor: Cleve Moler
Today's Topics:
-------------------------------------------------------
From: Bob Plemmons <plemmons@deacon.mthcsc.wfu.edu>
Date: Mon, 6 Aug 90 16:13:19 EDT
Subject: Temporary Address Change for Bob Plemmons
During the academic year 90/91 I will be at
Wake Forest University (Z. Smith Reynolds Professor).
The new address is:
Robert J. Plemmons
Dept. of Mathematics and Computer Science
Box 7311
Wake Forest University
Winston-Salem, NC 27109
e-mail: plemmons@.mthcsc.wfu.edu
office phone: (919) 759-5358(5354)
home phone (919) 723-3957
Thanks,
Bob Plemmons
------------------------------
From: Saul Drobnies <drobnies%math@sdsu.edu>
Date: Mon, 6 Aug 90 19:13:42 PDT
Subject: Visiting Position at San Diego State
Title of Position: Visiting Professor
Department Name: Mathematical Sciences
Institution Address: San Diego State University
San Diego, CA. 91282-0314
Phone Numbers: (619) 5946191 & (619) 594`6176
E-mail Address: drobnies@math.sdsu.edu
Name of contact person: Professor Saul I. Drobnies
Department of Mathematical Sciences
San Diego State University
San Diego, CA. 92181-0314
Comments: Appointment at rank of Professor for 1991-92 academic
year. Seeking distinguished visitor. Teach one upper
division course plus graduate seminar. Prefer person with
research interests in differential equations, asymptotic
analysis, linear algebra, or graph theory. Send resume
to contact person.
------------------------------
From: David R. Kincaid <kincaid@cs.utexas.edu>
Date: Sun, 12 Aug 90 02:00:20 CDT
Subject: Cheney-Kincaid code in C
I have been told that someone has rewritten the Fortran codes in the
Cheney-Kincaid book (Numerical Mathematics and Computing) in
Pascal and/or C. If this is true, I would like to make them available
to others.
Please contact me at
kincaid@cs.utexas.edu
if you have information on this. Thanks.
------------------------------
From: Heinz W. Engl <K310773%AEARN.BITNET@Forsythe.Stanford.EDU>
Date: Wed, 08 Aug 90 13:32:13 EDT
Subject: New Journal: Surveys on Mathematics for Industry
New Journal:
Surveys on Mathematics fop Industry
Publisher: Springer Verlag, Wien, New York
Editorial Board:
H. Engl (Managing Editor); T. Beth, C. Cercignani, M. Deistler,
A. Fasano (representative of ECMI), A. Gilg, M. Groetschel, H. Hagen,
R. Janssen, F. Kuhnert, A. Louis, P. Markowich, H. Martens,
R. Mennicken (representative of GAMM), H. Neunzert, P. Rentrop, A. Samarskii,
A. Tayler, W. Toernig (representative of DMV), I. Troch (representative of
OEMG), H. Wacker.
The main goal of this journal is to bridge the gap between university and
industry by
- The presentation of mathematical methods relevant for industry
- The exposition of industrial problems which are of interest
to mathematicians.
To achieve this goal, the journal publishes
- Surveys on new mathematical techniques
- Surveys on established mathematical techniques with a new
range of applications
- Surveys on industrial problems for which appropriate mathematical models
or methods are not yet available
- Articles comparing mathematical models or methods for particular
industrrial problems
- Articles describing mathematical modelling techniques
- Broad historical surveys
- Articles of general interest about the use of mathematics in industry
- Occasional book reviews and reports about conferences in the field of
industrial mathematics.
Normally, papers will be solicited by a member of the editorial board;
however, papers may also be submitted to the managing editor. All papers
will be refereed.
Editorial Office:
Prof. Dr. Heinz Engl
Institut fuer Mathematik
Johannes Kepler Universitaet
A-4040 Linz, Austria
phone: +43-(0)732 2468870
fax: +43-(0)732 246810, attn.: Prof. Engl
e-mail(bitnet): k310773@aearn
e-mail(na-net): na.engl@na-net.stanford.edu
Subscription Information:
Springer Verlag
POB 367
A-1011 Wien
Austria.
The first issue will appear in early 1991.
------------------------------
From: John Depillis <jdp@ucrmath.ucr.edu>
Date: Wed, 8 Aug 90 08:51:05 PDT
Subject: Householder Conference: An Overview
With thanks to Randy Bramley for the use of his notes and to
Gene Golub and Bob Plemmons for their observations.
The Event:
On June 18-22, 1990, the Eleventh Householder Symposium on
Numerical Algebra took place at the Nya Hotel Tylosand, located
on the west coast of Sweden near the town of Halmstad. There
were about one hundred and fifty persons in attendance. There
were attendees from various countries including, for the first
time, a large contingent from the Soviet Union and Eastern
Europe.
First Impressions:
On Sunday, the 17th, some participants arrived in order to
register and settle in early. Friends old and new made contact.
Groups were seen in search of local restaurants to share some
time and their first meal in Halmstad. Recovery time was
required by some victims of price-shock.
In certain respects, the casual visitor might conclude that the
charming Nya Tylosand was not so much a hotel as it was an intel-
igence test. This impression was due, in part, to the numbering
system of the rooms (for which no algorithm seems to exist) and
to the helpful signs "HISS" and "RUM" ("elevators" and "room".)
The Formal Talks:
There were so many interesting lectures (often in conflict) that
it is impossible to give more than a fleeting impression of the
meeting. The rich and stimulating meeting showed the growing use
of numerical linear algebra in a widening range of applications.
Also, it was of interest to see so many young persons involved in
the subject, evidencing a stronger interest than ever.
The Conference opened on Monday, 18 June, with welcoming remarks
from Ake Bjorck. Gene Golub extended his greetings and also
noted that among the original organizers of the Householder
Conferences only Dave Young and Gene himself have been present at
them all. Velvel Kahan was also in attendance at the very first
meeting at Gatlinburg.
The opening talk by Jim Demmel described some of his work on
LAPACK, a matrix library being designed for accuracy and
portability, qualities which are not easy to realize on CRAYs!
(See "The Informal Talks" section for a CRAY test you can do at
home.) Using component-wise relative error, (as opposed to the
more standard relative norm bounds), Jim was able to achieve
tighter error bounds in the solution of linear systems,
generalized SVD, the symmetric eigenvalue problem, etc.
The morning continued with Velvel Kahan speaking on symmetric
rank-1 perturbed diagonal's system, along with some observations
on CRAY's arithmetic weaknesses and failings.
K. Veselic gave more details of the accuracy of one-sided Jacobi
as applied to L' L = A: this was in contrast to use of the QR
algorithm. The error bounds were element-wise as described by
Demmel, and were convincing enough to make Jacobi the method of
choice for the LAPACK project.
Nick Higham talked about fast matrix multiplication, describing
recent developments using Strassen's algorithm. In the "usual"
martrix multiplication, we have an n**2 error term. In
Strassen's method, the error exponent p for n**p ranges from
2-3.85 and the numerical error can be 10-100 times greater than
that for standard multiplication. It was noted that IBM and CRAY
use Strassen's method in their libraries. R. Grimes pointed out
that Strassen's method requires more memory and so can not be
implemented in the BLAS-3's as a default. Kahan noted that BLAS-
3's perform well with scaling but Strassen's method does not.
Mario Arioli gave examples where a QR factorization used to solve
nonsingular systems gives much larger errors (up to 15 orders of
magnitude) than LU. His explanation was an error analysis that
accounts for the sparsity pattern of each Qi (again c.f. Demmel's
talk). Normally QR perturbs all of the upper triangle of A, not
just the nonzero parts. He also showed that QR cannot capture
Skeel's error bounds for LU, but yields the classical condition
number. Stewart pointed out that this was not a feature of QR,
but rather of the implementation of QR --- that is, each example
that Mario gave could have had a small relative error simply by
permuting the rows of the given matrix.
Two talks dealt primarily with condition number estimation. Chris
Bischof discussed combining his incremental condition number
(ICE) estimator with restricted column pivoting to obtain a rank
revealing QR factorization that could run well on high-
performance machines. Then Bob Plemmons introduced ACE and ALE,
fast adaptive condition number estimators for signal processing
applications. This application requires maintaining the Cholesky
factor of a matrix which is being updated/downdated by one row on
every time step. The method also applies to any low rank update
of a matrix and so might be used for quasi-Newton methods (which
have a rank-1 or -2 update on each step).
New approaches for the iterative solution of nonsymmetric systems
were presented in three interesting plenary talks. First, Freund
proposed that use of his quasi-minimal residuals (QMR) algorithm
can be extended beyond the complex symmetric case. Unfortunately
QMR can still fail in the same cases as when incurable breakdowns
occur in the Lanczos algorithm.
Secondly, Van der Vorst presented the stabilized CGS scheme, and
suggested that it might be combined with QMR. The basic idea is
that in bi-conjugate gradients, a polynomial Pi is created such
that Pi(A) reduces r0 to ri, and Pi(A^T) reduces r'0 to r'i. CGS
uses (ri, r'j) = (Pj(A)Pi(A)r0, r'0) to get a recursion for ri
without needing r_i. However, the polynomial Pi is effectively
squared, so when Pi has problems with conditioning, its square
suffers even worse effects. Van der Vorst also noted that
Pi(A)r0 is orthogonal to $Q(i-1)(A^T) r'0 for any polynomial Q of
degree less than i. He recommends using Qi(A) = (I- alphai A)*
(I- alpha1 A) (I- alpha0 A), with the parameters alphai chosen to
minimize the norm of ri. The resulting CGSTAB algorithm has a
smooth convergence of residual norms, has better performance than
GMRES(k) or CGS, and has never broken down on device simulation
problems.
Thirdly, Lothar Reichel presented a hybrid method using
Richardson's method and GMRES(k). He proposed using GMRES(k) to
find the parameters for a Richardson iteration, with the
parameters ordered using Leja points. His approach for finding
the parameters seems to differ from the one used by Saylor,
Smolarski (the pronunciation of which may be left to the reader's
discretion), Saad and Elman because instead of using the
underlying Arnoldi iteration, he directly uses the GMRES residual
polynomial. He proposed that the new method has better
properties because the GMRES residual polynomial captures the
$\epsilon$-pseudo spectrum (defined by Trefethen) while the
Arnoldi approach does not.
O. Widlund showed results from SESAM, a large finite element code
for elasticity problems. He proposed eliminating interior nodes,
that is, explicitly forming the Schur complement. He then tested
three block preconditioners, based on using a coarse grid, the
edge space of left-over unknowns, and the vertex space of left-
over unknowns, respectively. The last choice provided the best
preconditioner by far. Kahan asked about nonlinear problems,
where structural failure usually begins in the local elements
(which are eliminated by Widlund's scheme) and then work their
way up to larger structures. Widlund had no answer for that,
having tested only linear problems. Roger Grimes said that for
3D problems this approach was too expensive, since what is left
over consists of planes, not lines. Tony Chan bounced around in
his chair at this comment, but was not able to answer it until
the next break. I (R. Bramley) did not hear his response, but
apparently Tony feels that it is a practical approach even for
3D problems, and has written something up on it.
Yeremin also proposed explicitly forming the Schur complement for
elasticity problems in spite of the additional storage required
and the large number of operations required. He suggested using
an incomplete BSSOR-CG scheme as preconditioner-solver pair,
unlike his previous work which used a complete BSSOR
preconditioner. The incomplete BSSOR is based on using an
incomplete Cholesky factorization of the diagonal blocks of the
matrix, rather than the complete factorization.
In the following talk, Kolotilina discussed using direct
approximations to the inverse of the matrix as preconditioners,
and presented a way of obtaining a symmetric approximation when
$A$ is symmetric and positive definite. When applied to
elasticity problems, the preconditioned system has a larger
condition number than the unpreconditioned system! However,
significant improvement over BSSOR-CG and IBSSOR-CG is achieved
when the Schur complement is used instead.
It is impractical to give a full report on all of the excellent
talks at the conference. We only mention Bunse-Gertner's talk on
computing the eigendecomposition of unitary matrices, which
showed that by applying the QR algorithm to the Schur parameter
form of a unitary matrix one can take advantage of many more
zeros that occur for free during the bulge-chasing sequence.
Van Huffel gave an excellent overview and introduction to total
least squares, providing motivation, basic analysis, and
guidelines of when total least squares should and should not be
used (the alternative is regular least squares). Per-A ke Wedin
gave an overview of perturbational analysis of linear and
nonlinear least squares problems, and advocated using iterative
refinement for such problems. His analysis showed that
essentially the dependence on the square of the condition number
can be removed using this approach.
Of course, much of the action at the Householder Conference took
place in special sessions, not at the plenary sessions. One
especially notable special session dealt with row projection
methods. A. Dax of the Hydrological Service in Israel discussed
applying Kaczmarz methods for solving l_infty, l_1, and linear
programming problems by a regularization approach. M. Neumann
refined his analysis of the convergence of chaotic iterations,
and Mario Arioli presented further results for Cimmino's method
applied to sparse nonsingular systems.
The Householder Prize Lecture:
Householder Prize, based on the quality of the PhD thesis in
numerical analysis/algebra, was awarded jointly to both Alan
Edelman (PhD, MIT: Nick Trefethen supervisor) and to Maria Beth
Ong (PhD, Univ of Washington: Loyce Adams supervisor.)
At the Thursday night banquet, Pete Stewart formally announced
the names of the winners, noting the exceptionally high quality
of the submissions which rendered the committee's choice
pleasantly difficult.
On Friday, 22 June, Alan Edelman presented his results on
Eigenvalues and Condition Numbers of Random Matrices. It was
generally agreed that Alan's results were beautiful and his
presentation was delivered with clarity and style.
Sad to say, Mary Beth Ong, the co-winner, was not allowed to
leave Seattle to present her results in Sweden due to some sort
of visa problem with the US Immigration Service. It was rumored
that the INS thought her Green's function should also have a
green card (what else?) but in all fairness, this report is
totally unsubstantiated.
Informal Talks:
Besides the formally scheduled talks during the day, evening
sessions were spontaneously organized and very well attended.
One of the informal talks was given by Velvel Kahan immediately
after the Thursday banquet. This talk actually served as the
post-banquet entertainment. Velvel's lively and provocative
discourse provided more detail about CRAY's arithmetic. The
audience was invited to confirm an odd anomaly found in CRAY's
arithmetic, viz., that the CRAY computation of both
(62.0*63.0)/62.0) and (63.0*63.0)/63.0), return values, neither
of which is an integer.
Hans Schneider made some remarks in support of ILAC, the Inter-
national Linear Algebra Society. Speaking to professionals whose
very business it is to understand the notions of "less than" and
"greater than," Hans noted that the annual dues for this
organization amounted to less than the cost of two Swedish beers.
Wednesday Afternoon Excursion:
The afternoon of Wednesday 20 June was set aside for an excursion
to a wild-life refuge on an island off the Coast. Many
cheerfully piled into the Skandia buses to the harbor where a
roofless ferry awaited us. Only after we reached the island, did
the rains begin. Just a drizzle. Nothing that could result in
any diminution of The Experience. However, those of us who
failed to bring either an umbrella or raincoat were left in a
state of soggy contrition after our return trip on the roofless
ferry. At least the bus was covered!
Miscellaneous
To those interested (and there were many), Cleve Moler gave dem-
onstrations of a preliminary version of a forthcoming proposed
addition to MATLAB, the handling and graphing of sparse matrices.
The 22nd of June marks the year's longest day in Sweden. (This
event is increasingly being noted in other countries.) Folk-
dancing around special poles took place to mark this happy
phenomenon (Midsummer's Day.). But this time is apparently a
time to stay at home and celebrate as the ghost-town emptiness of
the streets would indicate.
This meant that I was to leave Halmstad at a train station that
had no passengers, no station master, and for a while there, I
was convinced that there would be no train, either. But the
train finally did appear, like a soundless Flying Dutchman with
only one or two passengers (strangers, like me, to the Swedish
ways.) In a word, a remarkably good meeting for which the
organizers are to be congratulated. Special thanks are due to
Ake Bjorck for all his attention and consideration!
Next meeting:
Gene Golub and Tony Chan will be organizing the next Householder
(Gatlinburg) Conference which will take place at the University
of California's Lake Arrowhead Conference Center in southern
California in June 1993. Watch this space for further details!
John de Pillis
U. of Calif., Riverside
8 August 1990
------------------------------
End of NA Digest
**************************
-------