NA Digest Sunday, May 5, 1991 Volume 91 : Issue 18
Today's Editor: Cleve Moler
Today's Topics:
-------------------------------------------------------
From: Rahul Chattergy <rc@wiliki.eng.hawaii.edu>
Date: Mon, 29 Apr 91 15:42:08 HST
Subject: Parallel Algorithms for Optimization
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
Subject: Software Request, Constrained Minimization
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
Subject: Describing Floating Point Arithmetic
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
Subject: Numerical ODEs Mailing List
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
Subject: Interpolation on a Large Grid
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
Subject: Association for Women in Mathematics
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
Subject: Contents: Linear Algebra and Applications
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
Subject: New Journal: Computational and Graphical Statistics
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
Subject: Midwest NA Day, Final Announcement
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
**************************
-------