Subject: NA-NET distribution message

From: [email-masked]
Date: Tue, 14 Aug 90 06:38:17 PDT

NA Digest   Tuesday, August 14, 1990   Volume 90 : Issue 28

Today's Editor: Cleve Moler

Today's Topics:

     Temporary Address Change for Bob Plemmons
     Visiting Position at San Diego State
     Cheney-Kincaid code in C
     New Journal: Surveys on Mathematics for Industry
     Householder Conference: An Overview

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

From: Bob Plemmons <[email-masked]>
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 <[email-masked]>
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: [email-masked]

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 <[email-masked]>
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

[email-masked]

if you have information on this. Thanks.

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

From: Heinz W. Engl <[email-masked]>
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): [email-masked]

Subscription Information:
Springer Verlag
POB 367
A-1011 Wien
Austria.

The first issue will appear in early 1991.

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

From: John Depillis <[email-masked]>
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
**************************
-------