NA Digest Monday, June 8, 1992 Volume 92 : Issue 23

Today's Editor:

Cleve Moler
The MathWorks, Inc.
moler@mathworks.com

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 <clawson@math.Jpl.Nasa.Gov>
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 <dmk@dmk.com>
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 <snash@gmuvax.gmu.edu>
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 <craig@ISL.Stanford.EDU>
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 <ehg@research.att.com> 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 <GDBYRNE%ERENJ.BITNET@pucc.Princeton.EDU>
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 <WES1@SSCVX1.SSC.GOV>
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 <ISD@IBM-B.RUTHERFORD.AC.UK>
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 <mike@thrain.anu.edu.au>
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 <PNAW92@edinburgh.ac.uk>
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 <Laila.Liseth@ii.uib.no>
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 <brualdi@imafs.ima.umn.edu>
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

**************************
-------