NA Digest Sunday, May 9, 1993 Volume 93 : Issue 19

Today's Editor:

Cleve Moler
The MathWorks, Inc.

Submissions for NA Digest:

Mail to

Information about NA-NET:

Mail to


From: Alan Edelman <>
Date: Sun, 2 May 93 22:53:40 PDT
Subject: Third Annual Large Dense Linear Algebra Survey


Once again I wish to ask about the state of the art of large dense
linear algebra applications. As usual, large means n > 10,000.
I am expecting this year's survey to be low-key in that computing
power has not increased significantly since a year ago, and I have
not heard of any new applications areas that have opened up in
the past year. (Am I misinformed?) Please send me your latest large
dense matrix information.

Previous surveys may be found in

Survey #1 SIGNUM Newsletter, 26 (October 1991), 6--12.
Survey #2 Inter. J. Supercomputing Appl., to appear this summer.

or by anonymous ftp from in pub/Alan_Edelman.


From: Walter Mascarenhas <>
Date: Tue, 4 May 93 18:07:36 EST
Subject: C++ vs. FORTRAN


Two weeks ago I posted a note in the na-digest asking people's impressions
about C++ for numerical analysis and how it compares with FORTRAN.

Unfortunately, there was a problem with the mailing system here and
I only got a couple of replies. Now my mail is back and I am getting
several messages asking for the results of my survey. Therefore, I
decided to post this note asking the people who tried to send me
a message in that week and didn't get through to try it again.
I also would like to hear more from people against C++.

Sorry for having to post this again,

Walter Mascarenhas.


From: Jie Shen <>
Date: Wed, 5 May 93 10:59:37 -0400
Subject: Block Tridiagonal Solver

I am looking for an efficient algorithm/software to solve the following

symmetric positive definite block tridiagonal system:

F X + D X + F X =G , i=1,2,...,n.
i-1 i-1 i i i i+1 i

where F and D are n-by-n symmetric tridiagonal matrices, F = F =0;
i i 0 n
X and G are vectors of order n. In addition, F and D are
i i i j
commutative (for all i,j).
It seems that the system can be solved in O(n log n) operations by
using a special cyclic reduction algorithm. Does anyone know a public

domain software and/or other algorithm which can solve the system in
O(n log n) operations ?

Jie Shen (
Department of Mathematics
Penn State University


From: Nick Trefethen <>
Date: Thu, 6 May 93 10:36:16 -0400
Subject: Classic Papers in Numerical Analysis


NA-Netters may be interested to hear of my experiences this spring teaching a
seminar with the above title to a dozen Cornell graduate students (three of
whom were actually post-docs or faculty). Comp. Sci. 722 met once a week for
two hours, and in the course of the semester we read thirteen papers:

1. Cooley & Tukey (1965) the Fast Fourier Transform
2. Courant, Friedrichs & Lewy (1928) finite difference methods for PDE
3. Householder (1958) QR factorization of matrices
4. Curtiss & Hirschfelder (1952) stiffness of ODEs; BD formulas
5. de Boor (1972) calculations with B-splines
6. Courant (1943) finite element methods for PDE
7. Golub & Kahan (1965) the singular value decomposition
8. Brandt (1977) multigrid algorithms
9. Hestenes & Stiefel (1952) the conjugate gradient iteration
10. Fletcher & Powell (1963) optimization via quasi-Newton updates
11. Wanner, Hairer & Norsett (1978) order stars and applications to ODE
12. Karmarkar (1984) interior pt. methods for linear prog.
13. Greengard & Rokhlin (1987) multipole methods for particles

Most weeks, one or two related readings were also assigned, typically from a
recent textbook or survey article. For example, along with the Fletcher &
Powell paper we read an extract from the 1983 text by Dennis & Schnabel.

Our weekly meetings followed a regular format. First, this week's Historian
distributed a handout containing information he/she had obtained about the
historical context of the paper, including biographical information about the
author(s) and a plot of citations as a function of time. Next, the
Mathematician gave a presentation of some of the central ideas of the paper.
Third and fourth, two Experimentalists reported the results of Matlab, C, or
Fortran experiments conducted to illustrate some of the properties of the
algorithm under discussion. Finally, the Professor added a few remarks.

To me and at least some of the students, this course provided a satisfying
vision of the broad scope of numerical analysis and a sense of excitement at
what a diversity of beautiful and powerful ideas have been invented in this
field. The thirteen papers were selected partly for their variety; they touch
upon nearly all the main problems of numerical computation. We found that
although they vary greatly in style, most are quite readable. Indeed it was a
pleasure, week after week, to be in the hands of the masters. These authors
are for the most part extraordinary people, including some about whom most
numerical analysts know little (such as Hirschfelder, one of the leading
American chemists of this century).

We were struck by how young many of the authors were when they wrote these
papers (average age: 34), and by how short an influential paper can be
(Householder: 3.3 pages, Cooley & Tukey: 4.4). Our readings also uncovered a
few surprises. For example, Curtiss and Hirschfelder inexplicably define
stiffness in terms of exponentially diverging trajectories, not converging
ones; nevertheless they invent the right cure for the problem in the shape of
backward differentiation formulas. For another example, did you know that the
classic SVD paper by Golub & Kahan makes no mention of the QR algorithm?

Our thirteen papers fall into three categories:

Finite algorithms for finite problems: papers 1,3,5
Infinite algorithms for infinite problems: papers 2,4,6,7,10,11
Infinite algorithms for finite problems: papers 8,9,12,13

(An infinite algorithm is one that depends on an iteration or discretization
parameter; an infinite problem is one for which all exact algorithms must be
infinite.) The third category is particularly interesting. Evidently four of
the most exciting modern developments in numerical analysis -- multigrid
iterations, conjugate gradient iterations, interior point methods, and
multipole methods -- have in common that they depend on the approximate
computation of quantities that might in principle be computed exactly.

Most readers of this note will have thought of other classic authors and papers
that should have been on the list. We agree! We are saving up ideas for the
next run of CS 722 in a couple of years.

Nick Trefethen
Dept. of Computer Science
Cornell University


From: Mike Dowling <>
Date: Mon, 3 May 93 11:33 MET DST
Subject: SIGOPT/OPT-NET: Call for Membership

(Fachgruppe Optimierung der DMV)

Call for Membership

The Special Interest Group for OPTimization (SIGOPT) has been
recently created under the auspices of the Deutsche Mathemiker
Vereinigung (DMV) with the purpose of encouraging cooperation amongst
its members, and of facilitating communication between them. It is
primarily intended to meet the needs of all those interested in
mathematical optimisation, both theory and practice.

SIGOPT provides a forum for discussing actual and future developments
in a broad variety of disciplines associated with optimisation, and
actively supports interdisciplinary research and applications to
industry. In particular, SIGOPT encourages students and younger
scientists to join in research on optimisation.

A yearly Mathematical Optimization Conference is organised by
SIGOPT members, the first of which will be held at Vitte/Hiddensee in
Germany in September this year. In the following two years, the
conference will be part of larger conferences, in Berlin under the
sponsorship of SVOR, and in Ulm under the sponsorship of DMV. The
following year, the conference will be held under GAMM sponsorship.
Further workshops shall be held on special aspects of mathematical

The first service to be provided by SIGOPT for the optimisation
community is OPT-NET, which has been implemented at the
Konrad-Zuse-Zentrum fuer Datentechnik in Berlin (ZIB) under the vice
presidency of Martin Groetschel. OPT-NET is an electronic forum
similar to NA-Net, so that most NA-Net participants will already be
familiar with the more important OPT-NET features. Like NA-Net, each
OPT-NET user has a unique nickname that can be used for e-mail
correspondence. If John has the nickname john, then Janet can send
e-mail to John by sending mail to

Each week, there will be a moderated digest consisting of articles
submitted by OPT-NET participants. The present moderator is Uwe
Zimmermann from the Technical University of Braunschweig. The digest
articles and other documents and programs will be stored in an archive
at ZIB, where they can be retrieved using simple e-mail messages
strongly reminiscent of the NETLIB procedure. There is also a
dialogue service via eLib for perusing and retrieving data stored in
the OPT-NET archive. Finally, anonymous FTP is can also be used to
deposit and retrieve data.

OPT-NET also supplies a WhitePage service similar to the WhitePages
associated with NA-Net. Participants names, research interests, etc.
are entered into a database which can be queried by other users. For
example, in this way you can find the e-mail address of a colleague,
or ask for a list of all those who are involved in research into
combinatorial optimisation.

There are nevertheless some important distinctions between OPT-NET
and NA-Net. Perhaps the most important difference is that the
WhitePages are closely associated with OPT-NET, so that, currently,
the only means of registering with the WhitePages is to register first
with OPT-NET. In fact, you will only have to register once, since the
OPT-NET database is the same as the WhitePage database. The only
difference is that, with a WhitePage registration, your data will be
publicly accessible. You can indicate on your OPT-NET registration
form that you want to publish your data. Only one registration is
therefore necessary for to participate in both OPT-NET and the
WhitePages. Similarly, changing your entry will update both your
OPT-NET entry and your WhitePage entry. Each user is solely
responsible for his or her own data. To guarantee this, your data
will be protected with a password which you will have to use each time
you change the data in your entry.

The opt-net-request program will NEVER use your e-mail address that
you enter with your registration. Rather, the e-mail address that the
mailer extracts from the header of your registration e-mail will be
used instead. In this way, we hope to avoid a number of problems that
may otherwise occur when sending e-mail through obscure gateways.

One more major distinction between OPT-NET and NA-Net is the
influence of the German data security laws which require that written
permission be obtained before personal data can be stored
electronically. This has the unfortunate consequence that, after you
have registered using e-mail, you will receive a letter by post
containing a form and a request that you sign to indicate that you
consent to ZIB storing your OPT-NET data. Failure to reply to this
letter will mean that the ZIB administration will have no alternative
but to delete your entry. Please do not feel disconcerted when you
receive this letter.

You are invited and encouraged to register with OPT-NET. You can
obtain the help file simply by sending an empty e-mail message to:

This help file will provide you with all the details you will need in
order to register with OPT-NET.

SIGOPT is also canvassing for new members. You can apply for
membership to SIGOPT simply by sending an e-mail message to with the appropriate subject line and
body. In fact, with a single additional line to your OPT-NET
registration e-mail, your request will be forwarded automatically to
the SIGOPT administration. How to do this and much more can be found
in the help file. SIGOPT will be using the OPT-NET database as its
membership list. In this way, you yourself can ensure that your
address information used by SIGOPT is always up to date. SIGOPT
members are therefore strongly advised to become OPT-NET participants.

We are particularly indebted to Martin Groetschel. From the
outset, it was clear that OPT-NET could never have got off the ground
without his offer to provide both the facilities and the man power
necessary for its implementation. It is thanks to him that OPT-NET
could be implemented at ZIB by ZIB staff. In this connection, we wish
extend our gratitude to the science director Joachem Luegger
( who was responsible for the organisation
and technical concept of OPT-NET, and Wolfgang Dalitz
(, who was instrumental in the software

We would especially like to thank Jack Dongarra and the NA-Net
team whose concept has served as an invaluable guide for designing

Mike Dowling (


From: P. M. Pardalos <>
Date: Thu, 6 May 93 14:40:54 EDT
Subject: Parallel Optimization Book

Topics in Parallel Computing in Mathematical Programming
(by P.M. Pardalos, A.T. Phillips and J.B. Rosen), Science Press (1992)
ISBN 1-880132-11-7

Chapter 1: Introduction to parallel computing
Chapter 2: Parallel methods for unconstrained optimization
Chapter 3: Parallel methods for large-scale linear and nonlinear programming
Chapter 4: Parallel methods for constrained global optimization
Chapter 5: Parallel methods for discrete optimization

The primary audience of this book is intended to be graduate students
and scientists interested in the applications of parallel computers in
solving mathematical programming problems. In addition, this book can
be used as a complimentary text for any course in parallel computing.


From: D. F. Griffiths <>
Date: Thu, 6 May 93 12:47:17 BST
Subject: Last Call: Dundee 93


29th June - 2nd July 1993

Last Call for Papers

Principal Speakers include

J W Barrett I S Duff C M Elliott
P Gill D J Higham N K Nichols
M J D Powell P Townsend J M Sanz-Serna
M N Spijker G W Stewart A M Stuart
R Temam M J Todd

A limited number of submitted papers will be presented. Abstracts
should be submitted by May 21.

Registration forms and full details of conference fees, etc.are
available from:

David F Griffiths Tel: (0382) 23181 EXT 4467
Dept of Maths & Computer Science FAX: (0382) 201 604
The University
Dundee DD1 4HN email:
Scotland, UK


From: Thomas M. Liebling <>
Date: Mon, 3 May 1993 18:29:41 +0200
Subject: A. W. Tucker Prize Announcement


The Mathematical Programming Society invites nominations for the A.W.
Tucker Prize for an outstanding paper authored by a student. The award will
be presented at the International Symposium on Mathematical Programming in
Ann Arbor (15-19 August 1994). All students, graduate and undergraduate,
are eligible. Nominations of students who have not yet received the first
university degree are especially welcome. In advance of the Symposium an
award committee will screen the nominations and select at most three finalists.
The finalists will be invited, but not required, to give oral presentations at
a special session of the Symposium. The award committee will select the winner
and present the award prior to the conclusion of the Symposium. The
members of the committee for the 1994 A.W. Tucker Prize are : Thomas M.
Liebling, Swiss Federal Institute of Technology, Lausanne; Andrew R. Conn,
Thomas J. Watson Research Center, Yorktown Heights, William H.
Cunningham, University of Waterloo, Clovis Gonzaga, COPPE, Federal
University of Rio de Janeiro and Jean-Philippe Vial, University of Geneva.


The paper may concern any aspect of mathematical programming; it may be
original research, an exposition or survey, a report on computer routines and
computing experiments, or a presentation of a new and interesting application.
The paper must be solely authored, and completed after January 1991. The
paper and the work on which it is based should have been undertaken and
completed in conjunction with a degree program.


Nominations must be made in writing to the chairman of the award committee

Thomas M. Liebling
Swiss Federal Institute of Technology
Department of Mathematics
CH-1015 Lausanne

by a faculty member at the institution where the nominee was studying for a
degree when the paper was completed. Letters of nomination must be
accompanied by four copies each of : the student's paper; a separate summary
of the paper's contributions, written by the nominee, and no more than two
pages in length; and a brief biographical sketch of the nominee.


Nominations must be sent to the chairman no later than December 31, 1993.
(Postmark on recommended letter).


From: Karen Hahn <>
Date: Mon, 3 May 93 14:57:38 EDT
Subject: IMACS Int'l. Conference on Computational Physics

Call for Papers/Call for Sessions
2nd. IMACS International Conference on COMPUTATIONAL PHYSICS
October 6-9, 1993
St. Louis, MO, USA

Conference Chair: Prof. Jean Potvin - St. Louis University

Topics to include: Computational Fluid Dynamics, Statistical mechanics,
Condensed matter Physics, Non-linear Dynamics, Quantum Field Theory on
the Lattice, Bio-Mechanics, Semi-Conductor Devices, Neural Networks,
Applications of Super- and Parallel Computers.

Proceedings will be produced, and selected papers of the conference
will also appear as regular articles in the IMACS journals. (IMACS
ACOUSTICS/World Scientific Pub. Co.)

For more information, contact:,,

Department of Science and Mathematics
Parks College of Saint Louis University
Cahokia, IL 62206, USA


IMACS Secretariat
Department of Computer Science
Rutgers University
New Brunswick, NJ 08903, USA


From: Post Kennung FORTWIHR <>
Date: Tue, 4 May 1993 07:37:17 +0200
Subject: Symposium on High Perfomance Scientific Supercomputing

The Bavarian Consortium for High Performance Scientific Computing (FORTWIHR)
announces a two-day
Symposium on High Perfomance Scientific Supercomputing
June, 17th and 18th, 1993
at BMW's Forschungs- und Ingenieur-Zentrum
Knorrstr. 147, D-8000 Muenchen 40, Germany

Topics will be perspectives, methods and applications of modern Supercomputing
in Science and Technology.

Invited Speakers:

Chr. Zenger (TU Muenchen) N. Fiebiger (Bayerische Forschungsstiftung)
R. Bulirsch (TU Muenchen) D. Kimbel (OECD)
H.D Simon (NASA) F. Durst (FAU Erlangen-Nuernberg)
A. Bode (TU Muenchen) H. Ryssel (FAU Erlangen-Nuernberg)
H. Fischer (BMW AG) W. Hanke (Univ. Wuerzburg, FORSUPRA)
G. Sachs (TU Muenchen) R. Callies (TU Muenchen)
K.-H.Hoffmann (TU Muenchen) G. Mueller (FAU Erlangen-Nuernberg)
E. Krause (RWTH Aachen) M. Schaefer (FAU Erlangen-Nuernberg)
A. Gilg (Siemens AG)

Conference languange will mainly be German.

The number of participants is limited to about 400.
Get application forms and further information from:

Prof. Dr. Chr. Zenger,
TU Muenchen,
Institut fuer Informatik,
Arcisstr. 21,
D-8000 Muenchen 2,



The Bavarian Consortium for High Performance Scientific
Computing (FORTWIHR) was founded for a time limited to nine years in
April, 1992. For a period of at least three years it will be financed by
the State of Bavaria and the Bavarian Research Foundation.
FORTWIHR is the fifth project financed by the Bavarian Research
Foundation, which was founded in 1990. The plan for the future is to
progressively increase the financial contributions of third agents.

More than 40 scientists in the fields of engineering sciences, applied
mathematics, and computer science of the Technical University of Munich
and of the Friedrich-Alexander-University of Erlangen-Nuernberg are
involved in the work of the Consortium. This inter-disciplinary concept
is based on the recognition that the increasing significance of the yet
young discipline High Performance Scientific Computing (HPSC)
can be only given due consideration if the technical knowledge of the
engineer, the numerical methods of the mathematician, and the up to date
methods and computers of computer science are all applied equally.


From: Trini Flores <>
Date: Wed, 05 May 93 13:22:45 EST
Subject: Inverse Problems and Optimal Design in Industry

Symposium on Inverse Problems and Optimal Design in Industry
July 8-10, 1993
Wyndham Franklin Plaza Hotel
Philadelphia, Pennsylvania

A three-day Symposium to broaden the contacts between universities and industry
on a world-wide scale. The Symposium precedes the July 12-16, SIAM Annual

A series of minisymposia at SIAM's annual meeting has been designed to
complement the themes of the three-day Symposium. SIAM invites all
attendees of the Symposium to attend the Annual Meeting.


SIAM has support from the Office of Naval Research to provide partial
reimbursement of travel and lodging expenses of graduate students and postdocs
who wish to attend the Symposium and the series of minisymposia at the Annual

To apply, students should ask their graduate advisor to send a letter of
recommendation, (include a statement of current status and research interests)
c/o Student/Postdoc Support IP93
3600 University City Science Center
Philadelphia, PA 19104-2688.

Postdocs should send a letter of application, including a statement of current
status and research interests to the same address.

The letter must be received at the above address by JUNE 15, 1993.


From: Aslak Tveito <>
Date: Tue, 04 May 1993 13:55:55 +0200
Subject: Post Doc Position at the University of Oslo


At The Department of Informatics, University of Oslo we have a
post doc position available for one year from approximately August 1-1993.
The salary is about $3000 per month. In addition, travelling expences to and
from Norway will be covered.

We are, in particular, interested in a person who has a background in
hyperbolic systems of conservation laws and who is interested in investigating
such systems by numerical experiments. The systems we are interested in
models different enhanced oil-recovery processes.

For further information, please contact

Ragnar Winther
Deparment of Informatics
University of Oslo
P.O. Box 1080 Blindern
0316 Oslo Norway



End of NA Digest