krj@na.toronto.edu (Ken Jackson) (01/23/89)
NA Digest Sunday, January 22, 1989 Volume 89 : Issue 3 Today's Editor: Cleve Moler 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 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 ************************** ------- Reposted by -- Kenneth R. Jackson, krj@na.toronto.edu (on Internet, CSNet, Computer Science Dept., ARPAnet, BITNET) University of Toronto, krj@na.utoronto.ca (CDNnet and other Toronto, Canada M5S 1A4 X.400 nets (Europe)) (Phone: 416-978-7075) ...!{uunet,pyramid,watmath,ubc-cs}!utai!krj