**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 <plemmons@deacon.mthcsc.wfu.edu>

Date: Mon, 6 Aug 90 16:13:19 EDT

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

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

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

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

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

**************************

-------