Subject: NA-NET distribution message

From: [email-masked]
Date: Sun, 8 Jan 89 12:26:35 PST

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

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

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

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

From: Ed Block <[email-masked]>
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 <[email-masked]>
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 [email-masked].  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 <[email-masked]>
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
	[email-masked] 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 <[email-masked]>
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 <[email-masked]>
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
**************************
-------