NA Digest Sunday, January 22, 1989 Volume 89 : Issue 3

Today's Editor: Cleve Moler

Today's Topics:

-------------------------------------------------------


From: Rob Schreiber <schreibr@riacs.edu>
Date: Wed, 11 Jan 89 09:53:06 PST
Subject: Hough's Random Story Explained

[Ed. Note: This week's first two contributions refer to a note
by David Hough in the NA Digest two weeks ago (Volume 89, Issue 1)
where he reported that a machine under development at Sun
slowed down severely when it encountered underflows in the
LINPACK Benchmark wth matrix order 512.]

Here is the explanation, (discovered by Nick Higham and me.)

The random number generator in "matgen" repeats after 16384 numbers.
(With the modulus 65536 it would be possible to extend the cycle to
that number. This could be done by replacing the relevant line by

init = mod(3125*init - 1,65536) .

This would, however, only push the problem out to 1024 by 1024
matrices.)

Another unfortunate choice was n = 512, which divides the period
(16384) of the generator. The effect is that the first 32 columns of
the matrix (16384 = 512 X 32) are repeated 16 times -- the matrix has
this structure:

A0 = rand(512,32);
A = [A0, A0, A0, A0, A0, A0, A0, A0, A0, A0, A0, A0, A0, A0, A0, A0];

Now consider the effect of the first 32 steps of Gaussian elimination.
We apply 32 transformations to A that have the effect, in real
arithmetic, of making A0 upper triangular. In floating point, they
leave a residue of small numbers (about 10 ** -7 in size) below the
main diagonal. Since round-off error is not random but in fact
deterministic, identical small numbers occur in each of the 15 blocks
of A to the right of the first. Thus, the remaining (512 - 32) X
(512 - 32) submatrix has the same block structure (with 15 columns)
as does A. Therefore, this process repeats every 32 steps:

after 32 steps the elements drop to O(10 ** -7);
after 64 steps the elements drop to O(10 ** -14);
after 96 steps the elements drop to O(10 ** -21);
after 128 steps the elements drop to O(10 ** -28);
after 160 steps the elements drop to O(10 ** -35);
after 192 steps the elements would drop to O(10 ** -42), but that is
less than the underflow threshold;

This explains why there is no problem in double precision (underflow
threshold is smaller than 10 ** -300) or for n = 256 (there are only 4
blocks of 64 columns each, so the smallest elements will be
O(10 ** -21) or for n = 300 or 1000 (columns aren't identical since n
does not divide the period 16384).

-- Rob Schreiber


------------------------------

From: Cleve Moler <moler@na-net.stanford.edu>
Date: Sun, 15 Jan 89 20:51:02 PST
Subject: Hough's Random Story and IEEE Denormals

David Hough and Rob Schreiber are right: the LINPACK Benchmark
uses a lousy random number generator and for certain orders the
matrices are singular, even highly rank deficient. The random
number generator used even predates LINPACK; it was part of the
EISPACK test program 20 years ago. It was intended to be portable,
which it is, and used to generate what are by today's standards
fairly small matrices. EISPACK tests went up to order 80.

But Hough's experience points out a serious shortcoming of the
implementations of IEEE floating point arithmetic that many of
us experience. He found that the rank deficiency led to underflows
and that underflows caused a serious degradation in speed. We
would see the same thing on the Ardent Titan, if we tried to
fully conform to the IEEE standard. This is because our machine,
like many others, must handle gradual underflow and denormal
numbers in software -- the required operations are too complicated
to be done in high speed, vector floating point hardware.

LINPACK and EISPACK are intended to function correctly if
underflows are quietly, and quickly, set to zero. There are
some places were these intentions are not completely fulfilled.
For example, convergence of implicit eigenvalue and singular
value iterations are compromised by underflow, particular with
VAX D format. But these situations are quite rare and gradual
underflow does not provide a complete fix.

So, at Ardent, we have chosen speed over denormals. Hough, and
Sun, are strong enough advocates for full IEEE compliance that
they will probably change the random number generator. I can
see a good case for either position.

-- Cleve Moler


------------------------------

From: John Lewis <jglewis%priapus@atc.boeing.com>
Date: Tue, 17 Jan 89 14:28:31 PST
Subject: SIAM Sparse Matrix Meeting Abstracts Deadline

Reminder -- the deadline for submitting abstracts to the SIAM
Conference on Sparse Matrices is fast approaching. Abstracts should
be submitted to the organizing committee no later than February 1st.

For those who may have missed the initial nanet announcement, and not
yet received either of the mailings from SIAM, the full text of the
announcement of the conference is attached.


SIAM Conference on Sparse Matrices


Sponsored by the SIAM Activity Group on Linear Algebra

Salishan Resort
Gleneden Beach, Oregon

May 22-24, 1989


OBJECTIVE: The quickening pace of increasing computer power and
decreasing cost has made feasible the solution of new, larger, and
more complex problems. Their solution requires new or improved
algorithms, while the architectural constraints imposed by the need
for high performance pose new difficulties in implementation. The
research and applications community have responded to these needs with
a number of advances in the solution of sparse problems.

This conference will provide a forum for the presentation of the most
significant achievements in meeting these new challenges. Theoretical
algorithms, new applications and implementations for vector and
parallel architectures will be presented. We expect to have
contributions in all of the traditional areas of sparse linear
algebra, linear equations, eigenvalue problems, and least squares
problems, as well as recent developments in such areas as sparse
control problems and sparse optimization. The conference is organized
to promote interchange of new ideas between the developers, the users
and the implementors of sparse matrix algorithms. We encourage the
participation of users of sparse matrix algorithms in structural
engineering, computational fluid dynamics, computational chemistry and
other fields, as well as the participation of algorithm developers.

FORMAT: The conference will be limited by the availability of hotel
rooms to approximately 150 participants. There will be no invited
speakers. Instead, 18 of the contributors will be chosen to give 45
minute presentations in non-parallel sessions over the three days of
the conference. In addition, there will be opportunity in 12 informal
workshops, scheduled in four periods, for the other contributors to
present their accomplishments and to discuss with their colleagues the
needs and directions for future work. All accepted abstracts, whether
for formal or informal presentation, will be distributed in the
conference program.

DEADLINE FOR PAPERS: In keeping with the goal of presenting the most
current advances, the deadline for submissions is not until Feb. 1,
1989. In selecting speakers, the committee will evaluate most
positively novel and unpublished work. Promising work in progress is
appropriate for submission.

LOCATION: The Salishan Resort is a first-class resort in an
attractive and secluded location on the beautiful Oregon Coast.
Contrary to usual anti-tourism propaganda, the weather at Salishan in
May is usually warm, sunny and dry. The resort provides easy walking
access to the beach, and has a wide range of exercise facilities. Its
location is ideal for exploring the Oregon Coast for those who may
want to arrive earlier or stay after the meeting. Transportation from
the Portland International Airport (approximately 90 miles) will be
available at specified times.

PROCEEDINGS: The SIAM Journal on Matrix Analysis will publish a
partial proceedings in a specially designated issue(s), consisting of
refereed contributions solicited from presentations at this
conference.

SUBMISSION OF ABSTRACTS:

Potential contributors should submit an extended abstract of no more
than two pages (approximately 800 words). Abstracts should be
submitted to:

John G. Lewis
Mail Stop 7L-21
Boeing Computer Services
P.O. Box 24346
Seattle WA 98124
(206)-865-3510

email: jglewis@atc.boeing.com or na.lewis@na-net.stanford.edu

We prefer to receive abstracts by electronic mail, where we will be
prepared to process plain ascii, plain TEX, LATEX or TROFF files.

REGISTRATION MATERIALS AND ADDITIONAL INFORMATION: Registration
materials will be sent automatically on receipt of abstracts.
However, participants who do not intend to give presentations and
participants who wish to ensure a reservation for one of the limited
hotel rooms are invited to register prior to the abstract deadline.
Registration materials can be obtained by completing the coupon
attached to this announcement and mailing it to:

Mr. Richard Porth
Conference Director
SIAM
117 South 17th Street, 14th Floor
Philadelphia, PA 19103, USA

Alternatively, you may send an electronic mail message including all
the information requested on the coupon, and the header (message for
Richard Porth, SIAM Conference on Sparse Matrices), to:

SIAM@wharton.upenn.edu or na.siam@na-net.stanford.edu



LOCAL ORGANIZING COMMITTEE:
John Lewis, Boeing
Horst Simon, Boeing and NASA Ames
Loyce Adams, Washington
David Scott, Intel

ADVISORY COMMITTEE:
Iain Duff, AERE Harwell
Stan Eisenstat, Yale
Alan George, Waterloo
Gene Golub, Stanford
Beresford Parlett, Berkeley
Ahmed Sameh, Illinois
Bob Ward, Oak Ridge

SPECIAL EVENTS

Welcoming Reception, Sunday, May 21, 8-10 pm
Beach Party & Clam Bake, Tuesday, May 23, 7-10 pm
Naturalist Guided Trail Walk, Wednesday, May 24, 5-7 pm ($6)
Climb of Mt. St. Helens, Thursday, May 25 (limited, by prior
arrangement only with the leader, Cleve Ashcraft)


------------------------------

From: John Lewis <jglewis%priapus@atc.boeing.com>
Date: Tue, 17 Jan 89 14:29:15 PST
Subject: Sparse Mountain Climbing

SIAM Members' Climb of Mt. St. Helens
May 25, 1989

Following the SIAM Sparse Matrix meeting, climb to the crater of Mt.
St. Helens in southwestern Washington State. This will involve 4500'
elevation gain (or more, depending on snow level) in an area of
spectacular beauty still devastated by the eruption several years
ago. Participants should be in good shape and will require proper
boots, attire and an ice axe. Previous ice axe experience will not
be required. Party size will be limited to six.

The climb will be made on Thursday, May 25. Camping arrangements
near the volcano will be made for Wednesday evening. Return to
Portland or Seattle on Friday.

This trip is neither sponsored nor endorsed by SIAM. Participants
assume all risks.

For more information, contact the leader before February 6 or after
March 1.

Cleve Ashcraft

na.ashcraft@na-net.stanford.edu
or
ashcraft@cs.yale.edu

203 - 432 - 1221
203 - 432 - 1200


------------------------------

From: Olavi Nevanlinna <MAT-ON%FINHUT.BITNET@Forsythe.Stanford.EDU>
Date: Thu, 19 Jan 89 10:41:25 EET
Subject: Scientific Director in Finland

SCIENTIFIC DIRECTOR AT THE STATE COMPUTER CENTRE IN FINLAND

A Cray X-MP supercomputer was installed in
Finland at the beginning of 1989. The Centre for
Scientific Computing, located in the Finnish State
Computer Centre, is responsible for operating the
computer and developing its environment. Principal
users of the computer include universities, the
Institute of Meteorology, the Finnish State
Technical Research Centre, and the Finnish State
Computer Centre.

In order to further develop supercomputing in
Finland we are now seeking a

SCIENTIFIC DIRECTOR.

The scientific director will work directly under the
manager of the State Computer Centre. The job
contract is for a period of 2-5 years.
The duties of the scientific director are the
following:

- The main task is to promote supercomputing
culture in all ways, both in scientific and applied
computing.
- He/she must establish and
maintain national and international connections
necessary for supercomputing.
- He/she will make proposals to improve the
environment of the supercomputer.

Candidates are required to have reached the scientific competence
of an assistant professor. In addition ,
international experience, connections to research
groups in universities and in industry, and the
ability to cooperate are considered beneficial.

For additional information, please contact the
chairman of the scientific board, Dr Risto Raitio,
Tel. 358-0-134171, network address RAITIO@FINFUN.BITNET.
Send applications to the secretary of the
scientific board: Hannu Karttunen, VTKK/TLP 2106,
PO Box 40, SF-02101 Espoo, Finland.
Deadline for applications is 6 March 1989.
The application should include a Curriculum Vitae,
salary requirement and all documents the candidate
wants to refer to.


------------------------------

From: Joe Traub <traub@cs.columbia.edu>
Date: Thu, 19 Jan 1989 11:27:45 EST
Subject: Complexity of Approximately Solved Problems

LAST CALL FOR PAPERS

Third Symposium on Complexity of Approximately Solved Problems
Computer Science Department
Columbia University

April 3-5, 1989

See NA Digest, Volume 89, Issue 1, for detailed annoucement.


------------------------------

From: Jesper Traff <mcvax!diku.dk!traff@uunet.UU.NET>
Date: Fri, 20 Jan 89 10:03:33 +0100
Subject: Binary Integer Programming Problems

I take the liberty to repost this message to the Stanford Numerical
Analysis list.

To people working on binary integer programming problems.

At the University of Copenhagen we are currently implementing a
parallel implicit enumeration algorithm for solving general binary
linear integer programming problems. So far our programs (written in C
for a 32 node Intel hypercube) seems to work well, but we lack medium
to large problem instances to make more interesting performance tests.
Anybody on the net who can supply us with such test cases??

Problem sizes prefered:
50 to 100 variables and 20 to 50 constraints, no special
representation required (we use an adjacency list representation of the
constraint matrix, but we can convert to this representation
ourselves)

regards and thanks in advance

Jesper Larsson Traff

DIKU, Deptartment of Computer Science, University of Copenhagen, Denmark
e-mail: traff@diku.dk


------------------------------

From: MT56000 <MT56%MCGILLA.BITNET@Forsythe.Stanford.EDU>
Date: Sat 21 Jan 1989 13:59:00 EST
Subject: Conference Honoring C. Radhakrishna Rao

RECENT DEVELOPMENTS IN STATISTICAL DATA
ANALYSIS AND INFERENCE: INTERNATIONAL
CONFERENCE IN HONOUR OF C. RADHAKRISHNA RAO

This International Conference on Recent Developments in
Statistical Data Analysis and Inference in honour of C.
Radhakrishna Rao will be held at the Universite de
Neuchatel, Neuchatel, Switzerland, from 21-24 August
1989. The conference will include invited talks,
contributed papers, and poster presentations; there will
also be ample opportunity for statistical software
demonstrations. All meeting activities will be held at the
University Campus where meals will be available at
reasonable rates. Accommodation will be available in the
inner-harbour area. As the number of reasonably-priced
hotel rooms in Neuchatel is limited, please register as
soon as possible; late registration may incur booking
problems in the center of Neuchatel.
A town of yellow stone, Neuchatel was founded upon a
hill dominated since the twelfth century by its castle and
collegiate church, and overlooks the largest lake in the
country to be entirely surrounded by Swiss territory.
Behind is situated the forest of Chaumont, which is flanked
on both sides by splendid vineyards. Founded in 1838, the
University of Neuchatel is situated within a few steps of
the lake. Though famous for its French language discipline,
the University offers courses in almost all current
branches of scientific study, and also accommodates
students from over 25 countries.
Talks are expected to be given on the following topics:
Estimation, Design of experiments P combinatorics,
Multivariate analysis, Generalized inverses, Weighted
distributions, Characterizations of probability
distributions, Linear models: fixed and mixed models,
Differential-geometric approaches to inference, Large-
sample test criteria, Data analysis, Bootstrap, Jackknife,
Bayes and empirical Bayes, Foundations, Stochastic
processes, Computational statistics, Sampling designs for
longitudinal data. The North Holland Publishing Company
will publish the conference proceedings. About 30
terminals connected to the System VAX/MS will be made
available, as well as certain PCUs.
The opening lecture will be given by Sir David Cox
(Nuffield College, Oxford). Invited speakers include: G.J.
Babu (USA), J.K. Baksalary (Poland), G.A. Barnard (UK), O.E.
Barndorff-Nielsen (Denmark), P.J. Bickel (USA), C.R. Blyth
(Canada), T. Cacoullos (Greece), T.K. Chandra (India), A.
Cohen (USA), C.M. Cuadras (Spain), P.L. Davies (FRG), M.H.
DeGroot (USA), H. Drygas (FRG), D.A.S. Fraser (Canada), F.
Fujikoshi (Japan), J.K. Ghosh (India), S.S. Gupta (USA), F.
Hampel (Switzerland), T. Havranek (Czechoslovakia), C.C.
Heyde (Australia), A. Kagan (USA), C. Kallianpur (USA), C.G.
Khatri (India), J. Kleffe (GDR), J. Kubilius (USSR), N.M. Laird
(USA), K.S. Lau (USA), T.A. Louis (USA), A. Marazzi
(Switzerland), T. Mathew (USA), F. Mehran (Switzerland),
S.K. Mitra (India), R. Mukerjee (India), J.M. Oller (Spain), E.
Parzen (USA), M.D. Perlman (USA), F. Pukelsheim (FRG), T.
Pukkila (Finland), S. Puntanen (Finland), M.M. Rao (USA), A.
Rizzi (Italy), E. Ronchetti (Switzerland), W. Schaafsma (NL),
D.N. Shanbhag (UK), P.K. Sen (USA), N.D. Singpurwalla (USA),
P. Sint (Austria), J.N. Srivastava (USA), G.P.H. Styan
(Canada), V. Statulevicius (USSR), T. Taguchi (Japan), I.J.
Taneja (Brazil), I. Vincze (Hungary), M. Zelen (USA), and V.
Zolotarev (USSR).
Those wishing to contribute papers at this conference
should submit an abstract in English (limited to one typed
page), related to any of the conference topics, to Yadolah
Dodge, Groupe dUinformatique et de statistique, Universite
de Neuchatel, Pierre--Mazel 7, Switzerland-2000
Neuchatel, Switzerland; (41-38) 257205.


------------------------------

From: David Salzman <salzman@jvnca.csc.org>
Date: Sat, 21 Jan 89 17:33:25 EST
Subject: Symposium on Automatic Groups at JvNC

The Geometry Supercomputer Project and
The John von Neumann National Supercomputer Center
Present a

SYMPOSIUM ON AUTOMATIC GROUPS

Friday-Saturday, 10-11 February 1989

The symposium will consist of talks and computer demonstrations, and will
be held at the John von Neumann National SupercomputerCenter (JvNC) in
Princeton, New Jersey, on Friday and Saturday, 10-11 February 1989.
PRE-REGISTRATION IS MANDATORY since space will be limited. Those giving
talks and demonstrations include:

Jim Cannon
David Epstein
Bill Floyd
Lee Mosher
David Mumford
Hamish Short
Bill Thurston
Jeff Weeks
David Wright

The Geometry Supercomputer Project is directed by Fred Almgren (Princeton),
Jim Cannon (BYU), David Dobkin (Princeton), Adrien Douady (Paris), David
Epstein (Warwick), John Hubbard (Cornell), Benoit Mandelbrot (IBM and Yale),
Albert Marden (Minnesota), Jack Milnor (IAS and Stony Brook), David Mumford
(Harvard), Bob Tarjan (AT&T Bell Labs and Princeton), Bill Thurston
(Princeton), and Allan Wilks (AT&T Bell Labs).

The John von Neumann National Supercomputer Center is owned and operated
by the Consortium for Scientific Computing, comprising the University of
Arizona, Brown, the University of Colorado, Columbia, Harvard, the
Institute for Advanced Study, MIT, New York University, Pennsylvania
State University, the University of Pennsylvania, Princeton, the
University of Rochester, and Rutgers.

Call the von Neumann Center at 609/520-2000 for further information, or to
pre-register.

------------------------------

End of NA Digest

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