krj@utcsri.UUCP (10/09/87)
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 <hplabs!hwolkowicz%water.waterloo.edu@relay.cs.net> To: na.moler@score.stanford.edu 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 <na.moler@score.stanford.edu> Subject: Underflow in EISPACK 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> Subject: Workshop on Parallel Computing 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 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 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 ************************** -------