krj@na.toronto.edu (Ken Jackson) (01/09/89)
NA Digest Sunday, January 8, 1989 Volume 89 : Issue 1
Today's Editor: Cleve Moler
Today's Topics:
Complexity of Approximately Solved Problems
Numerical Solution of Markov Chains
Conference on Numerical Combustion
SIAM Student Competition
Positions in Supercomputing at NASA Ames
Numerical Computation Position at U. Colorado
Random Story
-------------------------------------------------------
From: Joe Traub <traub@cs.columbia.edu>
Date: Tue, 3 Jan 1989 9:26:19 EST
Subject: Complexity of Approximately Solved Problems
SECOND CALL FOR PAPERS
Third Symposium on Complexity of Approximately Solved Problems
Computer Science Department
Columbia University
April 3-5, 1989
PROGRAM COMMITTEE:
Kenneth Arrow
Department of Economics
Stanford University
Stanford, California
Jerome Feldman
International Computer Science Institute
147 Center Street
Berkeley, California
Richard Karp
Computer Science Department
University of California at Berkeley
Berkeley, California
Christos Papadimitriou
Computer Science Department
University of California at San Diego
San Diego, California
Steven Smale
Mathematics Department
University of California at Berkeley
Berkeley, California
Joseph Traub
Computer Science Department
Columbia University
New York, New York
Henryk Wozniakowski
Computer Science Department
Columbia University
New York, New York
Donald Ylvisaker
Statistics Department
University of California at Los Angeles
Los Angeles, California
PARTIAL LIST OF SPEAKERS
PLENARY SPEAKERS:
Leon N. Cooper
Brown University
Steven Smale
University of California, Berkeley
INVITED SPEAKERS:
Adam Bojanczyk
Cornell University
Terrance Boult
Columbia University
David Donoho
University of California, Berkeley
Zvi Galil
Columbia University
Feng Gao
University of British Columbia
Ehud Kalai
Northwestern University
Mark Kon
Boston University
Marek A. Kowalski
University of Warsaw
J. Kuczynski
University of Warsaw
David Lee
AT&T Bell Laboratories
Leonid Levin
Boston University
Mario Milanese
Politecnico di Torino
Erich Novak
University of Erlangen
Michael Shub
IBM, T.J. Watson Research Center
K. Sikorski
University of Utah
Michael Steele
Princeton University
Aleksei Sukharev
Moscow State University
John N. Tsitsiklis
Massachusetts Institute of Technology
Umesh Vazirani
University of California, Berkeley
Grace Wahba
University of Wisconsin
Greg Wasilkowski
University of Kentucky
Arthur Werschulz
Columbia University
Henryk Wozniakowski
Columbia University
SOME OF THE TOPICS TO BE ADDRESSED ARE:
Average Case Analysis of Algorithms Neural Nets
Computational Complexity Optimal Recovery
Computer Vision Parallel Computation
Connectionist Models Prediction and Estimation
Continuous Complexity Random Algorithms
Decision Theory Random Complexity
Design of Experiment Robotics
Distributed Complexity Scientific Computation
Information-Based Complexity Seismology
Inverse Problems Signal Processing
Mathematical Economics
CONTRIBUTED PAPERS: All appropriate papers for which abstracts are
contributed will be scheduled. Contributed papers will be twenty
minutes in length.
To contribute a paper send title, author, affiliation, and abstract on
a single 8 1/2 by 11 sheet of paper or by electronic mail.
The above can be sent by U.S. mail to:
J.F. Traub
Computer Science Department
Columbia University
450 Computer Science Building
New York, New York 10027
Electronic Mail: kerny@cs.columbia.edu
TITLES AND ABSTRACTS MUST BE RECEIVED BY NO LATER THAN FEBRUARY 1, 1989
PUBLICATION: Invited papers will be published in the Journal of Complexity.
REGISTRATION: The symposium will be held in the Kellogg Conference
Center, on the fifteenth floor of the International Affairs Building,
Columbia University, 118th Street and Amsterdam Avenue. Registration
will start at 9:00 a.m. THERE IS NO REGISTRATION CHARGE.
FOR FURTHER INFORMATION: The program schedule will be sent
electronically about March 1, 1989. If you have any questions,
contact Kerny McLaughlin, Computer Science Department, Columbia
University, (212) 854-2736.
below and return by U.S. Mail to Traub or by electronic mail to
kerny@cs.columbia.edu.
SYMPOSIUM ON COMPLEXITY OF APPROXIMATELY SOLVED PROBLEMS
April 3-5, 1989
Name:
Affiliation:
Address:
[ ] I will attend the Complexity Symposium.
[ ] I may attend the Complexity Symposium.
[ ] I will contribute a paper.
------------------------------
From: William J. Stewart <billy@ece-csc.ncsu.edu>
Date: Wed, 4 Jan 89 09:31:25 EST
Subject: Numerical Solution of Markov Chains
Call for Papers
FIRST INTERNATIONAL WORKSHOP ON THE
NUMERICAL SOLUTION OF MARKOV CHAINS
North Carolina State University
Raleigh, N. Carolina, 27695-8206, USA.
January 8-10, 1990
The workshop aims are twofold: To foster cooperation among researchers and
practitioners working on diverse aspects of the numerical solution of Markov
chains; and to provide an opportunity for researchers to present their latest
results. The collection of presentations intends to be an authoritative over-
view of the field, including its developments, current status, and projections
for future directions. With this in mind, the program will consist of both
invited and contributed papers. The workshop proceedings will be published.
Workshop Organization:
Program Chairman: William J. Stewart, NCSU
Local Organizing Comm: C.D. Meyer, NCSU
R.J. Plemmons, NCSU
K. Trivedi, Duke University
S. Stidham, Jr., UNC
Speakers Participating in the Workshop:
P.J. Courtois Philips Research, Belgium
N.M. Van Dijk Vrije Univ., Netherlands
G.H. Golub Stanford Univ., USA
W.K. Grassmann U. of Saskatchewan, Canada
G. Latouche U. Libre de Bruxelles, Belgium
D. Mitra AT&T Bell Labs, USA
M.F. Neuts U. of Arizona, USA
Y. Saad RIACS, USA
P. Schweitzer U. of Rochester, N.Y., USA
E. Seneta U. of Sydney, Australia
G.W. Stewart U. of Maryland, USA
Y. Takahashi Tohoku Univ., Japan
K. Trivedi Duke Univ., USA
List of Topics:
Applications
Matrix Generation Techniques
Stochastic Petri Nets
Computation of Stationary Probability Vectors
Direct Solution Methods
Iterative Solution Methods
Recursive Solution Methods (incl. those of Neuts)
Domain Decomposition Methods
Incomplete Factorizations
etc.
Computation of Transient Solutions
Randomization/Uniformization
O.D.E. & P.D.E. Solvers
Others
Approximations
Aggregation/Disaggregation
Very Large State Spaces
Bounds
Markov Reward Models
Infinite Markov Chains
Sensitivity Analysis
Parallel Implementations
P.C. Demonstrations
IMPORTANT DATES:
June 1, 1989 Deadline for paper submission
Sept. 1, 1989 Notification of acceptance
Oct. 15, 1989 Final versions due
Jan. 8-10, 1990 Workshop
INSTRUCTIONS:
Submit five copies of a full paper to W.J. Stewart by June 1, 1989.
Papers should be no more than 20 double-spaced typewritten pages,
including tables and figures. All correspondance should be addressed to
William J. Stewart
Department of Computer Science
North Carolina State University
Box 8206
Raleigh, N.C. 27695-8206, USA
Phone: (919) 737-7824
E-mail: billy@ece-csc.ncsu.edu
------------------------------
From: Ed Block <IEBLOCK@wharton.upenn.edu>
Date: Wed, 4 Jan 89 21:23 EST
Subject: Conference on Numerical Combustion
Dear Colleague:
As you may know, INRIA, in association with SIAM, is conducting
the Third International Conference on Numerical Combustion.
The conference will be held on May 23-26, 1989, in Antibes on
the French Riviera.
Due to the recent French postal strike, the distribution of the
call-for-papers was delayed, especially in the United States.
Bernard Larrouturou, the French chair of the conference, has
asked me to let you know that the deadline for proposed
contributions has been postponed to January 15, 1989.
If you are interested in submitting a paper for this conference,
it is suggested that you send it now to:
Therese Bricheteau
INRIA
Domaine de Voluceau
BP 105 - Roquencourt
78153 Le Chesnay Cedex
FRANCE
Tel: 33/1/39-63-56-00
Telex: 697033F
Other relevant details are:
Topics: numerical methods for combustion problems, numerical
simulation of combustion phenomena.
Full contributions: ten (10) pages maximum.
Notification of acceptance: January 31, 1989
I hope we have been in time to give you the opportunity to send
your contributions to INRIA.
I. Edward Block
SIAM
January 4, 1989
------------------------------
From: Ed Block <IEBLOCK@wharton.upenn.edu>
Date: Thu, 5 Jan 89 18:40 EST
Subject: SIAM Student Competition
January 5, 1989
MEMORANDUM TO: STUDENTS AND THEIR ADVISERS
Subject: Best Papers Competition
The following announcement will appear in the January issue of
SIAM News:
The student authors of the three best papers in applied and computational
mathematics submitted to SIAM will be invited by SIAM to attend its annual
meeting in San Diego, July 17-21, 1989. Each winner will receive up to $750
to offset expenses and will be recognized at the meeting. Papers must be
singly authored to be eligible for consideration. Winners must present their
papers at the meeting to receive the awards. In submitting their work for
publication, authors are asked to consider the SIAM journals.
To qualify, authors must be students in good standing who have not received
their PhDs at the time of the submission.
Submissions must be received by SIAM on or before April 1, 1989. Submissions
can be sent by regular mail or Fax. Each submission must include (1) an
extended abstract (3-4) pages, double-spaced, in English); (2) the signature
of the author (on the submission); (3) a statement by the student's faculty
adviser (also on the submission) that the paper has been prepared by the
author indicated and that the author is a student in good standing; and (4) a
short biography of the student. Each submission must also include a letter of
recommendation from the student's adviser or department chair.
Submissions will be judged on the basis of originality, applicability, and
clarity of exposition. The winners will be notified by May 15, 1989.
Submissions and questions about this competition should be sent to A. Bogardo,
c/o San Diego Competition, SIAM, 1400 Architects Building, Philadelphia, PA
19103-5052. E-mail to siam@wharton.upenn.edu. Fax to (215) 564-4174.
Students interested in joining SIAM (only $15 per year) are invited to write
to SIAM for membership information.
------------------------------
From: Eugene Miya <eugene@orville.nas.nasa.gov>
Date: Thu, 05 Jan 89 18:32:04 PST
Subject: Positions in Supercomputing at NASA Ames
Supercomputing: No Experience Required
A Special Announcement of Opportunity (AO)
Numerical Aerodynamic Simulation Systems Division
NASA Ames Research Center
The Numerical Aerodynamic Simulation (NAS) Systems Division is seeking
new, recent, "fresh-out," graduates for challenging positions in large-scale
computer systems research, development, and operational support at
the NASA Ames Research Center located on Moffett Field, CA
[southern-most tip of San Francisco Bay in the Santa Clara Valley].
The NAS Facility houses one of the world's largest and most advanced
supercomputer systems, used by a nationwide user community for
solving highly complex problems in fluid dynamics, aeronautics, space,
and other scientific disciplines. The System includes a CRAY Y-MP*,
a CRAY-2, a Thinking Machine's Connection Machine-2, dual Amdahl 5880's,
four VAX 11/780s, over 30 Silicon Graphics Iris and SUN workstations
interconnected with local area networks ranging in speed 10 to 800 Mhz.
The user visible operating system is UNIX with TCP/IP-based networking
extensions.
Systems research, development, and computational service opportunities
exist in the following areas:
1) Supercomputers
2) Mass Storage Systems
3) High Performance Scientific Workstations
4) High Performance Data Networks
5) Long Haul Communications
6) Mini-supercomputers
Future developments will involve NeXT machines, Ardent Titan and Stellar
graphical superworkstations, and other flavors of state of the art
high technology.
These positions require at least a Bachelor's degree [or more] in
computer science, engineering, or one of the physical sciences.
Knowledge of the UNIX operating system and the DoD Internet Protocols
is highly desireable. This is an excellent entry opportunity for the
young and young-at-heart.
NASA (The National Aeronautics and Space Administration) is the Nation's
civilian space Agency. The NASA Ames Research Center is an
Equal Opportunity Employer.
US Citizenship is required. Security clearance is not required.
Send resumes to:
Mr. Bruce Blaylock
Chief, NAS Systems Development Branch
M/S 258-5
NASA Ames Research Center
Moffett Field, CA 94035
blaylock@prandtl.nas.nasa.gov or
ames!prandtl!blaylock
TeX and troff okay.
*Trademarks:
CRAY Y-MP, CRAY-2 are trademarks of Cray Research Inc.
Connection Machine-2 is a trademark of Thinking Machines Corp.
UNIX is a trademark of AT&T Bell Laboratories.
VAX is a trademark of Digital Equipment Corporation.
Iris is a trademark of Silicon Graphics Inc.
SUN is a trademark of SUN Microsystems Inc.
Send specific questions to me.
-- Eugene Miya
------------------------------
From: Bobby Schnabel <bobby@boulder.Colorado.EDU>
Date: Fri, 6 Jan 89 14:25:01 MST
Subject: Numerical Computation Position at U. Colorado
UNIVERSITY OF COLORADO
DEPARTMENT OF COMPUTER SCIENCE
We invite applications for a faculty position in parallel and
numerical computation. Preference is at the assistant professor
level, but candidates at all levels will be considered.
The Department has a faculty of 20, and 160 graduate students.
It has strong research programs in parallel and distributed
computation, numerical computation, artificial intelligence,
systems and software, databases, and theoretical computer science.
The computing environment includes Vax-class mainframes, SUN-class
workstations, Symbolics workstations, shared and local memory
multiprocessors including an Intel Hypercube, Encore and Sequent
multiprocessors, and an Alliant FX/8. A number of research
activities in parallel and distributed computation are supported
by an NSF-funded CER award. The Department is a principal
participant in the University's Center for Applied Parallel
Processing which has a broad interdisciplinary research program
in large-scale scientific computation and operates a Thinking
Machines CM2. There is also a satellite link to the supercomputing
facility at the John Von Neumann Center in Princeton.
Applicants should send a current curriculum vita to Professor
Robert Schnabel, Department of Computer Science, Campus Box 430,
University of Colorado, Boulder, CO 80309-0430. Applications
are due by February 15, 1989. Late applications will be considered
for any positions remaining unfilled on March 15, 1989.
The University of Colorado at Boulder has a strong institutional
commitment to the principle of diversity in all areas. In that
spirit, we are particularly interested in receiving applications
from women, ethnic minorities and disabled individuals.
------------------------------
From: David Hough <dgh@Sun.COM>
Date: Fri, 6 Jan 89 21:52:41 PST
Subject: Random Story
It's not often that I apply what I learned at Berkeley
to my daily work, which primarily involves finding very
low-level bugs in hardware and software, mostly under
development by other people.
Since I have to test hardware with a wide performance
range, benchmarks have to be adjustable in size so that they
don't run too quickly on fast hardware to be timed accu-
rately, nor too slowly on slow hardware to finish before
that hardware is obsolete.
So I have added adjustable parameters to a number of
benchmarks. To calibrate them I run a little measurement
program derived from the infamous Linpack benchmark. (When
I first came to Sun I was so ignorant that I thought Linpack
was a library of linear algebra subroutines rather than a
benchmark program.)
This little Linpack starts off factoring a 32x32
matrix. Even a Sun-2 can do that in acceptable time. If
the time is too fast, it then automatically tries a larger
matrix, up to 512x512. Then it computes what the execution
time would have been for a 512x512 on the particular system,
scaling the time for whatever matrix it settled on by
(512/n)**3.
Some Sun hardware currently under development has been
getting fast enough that the calibration program tries
512x512. On both projects in question, however, I noticed
that the program was getting hung up and taking an inordi-
nate amount of time to finish the calibration program. This
of course indicated a hardware bug, of which I informed the
hardware guys and left them to find it. Oddly enough, the
bug only affected IEEE single precision; double precision
was fine; most of our bugs tend to occur in double precision
for various reasons. Furthermore the bug didn't seem to
show up in the 100x100, 300x300, or 1000x1000 single preci-
sion Linpack benchmarks that I also run.
In the first project the microcoder dutifully tracked
things down with a logic analyzer to where an underflow was
occurring. Now I knew that the Linpack benchmark generates
uniform random data over an innocuous interval, and we all
know that matrices composed of random data from a uniform
distribution are remarkably well conditioned. I remember
this particularly well because one of my Berkeley qualifying
examination questions - put to me a week ahead of time to
ponder fruitlessly - was to come up with a plausible expla-
nation of how an eminent mathematician had conducted an
empirical investigation of iterative improvement, studying
published test matrices and matrices of uniformly-
distributed random data, and had come to the conclusion that
iterative improvement never improved the answer by more than
one or two digits, which seemed to argue against what's
routinely taught in elementary numerical analysis.
Anyway I told the microcoder that there was still a
hardware bug, but shortly thereafter something else changed
and the calibration benchmark went back to 256x256 and there
never was any other evidence of a single precision problem,
so I quit worrying about it. Underflows, if they could have
occurred, would account for the program apparently hanging
up, because the way Sun obtains IEEE conformance on under-
flow in systems built upon hardware like the Weitek 1164/5,
is to trap on underflow and recompute the correct result
very slowly in software. Such underflows are supposed to be
rare.
Then a totally unrelated but even more critical project
ran into a similar problem. This afternoon I went to a high
level crisis meeting attended by at least two vice
presidents, at which I gloomily reported that a new, previ-
ously unknown hardware bug had appeared that affected single
precision.
Upon returning from that meeting one of my colleagues,
who'd been helping at the logic analyzer until he got suspi-
cious, informed me that he thought there was no hardware or
compiler bug, rather that the program had started to under-
flow because the pivots had gotten too small and fallen off
the end of single precision. What about the well-known
wonderful condition of matrices of uniform random data, I
asked? He suspected that the high dimensionality (512x512)
was just too much for single precision. I wondered why the
1000x1000 benchmark worked in single precision.
Since no progress was being made on the hardware bug, I
started printing out the pivots in the program. The started
out as normal numbers like 1 or -10, the suddenly dropped to
about 1e-7, then later to 1e-14, and then:
k 82 pivot -1.8666e-20
k 83 pivot -2.96595e-14
k 84 pivot 2.46156e-14
k 85 pivot 2.40541e-14
k 86 pivot -4.99053e-14
k 87 pivot 1.7579e-14
k 88 pivot 1.69295e-14
k 89 pivot -1.56396e-14
k 90 pivot 1.37869e-14
k 91 pivot -3.10221e-14
k 92 pivot 2.35206e-14
k 93 pivot 1.32175e-14
k 94 pivot -7.77593e-15
k 95 pivot 1.34815e-14
k 96 pivot -1.02589e-21
k 97 pivot 4.27131e-22
k 98 pivot 1.22101e-21
k 99 pivot -7.12407e-22
k 100 pivot -1.75579e-21
k 101 pivot 3.13343e-21
k 102 pivot -6.99946e-22
k 103 pivot 3.82048e-22
k 104 pivot 8.05538e-22
k 105 pivot -1.18164e-21
k 106 pivot -6.349e-22
k 107 pivot -2.48245e-21
k 108 pivot -8.89452e-22
k 109 pivot -8.23235e-22
k 110 pivot 4.40549e-21
k 111 pivot 1.12387e-21
k 112 pivot -4.78853e-22
k 113 pivot 4.38739e-22
k 114 pivot 7.3868e-28
SIGFPE 8: numerical exception, CHK, or TRAP
stopped at daxpy+0x18c: movl a4@(0xe10),a3@
Those sudden drops were certainly perplexing - almost full
word width, as if the matrix were actually exactly singular.
Could there be a bug in the matrix generator routine (mat-
gen) causing some wild data to be thrown into the pot? I
looked and found a perfectly conventional portable linear
congruential random number generator:
subroutine matgen(a,lda,n,b,norma)
REAL a(lda,1),b(1),norma
c
init = 1325
norma = 0.0
do 30 j = 1,n
do 20 i = 1,n
init = mod(3125*init,65536)
a(i,j) = (init - 32768.0)/16384.0
norma = max(a(i,j), norma)
20 continue
30 continue
Now you have all the clues. If anybody asks I'll post
the solution in next week's issue.
------------------------------
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