**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

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

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

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

January 5, 1989

MEMORANDUM TO: STUDENTS AND THEIR ADVISERS

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

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

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

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

**************************

-------