Subject: NA Digest, V. 92, # 23 NA Digest Monday, June 8, 1992 Volume 92 : Issue 23 Today's Editor: Cleve Moler The MathWorks, Inc. moler@mathworks.com Today's Topics: Lawson & Hanson Least Squares Code Re: Did Roundoff Cause Patriot Failure? Who was Raphson? (an answer) Overlaying Postscript Figures with LaTeX Fragments SISSC Table of Contents Online New Book by Bryne and Schiesser Two New Books CERFACS Annual Report by FTP CTAC93 Meeting in Australia Parallel Numerical Analysis Workshop `92: PROGRAM Positions at University of Bergen Linear Algebra and its Applications Submissions for NA Digest: Mail to na.digest@na-net.ornl.gov. Information about NA-NET: Mail to na.help@na-net.ornl.gov. ------------------------------------------------------- From: Chuck Lawson Date: Tue, 2 Jun 92 12:01:53 PDT Subject: Lawson & Hanson Least Squares Code Answering the query by Ferguson in the NA Digest re a source for the code from the Lawson & Hanson book, Solving Least Squares Problems. This code was available from IMSL from the publication of the book (1974) up to a couple of years ago. At that time IMSL decided to quit handling distribution of ACM TOMS algorithms and miscellaneous software packages. C. Abaci, Inc., (Phone 919-832-4847) has taken on much of this distribution service. In particular the Lawson & Hanson code, called LLSQ, is available from C. Abaci, Inc., for $75 plus shipping/media charge. -- C. Lawson clawson@math.jpl.nasa.gov ------------------------------ From: David Keaton Date: Wed, 3 Jun 92 10:34 MDT Subject: Re: Did Roundoff Cause Patriot Failure? It appears that several members of the Numerical Analysis mailing list are confused. Would you please post the following message there for me? I have absolutely no connection with the government and am not a distribution point for the Patriot missile bug report. I am just a citizen letting people know how to get ahold of it. Please contact the GAO to receive your report, not me. As far as I know, there is no way to get it by email. David Keaton dmk@dmk.com ------------------------------ From: Stephen Nash Date: 5 Jun 92 15:03:00 EST Subject: Who was Raphson? (an answer) Who was Raphson? (an answer) Many thanks to those of you who responded with suggestions. The popular answer, by the way, is that "Raphson was Newton's programmer." (This answer has been attributed to Doug Wilde of Stanford University.) You can decide for yourself the accuracy of this statement. Newton studied a number of methods for finding roots of polynomials. (Many of these results were not published by Newton, but are now available in [N]. Whiteside, the editor, has provided detailed tables of contents and footnotes. I have found these volumes to be a remarkable resource.) In late 1664 (?) Newton examined existing algorithms due to Viete and Oughtred [N, v. 1]. (These are linearly convergent methods that find the root one digit at a time; for details see [G, p. 66].) In early 1665 (?) Newton discovered the secant method [N, v. 1]. The derivation appears to be based on geometric reasoning, although Newton does not include a diagram. In June 1669 (?) in a manuscript entitled "De Analysi Per Aequationes Infinitas" Newton derives his version of what is now called the Newton-Raphson method [N, v. 2]. The derivation is analytic, based on a linearization of a higher-order polynomial. Newton solves a cubic equation (y^3 - 2y - 5 = 0). A few pages later Newton uses his technique symbolically to develop a power series expansion for the root of an equation. His comments seem to suggest that he was aware of his method's quadratic convergence rate, but this result is not stated explicitly. Newton also points out that you could use a quadratic approximation and ``in that way you will gain twice as many figures each time.'' Although it appears that Newton discovered this method independently, Whiteside comments that "this method of resolving numerical equations has a long manuscript history, and its essential structure was known to the fifteenth-century Arabic mathematician al-Kasi." (Whiteside goes on to give further background information.) Joseph Raphson F.R.S. (1648-1715) published a variant of Newton's method in "Analysis Aequationum universalis ..." (1690). (I have not seen this work; the original is in the British Library, London.) Raphson had seen Newton's manuscript. The two methods are equivalent, but Raphson did not realize this. According to [B], "Newton laboriously derives a new cubic equation each time, linearizes it as though it were unique, and then solves it to find the residual for that equation; it is only at the end of the process that all these residuals are added together to solve the original equation. Raphson, on the other hand, systematically writes a `theorem' or `canon' for a general cubic equation to find the residual x to be added to any guess g. ... This can be seen as exactly the same as the modern-day procedure ... Both methods must give the same increments ... thereby proving that they are the same method, but Raphson has taken Newton's and given it a form that is at the same time more general as well as more convenient." (Another discussion of Raphson' contribution can be found in [W].) There remains the question of who generalized this method to systems of nonlinear equations. G.J. Tee speculated that this may have been done by Gauss in his "Theoria Motus Corporum Coelestium in Sectionibus Conicus Solem Ambientum" (1809). A translation of this work is available from Dover. I have not yet looked at it. [B] N. Bicanic and K.K. Johnson, "Who was '-Raphson'?" Int. J. Num. Meth. Engng. 14 (1979), pp. 148-152. [G] H.H. Goldstine, "A History of Numerical Analysis from the 16th through the 19th Century," Springer Verlag (1977). [N] Isaac Newton, "The Mathematical Papers of Isaac Newton (7 volumes)," edited by D.T. Whiteside, Cambridge University Press (1967-1976). [W] R. Wait, "The Numerical Solution of Algebraic Equations," Wiley (1979). Stephen Nash George Mason University ------------------------------ From: Craig Barratt Date: Mon, 08 Jun 92 00:39:07 -0700 Subject: Overlaying Postscript Figures with LaTeX Fragments This is somewhat outside NA-Net's scope, but many subscribers might be interested. I have written some LaTeX macros (PsFrag) that make it easy to overlay postscript figures with fragments of LaTeX. I use these macros to place nice LaTeX equations and math symbols on top of postscript figures. More precisely, the PsFrag macros allow specific pieces of postscript text in a postscript figure (included via \epsfbox or \special) to be replaced with arbitrary fragments of LaTeX. When your document is latex'ed and dvips'ed, each piece of postscript text is replaced by the LaTeX text. The postscript file might be produced, for example, by xfig, idraw, matlab, xmath, etc. Each string displayed by postscript's show operator is a candidate for replacement by LaTeX text, math symbols, equations, pictures etc. For example, you can include a matlab plot in a LaTeX document with the title, axis labels, and legend generated by LaTeX. The LaTeX fragments can be optionally rotated, scaled, and repositioned relative to the text being replaced. The LaTeX fragments automatically track the postscript text position as the scaling and offsets of the \special or \epsfbox are changed. PsFrag is available via anonymous ftp from isl.stanford.edu. After logging in, cd to the directory pub/boyd/psfrag, and set binary mode. Get the compressed tar file psfrag.tar.Z, uncompress it, and tar xvf it: uncompress psfrag.tar.Z tar xvf psfrag.tar See the files README, USAGE, INSTALL for detailed information. Note: PsFrag uses ghostscript (gs) and assumes that your dvi to ps driver is Tomas Rokicki's dvips. You will need both of these programs to use PsFrag. Craig Barratt craig@isl.stanford.edu ------------------------------ From: Eric Grosse 908-582-5828 Date: Mon, 8 Jun 92 12:50 EDT Subject: SISSC Table of Contents Online Thanks to the efforts of Bernadetta DiLisi, you can now do a keyword or author search in the table of contents of the SIAM Journal on Scientific and Statistical Computation, issues 1:1 through 13:1. For example, mail netlib@research.att.com find Petzold stiff from siam yields Automatic Selection of Methods for Solving Stiff and Nonstiff Systems of Ordinary Differential Equations Linda Petzold Pgs. 136-148 SISSC 4:1 Mar 1983 ------------------------------ From: George D. Byrne Date: Wed, 03 Jun 92 09:33:05 EDT Subject: New Book by Bryne and Schiesser We are pleased to announce the publication of the book "Recent Developments in Numerical Methods for ODEs/DAEs/PDEs," ISBN 981-02-0557-0, which was edited by George D. Byrne and William E. Schiesser. The publisher is World Scientific Publishing Company, Suite 1B, 1060 Main Street, River Edge, NJ 07661, telephone 201/487-9655, rush orders telephone 201/487-9656, and FAX 201/487-9656. The book is a collection of papers presented at the November 1990 American Institute of Chemical Engineers Annual Meeting in a session by the same name as the title. One objective of the book and of the session was to bring people active in numerical methods in contact with those who use them. The contents of the book are as follows: "An Overview of Recent Developments in Numerical Methods and Software for ODEs/DAEs/PDEs," by G. D. Byrne and W. E. Schiesser. "Experiments with an Ordinary Differential Equations Solver in the Parallel Solution of Method of Lines Problems on a Shared Memory Parallel Computer," by D. K. Kahaner, E. Ng, W. E. Schiesser, and S. Thompson. "CRAYFISHPAK: A Vectorized Fortran Package to Solve Helmholtz Equations," by R. A. Sweet. "Experiments with an Adaptive H-, R-, and P-Refinement Finite Element Method for Parabolic Systems," by J. E. Flaherty and Y. Wang. "Incomplete Block Factorization Preconditioners: An Implementation for Block Tridiagonal Systems," by D. E. Salane. "Fast Generation of Weights in Finite Difference Formulas," by Bengt Fornberg. "Numerical Methods for Boundary Value Problems in Differential-Algebraic Equations," by U. M. Ascher and L. R. Petzold. "The Solution of a Co-Polymerization Problem with VODE," by G. D. Byrne. ------------------------------ From: W. E. Schiesser Date: Wed, 3 Jun 1992 15:23:44 -0500 (CDT) Subject: Two New Books Two new books are now available from Academic Press (1) "The Numerical Method of Lines Integration of Partial Equations", W. E. Schiesser, ISBN: 0-12-624130-9 (2) "Dynamic Modeling of Transport Process Systems", C. A. Silebi and W. E. Schiesser, ISBN: 0-12-643420-4 Academic Press, Inc. 1250 Sixth Avenue San Diego, CA 92101 USA ------------------------------ From: Iain Duff Date: Thu, 04 Jun 92 09:55:08 BST Subject: CERFACS Annual Report by FTP The 1990-91 CERFACS Annual Scientific Report is available from CERFACS by anonymous ftp. In order to get this report which covers all aspects of CERFACS Scientific activity, you should do the following: 1) TYPE : ftp orion.cerfacs.fr OR ftp 138.63.200.33 2) LOGIN : anonymous 3) PASSWORD : your email address 4) Select directory: cd pub/REPORTS/Scient_rep/Cerfacs 5) Receive appropriate file: bin get PSScRep91.tar.Z 6) On your machine you must uncompress the ".Z" file and then tar the resulting tar file. Instructions for printing the resulting ps files will be found in the README_PS file. ------------------------------ From: Mike Osborne Date: Thu, 4 Jun 92 14:22:28 +1000 Subject: CTAC93 Meeting in Australia Preliminary Announcement: CTAC93 CTAC93 is the 8'th biennial Conference of the Special Interest Group in computational techniques and applications of the Applied Mathematics Division of the Australian Mathematical Society. Venue: School of Mathematical Sciences The Australian National University, Canberra, A.C.T. Dates: 5-7'th July, 1993. Organising Committee: Director: Mike Osborne (Maths, ANU) Treasurer: Steve Roberts (Maths, ANU) Secretaries: Henry Gardiner (Th. Phys., ANU), hjg105@csc.anu.edu.au Dave Singleton (Supercomputer Facility, ANU), singleton_d@laplace.anu.edu.au Dave Stewart (Maths, ANU), des@thrain.anu.edu.au Jerrard Barry (ANSTO, Chairman of CTAC) Basil Benjamin (Math, USA) Kevin Burrage (Maths, UQ) Frank De Hoog (DMS, CSIRO) Alan Easton (Maths, SIT) Clive Fletcher (Mech. Eng., SU) Bob Gingold (Supercomputer Facility, ANU) Linsey Hood (ANU and TMC) Invited Speakers: Anthony Cooper (Lausanne) Stability calculations in MHD and Plasmas. Charles Elliott (Sussex) Multiphase flow problems. David Green (ANU) Neural nets, L-systems, and complex systems applications. Andreas Griewank (Argonne) Automatic differentiation of algorithms. Steve McCormick (U.C. Denver) Multilevel projection methods. Joe Monaghan (Monash) Particle in cell methods. Workshops: It is expected that several workshops will be associated with the conference and will be held on July 8-9'th. Topics mooted include `computational techniques in MHD and Plasma research', `high level languages for distributed memory multiprocessors', and `numerical techniques in optimization'. Call for Papers: It is intended that this will be issued by November 1992. Intending speakers will be asked to make preliminary versions of their papers available for distribution at the conference. They will be notified of procedures and recommended formats. Refereed Proceedings of CTAC conferences are published. Conference Information: An information file on the Conference, `ctac93.info', is held in the ftp directory pub/CTAC3 on thrain.anu.edu.au and is available for access by anonymous ftp (log in as anonymous and use your email address as password). Sponsors: These will include: The Australian National University, The British Council, Cray Research (Australia). Expressions of interest: Anyone wishing to be sent further information on CTAC93 is requested to contact: CTAC registration email: ctac-reg@thrain.anu.edu.au School of Mathematical Sciences fax : 61+6 247 2347 Australian National University PO BOX 4 Canberra ACT 2601 Australia ------------------------------ From: Frank Plab Date: Tue, 9 Jun 92 0:32:43 WET DST Subject: Parallel Numerical Analysis Workshop `92: PROGRAM FINAL CALL FOR PARTICIPATION Second Workshop on PARALLEL NUMERICAL ANALYSIS sponsored by Edinburgh Parallel Computing Centre and Science and Engineering Research Council cosponsored by The Institute of Mathematics and its Applications 25-26 June 1992 University of Edinburgh Scotland, UK The Edinburgh Parallel Computing Centre is organizing a two day ``Workshop on Parallel Numerical Analysis'' in Edinburgh on 25 and 26 June this year for mathematicians and others interested in the numerical aspects of parallel computing. INVITED SPEAKERS: Prof D.P. Bertsekas (Department of Electrical Engineering and Computer Science, MIT, Cambridge, USA) Prof Z. Zlatev (National Environmental Research Institute, Roskilde, Denmark) Prof L.C.W.Dixon (School of Information Sciences, Hatfield Polytechnic, UK) Prof Morgan (Department of Civil Engineering, University of Swansea, UK) WORKSHOP FEE (incl. lunches): \pounds 20 The Edinburgh Parallel Computing Centre (EPCC) is a multi-disciplinary institution engaged in research into and commercial development of parallel computing. It is home to a wide range of parallel computing equipment, including: a 16K processor Connection Machine CM-200, a Meiko Computing Surface with more than 400 T800 transputers; the UK Grand Challenge machine, which contains 64 i860/T800 hybrid nodes; and 64x64 AMT DAP. EPCC has a full-time staff of over 35, and a large number of associates in computer science, physical and mathematical sciences. For an electronic registration form and a copy of the preliminary program, please contact: PNAW92 c/o Frank Plab Edinburgh Parallel Computing Centre James Clerk Maxwell Building University of Edinburgh Mayfield Road Edinburgh EH9 3JZ Phone: 031-650 5818/5042 (UK), +44-31-650 5818/5042 (international) Fax: 031-650 6555 (UK), +44-31-650 6555 (international) E-mail: PNAW92@ed.ac.uk ------------------------------ From: Petter Bjorstad Date: Thu, 4 Jun 1992 09:41:11 +0200 Subject: Positions at University of Bergen POSITIONS AVAILABLE AT THE UNIVERSITY OF BERGEN UNIFOB, University of Bergen has 5 vacant positions at Para//ab - Laboratory for parallel computing MASSIVELY PARALLEL COMPUTING Para//ab was established in 1988 and represents the centre of effort of research in and application of parallel computing at the University of Bergen. Para//ab is operated by the Department of Informatics, and the laboratory is recognised as one of the leading laboratories in Europe in information technology. Para//ab now wishes to increase its activities within supercomputing, and announces the following vacant positions: - 2 Senior Scientists/Post Doctorate - 2 Stipendiate/Doctorate - 1 Scientist The positions are organised under the UNIFOB foundation. Those accepted for the positions will take part in work funded by the Norwegian research councils NTNF and NAVF together with industrial partners to convert applications to parallel architectures and contribute to algorithm development. The accepted candidates will also be expected to contribute with active support to external users of the laboratory's equipment. The Doctoral candidates will take part in para//ab projects as part of their compulsory activities. Qualifications: SENIOR SCIENTIST/POST DOC. must have Norwegian or other foreign doctoral degree within the natural sciences. The applicants must be able to document skills and experience with the use of advanced computers in scientific computation. The first position will involve a responsibility for system applications for the laboratory's parallel computers, and active involvement in research projects. The second position will be mainly involved with the laboratory's industrial project "Massively parallel algorithms for reservoir simulation" STIPENDIATE must be qualified for a doctoral programme at the Department of Informatics, University of Bergen. The student shall carry out his/her studies in problem areas within parallel computation. SCIENTIST must have qualifications equivalent to Cand. Scient./Siv.ing. (Master of Science) and documented experience and competence in the use of advanced computers. The working area will be application development for massively parallel computers, external user support and project activities where effective use of parallel computers is in focus. The three scientist positions are available for a period of three years. The stipendiate positions are for 4 years. Further details of the positions can be obtained from Professor Petter Bjorstad, Dept. of Informatics, tel. +47 5 54 41 71. Applications, including details of educations and earlier experience, together with references and certificates, should be sent to: The University of Bergen, Personell Dept., N-5020 Bergen, by 15. June 1992. Scientific works should be sent direct to: Dept. of Informatics, High Technology Centre, N-5020 Bergen by the same date. ------------------------------ From: Richard A. Brualdi Date: Fri, 5 Jun 92 12:26:09 CDT Subject: Linear Algebra and its Applications Below are the contents of Volume 172 of LAA. The contents of LAA beginning with Volume 150 as well as information on the current special issues of LAA are available from the ILAS Information center. They can be obtained as follows: Send an email message to listserv@technion.bitnet (or listserv@technion.technion.ac.il) with the commands in the mail body of the message: get LAA 91-92 get LAA SPECIAL The files will then be sent to you as an email message. The files can also be obtained by anonymous FTP. LAA Contents Volume 172, July 15, 1992 (Proceedings of the NIU Conference) David Carlson (San Diego, California), Daniel Hershkowitz, and Dafna Shasha (Haifa, Israel) Block Diagonal Semistability Factors and Lyapunov Semistability of Block Triangular Matrices 1 Y. P. Hong and C.-T. Pan (DeKalb, Illinois) A Lower Bound for the Smallest Singular Value 27 Kenneth D. Clark (Research Triangle Park, North Carolina) Decomposition of Hessenberg DAE Systems to State Space Form 33 Marcin Paprzycki (Odessa, Texas) Comparisons of Gaussian Elimination Algorithms on a Cray Y-MP 57 Shmuel Friedland (Chicago, Illinois) Lower Bounds for the First Eigenvalue of Certain *iM-Matrices Associated With Graphs 71 Richard E. Faulkenberry (North Dartmouth, Massachusetts) The Continuous Kernel of a Nonsquare Rational Matrix Function 85 Jean H. Bevis and Frank J. Hall (Atlanta, Georgia) Nested Range Conditions for *iL*iU Factorizations of Integer Matrices 97 Daniel L. Boley (Minneapolis, Minnesota), Tong J. Lee, and Franklin T. Luk (Ithaca, New York) The Lanczos Algorithm and Hankel Matrix Factorization 109 Leonid Gurvits (New York, New York), Leiba Rodman (Williamsburg, Virginia), and Tamir Shalom (New York, New York) Controllability and Completion of Partial Upper Triangular Matrices Over Rings 135 Richard A. Brualdi and Geum-Sug Hwang (Madison, Wisconsin) Generalized Transitive Tournaments and Doubly Stochastic Matrices 151 James Nagy (Raleigh, North Carolina) and Robert J. Plemmons (Winston-Salem, North Carolina) An Inverse Factorization Algorithm for Linear Prediction 169 S. L. Chung, F. B. Hanson, and H. H. Xu (Chicago, Illinois) Parallel Stochastic Dynamic Programming: Finite Element Methods 197 D. Calvetti (Hoboken, New Jersey) and L. Reichel (Kent, Ohio) A Chebychev-Vandermonde Solver 219 James R. Bunch and Ricardo D. Fierro (La Jolla, California) A Constant-False-Alarm-Rate Algorithm 231 Thomas J. Laffey and Eleanor Meehan (Dublin, Ireland) An Extension of a Factorization Theorem of Wedderburn to Matrix Rings 243 Richard A. Brualdi and Hyung Chan Jung (Madison, Wisconsin) Maximum and Minimum Jump Number of Posets From Matrices 261 D. Y. Hu (Lexington, Kentucky) and L. Reichel (Kent, Ohio) Krylov-Subspace Methods for the Sylvester Equation 283 G. S. Ammar (DeKalb, Illinois), W. B. Gragg (Monterey, California), and L. Reichel (Kent, Ohio) Downdating of Szego@a3 Polynomials and Data-Fitting Applications 315 Roger A. Horn (Baltimore, Maryland) and Roy Mathias (Williamsburg, Virginia) Block-Matrix Generalizations of Schur's Basic Theorems on Hadamard Products 337 P. Amodio and L. Brugnano (Bari, Italy) Parallel Factorizations and Parallel Solvers for Tridiagonal Linear Systems 347 Author Index 365 ------------------------------ End of NA Digest ************************** -------