**Today's Topics:**

- Parallel Algorithms for Optimization
- Software Request, Constrained Minimization
- Describing Floating Point Arithmetic
- Numerical ODEs Mailing List
- Interpolation on a Large Grid
- Association for Women in Mathematics
- Contents: Linear Algebra and Applications
- New Journal: Computational and Graphical Statistics
- Midwest NA Day, Final Announcement

From: Rahul Chattergy <rc@wiliki.eng.hawaii.edu>

Date: Mon, 29 Apr 91 15:42:08 HST

Hello fellow na-netters:

I am interested in parallel algorithms for optimization. I have a

fairly good collection of references over 88 to 90. If you come across

any thing interesting in this area please drop me a note.

Thanks.

Rahul Chattergy

e-mail: rc@wiliki.eng.hawaii.edu

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

From: Bob Sloan <sloan@turing.eecs.uic.edu>

Date: Tue, 30 Apr 91 23:34:24 -0500

I'm looking for some software to solve a constrained minimization

problem with analytic objective functions and constraints. I'd prefer

something compatible with a Sun running Unix.

(I'm a complexity theory and algorithms person, but a mathematician

friend said that this was the place to write for my problem.)

Robert Sloan

Assistant Professor

EE and Computer Science Dept. (M/C 154)

University of Illinois at Chicago

Box 4348

Chicago, IL 60680

(312) 996-3422

Internet: sloan@ss1.eecs.uic.edu

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

From: James W. Demmel <demmel@wsparc.Berkeley.EDU>

Date: Mon, 29 Apr 91 11:43:08 PDT

Unfortunately, a few parameters like eps, mu, etc., are not enough to

describe the arithmetic well enough to make the algorithmic decisions

one has to make at run time. For example, in the LAPACK project we need

to know whether the arithmetic is accurate enough to support simulating

quad precision using double (using some standard tricks a la Dekker et al.).

What we need is approximately described by saying "a guard digit in

add/subtract and multiply being exact when the exact result is

representable", but it appears that a different correctness proof of

of the quad simulation is needed for many major floating point architectures

(IEEE, IBM, ...). Thus, the LAPACK code (SLAMCH) for discovering floating

point properties at run time essentially has to figure out whether we are

running on an IEEE machine, IBM, Cray, ... to decide if this quad simulation

code works. And once you know what machine you're on, you know a great deal.

(By the way, this quad simulation appears to be impossible -- at a reasonable

price -- on the Cray.)

Another issue resulting from the software changing the floating point properties

as they appear to the programmer is complex division; if this is executed in

the simplest way (without branches) then over/underflow can ruin the accuracy

for half the exponent range, essentially replacing the over/underflow

thresholds with their square roots for this operation. Some machines

implement it this way because it is faster than the safer alternative using

branches. At a higher level SNRM2 (a BLAS1 routine for computing the Euclidean

norm of a vector, as implemented by the manufacturer) may also have an

effective over/underflow threshold equal to the square root of the native

hardware for a similar reason.

SLAMCH is just one in a long series of codes written to discover floating

point properties at run time. We apparently cannot solve this problem once

and for all for two reasons:

1) New hardware and new software

2) The "mail order software" model means that one expects to be able to

move source from any machine to any other, recompile and have it work.

Thus there can be no "installation procedure" which would choose the right

data statement describing the machine at installation or compile time,

and so everything has to be done at run time.

If Fortran ever adopts a standard facility analogous to "include <math.h>",

this may not be necessary, but until then ...

Jim Demmel

Computer Science Division and Math Department

U. C. Berkeley

demmel@arpa.berkeley.edu

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

From: John Butcher <butcher@mat.aukuni.ac.nz>

Date: Sat, 4 May 91 13:05:15 NZS

Numerical ODEs mailing list

Some years ago, I put together a list of the postal addresses of people I

knew about who had an interest in numerical ordinary differential equations.

I have tried to maintain this list and to send out copies to interested

parties. I had planned to add other information such as email addresses,

telephone and FAX numbers and so forth to make the information as useful

as possible.

I now must admit my inability, because of other pressures, to keep this

up-to-date. Maybe there is no real need for it now but I know that in the

recent past it has been useful to some people.

Does anyone volunteer to take over this little project? Or are there

better ideas for keeping people with this interest aware of each others'

existence and location? One way would be to persuade SIAM to maintain

a directory with this information in it such as they do with the

Linear Algebra Special Interest group.

I would welcome suggestions and offers. I won't, of course, give up this

role unless there is someone who can convince me that he or she will make

a real effort to keep the list up-to-date and internationally-comprehensive.

John Butcher

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

From: Stewart Levin <salevin@drl.mobil.com>

Date: Tue, 30 Apr 91 08:30:32 -0500

I have a 1000x1000 uniform grid on which I'm given upt to a few hundred control

points where some physical parameter (in this case acoustic velocity) is

specified. I want to interpolate this information onto the whole grid

in such a way that 1) long wavelength variations are well preserved,

say constant and linear functions are correctly reproduced, 2) the

interpolant is reasonably smooth, say C^1 or C^2, and 3) the interpolation

is reasonably local.

One algorithm suggested in the literature is to place a suitable sized

disk around each control point, such that their union covers the whole

grid, and then form a partition of unity from radially symmetric

functions smoothly tapering to zero at the boundary of the disks.

The question I have is how to choose a disk radius that guarantees

coverage of the whole grid? Can this be worked out quickly using

the coordinates of the control points, or do I have to do a search

by, say, progressively doubling a trial radius and checking each point

on the grid for coverage? I can afford a couple million floating

point operations, I can't afford a couple hundred million flops, and

I could get by temporarily if its in the 20 million flop range.

Alternatively, would any of the ACM algorithms, such as Shepard(sp?)'s

method fit the bill?

Stewart Levin

na.slevin@na-net.stanford.edu

stew@hanauma.stanford.edu

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

From: Tricia Cross <PCROSS@LUCY.WELLESLEY.EDU>

Date: Mon, 29 Apr 1991 11:51 EDT

Attention Women Graduate Students and Postdocs*

in Applied Mathematics

The Association for Women in Mathematics is pleased to

announce an AWM Workshop on Sunday, July 7, 1991 at the

Washington Sheraton Hotel, Washington, DC immediately preceeding

the 2nd International Conference on Industrial and Applied

Mathematics. ICIAM 91 will be held from July 8 - 12, 1991 at

the same location.

FUNDING AVAILABLE

The National Science Foundation and the Office of Naval

Research are providing funds for travel and subsistence and

registration fees for 10 women graduate students and 10 women

postdocs to attend the AWM Workshop and ICIAM 91. The

workshop will provide opportunities for both groups of women

to discuss their research and to participate in a number of

other events during the day. There will be a panel to

discuss research funding, the graduate school environment,

and pipeline issues, a luncheon, and a special program and

dinner for all workshop participants.

All mathematicians (female and male) are invited to attend

the workshop even though only 20 women will be funded.

Departments are urged to encourage graduate students and

postdocs to apply for funding and if they are not successful

to help them obtain some institutional support.

APPLICATION PROCEDURES

Graduate students: To be eligible for funding a graduate

student must have begun work on a thesis problem. Send a

brief (1 page) letter describing the research area and

problem. This letter should be accompanied by a letter of

recommendation from the thesis advisor or department chair.

* Postdocs: To be eligible for funding a women must have

received her PhD within approximately the last 5 years. Send

a letter describing the area of research and a curriculum

vita.

All applications must be postmarked by May 1, 1991 and sent

to AWM, Box 178, Wellesley College, Wellesley, MA 02181.

Direct any questions regarding funding or the AWM Workshop to

Patricia N. Cross at 617-237-7517.

Tricia Cross, AWM, Executive Director

[Ed. Note: The NA News Digest got this too late for the May 1

deadline for funding, but we thought our readers might be

interested anyway. -- Cleve]

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

From: Hans Schneider <hans@math.wisc.edu>

Date: Tue, 30 Apr 91 09:33:00 CDT

LAA CONTENTS

Volume 152, July 1, 1991

Interior Point Methods for Linear Programming

Special Editors: David M. Gay, Masakazu Kojima,

and Richard Tapia

Yinyu Ye and Panos M. Pardalos

A Class of Linear Complementarity Problems Solvable in Polynomial Time

Robert M. Freund

Theoretical Efficiency of a Shifted-Barrier-Function Algorithm

for Linear Programming

D. den Hertog, C. Roos, and T. Terlaky

A Potential-Reduction Variant of Renegar's Short-Step

Path-Following Method for Linear Programming

Panos M. Pardalos, Yinyu Ye, and Chi-Geun Han

Algorithms for the Solution of Quadratic Knapsack Problems

Michael J. Todd

The Affine-Scaling Direction for Linear Programming Is a Limit of

Projective-Scaling Directions

Robert J. Vanderbei

Splitting Dense Columns in Sparse Linear Systems

K. Kim and J. L. Nazareth

The Decomposition Principle and Algorithms for Linear Programming

Masakazu Kojima and Nimrod Megiddo

The Relation Between the Path of Centers and Smale's Regularization of

the Linear Programming Problem

Kathryn Turner

Computing Projections for the Karmarkar Algorithm

Shinji Mizuno

O(nrL)-Iteration and O(n3L)-Operation Potential Reduction Algorithms

for Linear Programming

K. O. Kortanek, Florian Potra, and Yinyu Ye

On Some Efficient Interior Point Methods for Nonlinear Convex Programming

Irvin J. Lustig, Roy E. Marsten, and David F. Shanno

Computational Experience With a Primal-Dual Interior Point Method for

Linear Programming

Kurt M. Anstreicher

On Monotonicity in the Scaled Potential Algorithm for Linear Programming

Sanjay Mehrotra

On Finding a Vertex Solution Using Interior Point Methods

Stefano Herzel, Maria Cristina Recchioni, and Francesco Zirilli

A Quadratically Convergent Method for Linear Programming

David M. Gay

Massive Memory Buys Little Speed for Complete, In-Core Sparse Cholesky

Factorizations on Some Scalar Computers

Paul D. Domich, Paul T. Boggs, Janet E. Rogers and Christoph Witzgall

Optimizing Over Three-Dimensional Subspaces in an Interior-Point Method

for Linear Programming

R. A. Tapia and Yin Zhang

An Optimal-Basis Identification Technique for Interior-Point Linear

Programming Algorithms

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

Special Issues in Progress

1. Iterations in Linear Algebra and Its Applications (Dedicated to G. H. Golub,

R. S. Varga, and D. M. Young); special editors are O. Axelsson, J. de Pillis,

M. Neumann, W. Niethammer, and R. J. Plemmons. To appear as Volumes 154/155,

August/September 1991.

2. Algebraic Linear Algebra; special editors are Robert M. Guralnick, William

H. Gustafson, and Lawrence S. Levy. To appear as Volume 157, October 15, 1991.

3. Proceedings of the Auburn 1990 Matrix Theory Conference; special editors

are David Carlson and Frank Uhlig. Submission deadline: August 1, 1990.

Details provided with the conference announcement.

4. Proceedings of the Sixth Haifa Conference on Matrix Theory; special editors

are A. Berman, M. Goldberg, and D. Hershkowitz. Submission deadline: October 1,

1990. Details provided with the conference announcement.

5. Proceedings of the International Workshop on Linear Models, Experimental

Designs and Related Matrix Theory, (August 6-8, 1990, Tampere, Finland);

special editors are Jerzy K. Baksalary and George Styan. Submission deadline:

October 31, 1990. Details provided with the conference announcement.

6. Proceedings of the Second NIU Conference on Linear Algebra, Numerical Linear

Algebra and Applications, (May 3-5, 1991, Northern Illinois University, DeKalb,

Illinois); special editors are Biswa Dutta and Robert Plemmons. Submission

deadline: July 31, 1991. Details provided with the conference announcement.

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

From: William F. Eddy <bill+@andrew.cmu.edu>

Date: 2 May 91 17:46:06 GMT

The American Statistical Association, the Institute for Mathematical

Statistics, and the Interface Foundation of North America are starting

the Journal of Computational and Graphical Statistics (JCGS), with the

first issue due out in March 1992. William F. Eddy of Carnegie Mellon

University is serving as the first editor for the term 1992--1994.

The JCGS aims to improve and extend the use of computational and

graphical methods in statistics and data analysis. It will publish

articles containing original research, as well as surveys or reviews

of computational or graphical methods. The papers must represent the

best current knowledge in these fields. The presentation should be

accurate, clear, and comprehensible to readers with a statistical

background. Research papers may discuss any field that involves

significant new work in computing or graphics with value for

statistics, including (but not limited to) numerical and combinatorial

methods, programming environments, simulation, graphical displays,

graphical methods, and perception. Examples of specific topics that

are of interest but not obviously so include expert systems, symbolic

computation, and supercomputers.

Review papers of high quality are particularly solicited. Especially

valuable are papers that describe current results in areas of computing or

graphics that are unlikely to be familiar to most readers of the statistical

literature. For review papers to be useful to the audience of JCGS,

they must represent the best current knowledge in the area of

computing or graphics covered. They should be clearly understandable

to a reader interested in statistics, who has moderate, but not

necessarily expert, knowledge of computing. Practical advice,

preferably including actual examples, is particularly desirable.

Comparisons and reviews of software systems are welcome, provided that

the software is generally available and relevant to readers, and

provided that the writer can give an informed and balanced review of

available alternatives.

Papers may include explicit programs or subprograms, coded in a

programming language. The code should be self-contained so that

readers can use it directly, or sufficiently compact and clear that it

is the best way to describe the method it implements. Authors should

be prepared to provide machine-readable copies of all such code; in

any event, no code should be included in submissions unless it has

been thoroughly debugged and tested. Although code may be written in

any programming language, strong preference will be given to languages

that are widely available to readers of the journal.

All data and computer programs on which published papers are based

must be deposited in a permanent publicly accessible archive. The

data and programs must be made available to the reviewers of submitted

manuscripts. Subsequently, these items must be permanently deposited

with the editor or in a suitable computer-readable archive, such as the

Statlib archive, statlib@lib.stat.cmu.edu.

The journal will publish articles that make original contributions to

computational statistics and graphical statistics. These fields are

interpreted in the broadest possible sense; contributions could include

original theory, development of new software systems, comparison of

existing methods, reviews of specialized topics, proposals for

standards, etc.

The journal will publish book reviews, software reviews, hardware

reviews, and, occasionally, short reviews of articles in other journals.

Any manuscript submitted will be subject to editorial review.

Machine-readable submissions are preferred. You can send e-mail to

the journal editorial office at jcgs@stat.cmu.edu.

Subscription information is available from any of the sponsoring

organizations.

William F. Eddy, Department of Statistics, Carnegie Mellon University

Pittsburgh, PA 15213 Phone: (412) CMU-2725 Email: bill@stat.cmu.edu

FAX: (412) CMU-STAT

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

From: Steven Lee <slee@csrd.uiuc.edu>

Date: Sat, 4 May 91 15:55:06 CDT

FINAL ANNOUNCEMENT

for the

2nd Annual Midwest NA Day

Location: Champaign-Urbana, IL

Digital Computer Laboratory, Rm 1320

1304 W. Springfield Ave, Urbana IL

Date: Saturday, May 11 1991

8:30AM - 5:00PM

The 2nd Annual Midwest NA Day is scheduled for Saturday, May 11 1991

on the University of Illinois, Urbana-Champaign campus. The first NA

Day was held in April of last year to take special note of the

retirement of Bill Gear from the University of Illinois. This year,

the conference coincides with the May graduation ceremonies in which

Gene Golub is to receive an honorary doctorate from the University.

The list of speakers for the program includes:

Steve Ashby (Lawrence Livermore National Laboratory)

Mike Berry (University of Alabama)

Dan Boley (University of Minnesota)

Tony Chronopoulos (University of Minnesota)

Bill Gear (NEC)

Ben Leimkuhler (University of Kansas)

C.T. Pan (Northern Illinois University)

Haesun Park (University of Minnesota)

Linda Petzold (Lawrence Livermore National Laboratory)

Richard Varga (Kent State)

David Young (University of Texas at Austin)

Those who wish to be included on the electronic mailing list for news

on this event (schedule information, travel directions, etc.) should

send email to:

naday@martini.cs.uiuc.edu

Organizers: George Cybenko, Michael J. Holst, Steven Lee, Faisal

Saied, Ahmed Sameh, Paul Saylor, and Robert Skeel

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

End of NA Digest

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

-------