From na-net@patience.stanford.edu Tue Aug 14 10:47:08 1990 Received: from sparky.EPM.ORNL.GOV by CS.UTK.EDU with SMTP (5.61++/2.5s-UTK) id AA01933; Tue, 14 Aug 90 10:45:52 -0400 Received: from msr.epm.ornl.gov by sparky.EPM.ORNL.GOV (4.1/1.34) id AA01710; Tue, 14 Aug 90 09:46:52 EST Received: from beauty.Stanford.EDU by msr.epm.ornl.gov (5.61/1.34) id AA10921; Tue, 14 Aug 90 10:45:57 -0400 Received: from patience.Stanford.EDU by beauty.Stanford.EDU (4.0/inc-1.5) id AA17622; Tue, 14 Aug 90 07:40:11 PDT Received: by patience.Stanford.EDU (4.0/inc-1.5) id AA03577; Tue, 14 Aug 90 06:38:17 PDT Date: Tue, 14 Aug 90 06:38:17 PDT From: na-net@patience.stanford.edu Message-Id: <9008141338.AA03577@patience.Stanford.EDU> Return-Path: Subject: NA-NET distribution message Maint-Path: maintainer@na-net.stanford.edu To: na-net@patience.stanford.edu Reply-To: na-net@patience.stanford.edu Comment: requests, comments or problems to nanet@na-net.stanford.edu Comment: submissions to na@na-net.stanford.edu Status: RO 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 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 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 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 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 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 ************************** -------