**Today's Topics:**

- Hough's Random Story Explained
- Hough's Random Story and IEEE Denormals
- SIAM Sparse Matrix Meeting Abstracts Deadline
- Sparse Mountain Climbing
- Scientific Director in Finland
- Complexity of Approximately Solved Problems
- Binary Integer Programming Problems
- Conference Honoring C. Radhakrishna Rao
- Symposium on Automatic Groups at JvNC

From: Rob Schreiber <schreibr@riacs.edu>

Date: Wed, 11 Jan 89 09:53:06 PST

[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

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

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

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

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

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

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

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

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

**************************

-------