Subject: NA Digest V87 #72

From: NA Digest <[email-masked]>
Date: Thu 8 Oct 87 22:12:00 PDT

NA Digest   Thursday, October  8, 1987   Volume 87 : Issue 72

This weeks Editor: Cleve Moler

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 <[email-masked]>
To: [email-masked]
Subject: Query on Topological Closure

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 <[email-masked]>
Subject: Underflow in EISPACK
To: [email-masked]

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 <[email-masked]>
Subject: Workshop on Parallel Computing
To: [email-masked]
X-VMS-To: IN%"[email-masked]"

                        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 <[email-masked]>
To: [email-masked]
Subject: Parallel Programming Class 

     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
     [email-masked]

There will be a $25.00 charge for this class, no financial support
for attendees is available.

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

End of NA Digest
**************************
-------