**Today's Topics:**

- Query on Topological Closure
- Underflow in EISPACK
- Workshop on Parallel Computing
- Parallel Programming Class

Date: Mon, 28 Sep 87 20:07:24 EDT

From: Henry Wolkowicz <hplabs!hwolkowicz%water.waterloo.edu@relay.cs.net>

To: na.moler@score.stanford.edu

I am interested in references to the problem: given 2 sets C,D, in a

seperated topological vector space X, when is the sum C+D closed?

In particular, I am interested in the case when C and D are closed,

cones. I am aware of several results, e.g. under local compactness

of one of the sets, a sufficient condition is that the

intersection of the 'recession cones' of C and -D

is 0. Are there any characterizations for the closure for finite or

infinite dimensions? Note that even the sum of 2 closed subspaces in

Hilbert space need not be closed.

d 1

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

Date: Mon 5 Oct 87 20:46:14-PDT

From: Cleve Moler <na.moler@score.stanford.edu>

To: na@Score.Stanford.EDU

UNDERFLOW IN EISPACK

by Eric Grosse, Bell Labs, Murray Hill, NJ

and Cleve Moler, Dana Computer, Sunnyvale, CA

We recently came across an interesting case where EISPACK fails

to give the correct eigenvalues for what appears to be an easy

matrix. The difficulties can be traced to floating point underflow.

They are most insidious in double precision arithmetic on the VAX [*]

where the "D" floating point format has an unfortunately small exponent

range. However, a scaled version of the example can fail on any machine,

including ones which fully conform to the IEEE floating point standard.

We recommend a simple change to the EISPACK top level routine "RS"

which should protect most users from the problem.

The example is due to Guenter Ziegler of the University of Augsburg

in West Germany and Andrew Odlyzko of AT&T Bell Laboratories. They

were investigating a question raised by Amir Dembo of Brown University

regarding the distribution of rank in real symmetric Hankel

matrices whose elements are +1 and -1. (A Hankel matrix is constant

along each anti-diagonal, but that's irrelevant for what concerns us

here.) One of their matrices is 9-by-9:

-1 1 1 -1 -1 1 1 -1 -1

1 1 -1 -1 1 1 -1 -1 1

1 -1 -1 1 1 -1 -1 1 1

-1 -1 1 1 -1 -1 1 1 -1

-1 1 1 -1 -1 1 1 -1 -1

1 1 -1 -1 1 1 -1 -1 1

1 -1 -1 1 1 -1 -1 1 -1

-1 -1 1 1 -1 -1 1 -1 1

-1 1 1 -1 -1 1 -1 1 1

It is not obvious, but this matrix happens to have four eigenvalues

equal to zero, and hence its rank is five. From the many possible

ways to compute the rank of such matrices, Zeigler and Odlyzko chose

for convenience to use the EISPACK routine RS (for Real Symmetric) and

count the number of negligible computed eigenvalues. For this example,

running on a VAX in D format double precision, EISPACK incorrectly

claimed there were five eigenvalues on the order of roundoff error.

The same program, running on almost any other computer, would produce

the correct answer, which is only four negligible eigenvalues.

The problem turns out to be a catastrophic underflow in the EISPACK

routine TQLRAT. This is a square-root-free variant of the QR algorithm for

finding eigenvalues of a symmetric tridiagonal matrix. It operates on

the squares of off-diagonal elements. On the VAX, the square of

double precision roundoff error is roughly 10^(-34) and the underflow

limit is only 10^(-38). There is not enough room between those two

numbers for TQLRAT to operate properly. On other computers, similar

difficulties will occur if the example is scaled by a factor on the

order of the square root of the underflow limit. For IEEE machines,

the scale factor would have to be about 10^(-150), so such examples are

much less likely in practice, but TQLRAT might not properly handle

any which do turn up.

The easiest solution is to replace

CALL TQLRAT(N,W,FV2,IERR)

in EISPACK routine RS by

CALL TQL1(N,W,FV1,IERR).

Since TQL1 does not work with the squares of the tridiagonal elements,

it is much less prone to underflow trouble. No change is needed in

the case when eigenvectors are being computed, since RS then calls TQL2

rather than TQLRAT.

An alternate solution, an improved version of TQLRAT, is available from

the authors. But its range of applicability is still limited to a smaller

portion of the floating point exponent range than TQL1 and TQL2.

Ironically, advances in floating point hardware make the need for

square-root-free algorithms less pressing. On one recent chip,

the builtin square root is even slightly faster than division!

[*] VAX is a trademark of Digital Equipment Corporation.

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

Date: Tue, 6 Oct 87 10:31 EST

From: Dan Warner <WARNER@prism.clemson.edu>

To: NA@SCORE.STANFORD.EDU

X-VMS-To: IN%"NA@SCORE.STANFORD.EDU"

Clemson University

presents a

WORKSHOP

on

PARALLEL COMPUTING*

This workshop is designed for researchers who are familiar with

traditional scientific computing but who are not up-to-speed with

the recentJdevelopments in parallel computing. The workshop will

be largely tutorial and will be focused on providing a firm

foundation in both architecture and algorithms. Particular

emphasis will be placed on the ascendant hypercube architecture.

After completing this workshop, attendees should be well prepared

to assess the significance and applicability of current work in

this rapidly evolving area.

Date and Time:

The workshop will start at 8:00 am Wednesday, November 18, and

will run until noon on Thursday, November 19. RHands onS demos of

the FPS T-20 hypercube will be available Thursday afternoon.

Key Topics:

The Evolution of Parallel Architectures

Measures of Parallel Performance

Optimal Communications in Hypercubes

Developments in Parallel Languages

Computational Fluid Dynamics

Multigrid on Hypercubes

Principal Lecturers:

Dr. Paul O. Frederickson, Los Alamos Scientific Laboratory

Dr. Michael W. George, Aeropropulsion Methods, Northrop Corp.

Dr. Roy P. Pargas, Computer Science, Clemson University

Dr. Dennis E. Stevenson, Computer Science, Clemson University

Dr. Daniel D. Warner, Mathematical Sciences, Clemson University

Accommodations are available at the Ramada Inn in Clemson (803)

654-7501. Mention the Workshop on Parallel Computing to obtain

the conference rate.

Attendance will be limited and advance registration is required.

The registration fee is $25.

Write to:

Department of Mathematical Sciences

Attn: Workshop on Parallel Computing

Clemson University

Clemson, SC 29634-1907

Phone:

Kay Powers (803) 656-2883 or Dept. Office (803) 656-3434

*This workshop is being funded by the Office of Naval Research

through the University Research Initiative Program, Contract No.

N00014-86-K-0693.

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

Date: Wed, 7 Oct 87 20:39:46 cdt

From: Rick Stevens <stevens@anl-mcs.ARPA>

To: na@score.stanford.edu

Argonne National Laboratory has set up an Advanced Computing

Research Facility (ACRF) for the study of parallel computing. It

currently features an 8-processor Alliant FX/8, a 20-processor

Encore Multimax, a 12-processor Sequent Balance 21000, and a

32-processor Intel iPSC hypercube machine. Local projects utilizing

the ACRF include investigations in parallel logic programming and

parallel linear algebra and the development of portable parallel

programming methodologies.

To encourage use of the ACRF as a national user facility,

Argonne is sponsoring various classes to familiarize potential

users with the ACRF multiprocessors and with parallel programming

in general. The next classes will be held on November 11-13, 1987

and January 13-15, 1988i. The first two days will cover parallel

programming on the Alliant, Encore,

Sequent, and Intel computers; the third day will be devoted to

consideration of each attendee's particular project. Fortran will be

emphasized as the primary programming language, although C will be discussed.

This will be a hands-on class; at its completion participants will

have written and run a number of programs on each machine, and should

be familiar with the ACRF environment.

Those interested in the classes should contact

Teri Huml

Mathematics and Computer Science Division

Argonne National Laboratory

Argonne, IL 60439-4844

(312) 972-7163

huml@anl.mcs.arpa

There will be a $25.00 charge for this class, no financial support

for attendees is available.

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

End of NA Digest

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

-------