NA Digest Sunday, October 1, 1989 Volume 89 : Issue 38
Today's Editor: Cleve Moler
Today's Topics:
-------------------------------------------------------
From: Steve Horne <horne@alcvax.pfc.mit.edu>
Date: Mon, 25 Sep 89 09:20 EDT
Subject: Software for Mixed Integer Programming Problem
I have the following problem in Mixed Integer Linear Programming.
S_0 is a point (vector) in Euclidean n-space En
A is an n x m matrix containing m vectors in n-space, m>n.
d is a vector of m distances from S_0 to each column in A
x is an unknown vector of m weights, n+1 of which are gt 0, the rest
zero
y is an unknown vector whose components contain (n+1) ones
and (m-n-1) zeros.
e is a vector with m components, all ones.
The Problem:
minimise d.y
with constraints
A.x = S_0
e.x = 1
x le y
y is (0,1)
x ge 0
In words, select from m points the n+1 points whose convex hull contains
S_0, and the sum of whose distances from S_0 is a minimum.
Typical dimensions -- S has 5-7 components; m is about 30.
I need a subroutine which solves the above, preferably in Fortran or C.
Ideally, the routine would not be a general mixed integer routine, but would
take advantage of some of the special structure. However, I'll take anything I
can get. The application is approximation of a function whose value is
known in scattered points in n-space. The subroutine(s) would become part of a
package to be used in programming the feedback control computer for Alcator
C-Mod, a tokamak under construction at MIT. Any contribution used in the
package will be carefully and gratefully acknowledged.
Thanks for your help
Steve Horne
(617) 253-8663
Horne@alcvax.pfc.mit.edu
------------------------------
From: Bette Byrne <bette%na.oxford.ac.uk@nsfnet-relay.ac.uk>
Date: Mon, 25 Sep 89 15:07:21 BST
Subject: Fluid Dynamics Conference at Oxford
12TH INTERNATIONAL CONFERENCE ON
NUMERICAL METHODS IN FLUID DYNAMICS
University of Oxford
9-13 July 1990
The conference will cover all areas of Computational Fluid Dynamics with
particular emphasis on:
Algorithm Development Parallel Computing
Hypersonic Flows Transition and Turbulence
Environmental Flows Propulsion Systems
It will be held in the Lecture Theatre of the Zoology and Psychology Building
and hosted by the Computing Laboratory, Department of Engineering Science
and the Mathematical Institute. Accommodation has been arranged in a number
of Oxford colleges and the Randolph Hotel for the duration of the Conference.
Details of this and other accommodation in Oxford or its surrounding
countryside will be made available upon request.
There will be six invited speakers as well as contributed papers. Two page
abstracts (including sample figures) of contributed papers should be submitted
before December 8, 1989: five copies are required. Notifications of acceptance
will be given by March 12, 1990. Camera ready copies of the final manuscript
will be due at the conference for publication in the proceedings. Abstracts
should be submitted according to the author's home country as follows:
USA USSR and Eastern Europe
Professor M Holt Professor V Rusanov
Dept of Mechanical Engineering Keldysh Inst Appl Mathematics
University of California Miusskaya Pl.4
Berkeley,CA 94720 125047 Moscow A-47
India, Asia, Pacific Rim Canada, Western Europe, Israel
Professor K Oshima (and all other countries)
Inst Space & Astro Science Professor R Temam
3-1-1 Yoshinodai Laboratoire D'Analyse Numerique
Sagamihara Universite Paris Sud/Bat.425
Kanagawa 229, Japan 91405 Orsay, France
A limited number of bursaries will be made available to young potential
contributors born after 9 July 1960. Applications with abstracts should be
sent to Prof. P. J. Zandbergen, Department of Applied Mathematics,
Twente University Technology, PO Box 217, 7500 AE Enschede, The Netherlands.
For further details contact:
Mrs Bette Byrne
Institute for Computational Fluid Dynamics
Oxford University Computing Laboratory
8-11 Keble Road
Oxford OX1 3QD
Tel.+44-865-273883
Fax.+44-865-273839
------------------------------
From: Chris Bischof <bischof@antares.mcs.anl.gov>
Date: Tue, 26 Sep 89 09:27:53 CDT
Subject: MATLAB User's Group
In response to an initiative by Howard Wilson from the University
of Alabama, there is now a MATLAB User group mailing list and
software repository. If you are interested in joining and are not
on the mailing list yet (i.e. you have not yet received the message
describing the setup of the user group and library), send a message
to
matlab-users-request@mcs.anl.gov
and I will add you to the mailing list and send you information
about the mailing list and library.
-- Chris Bischof
Mathematics and Computer Science Division
Argonne National Laboratory
Argonne, IL 60439
(312) 972-8875
bischof@mcs.anl.gov
------------------------------
From: Farid Alizadeh <alizadeh@UMN-CS.CS.UMN.EDU>
Date: 26 Sep 89 19:44:54 GMT
Subject: Generating Eigenvalues in a Particular Order
Here is a problem I have come across in the course of some optimization
problem.
Let A(x) be a real, symmetric n x n matrix with some or all of its entries
variables. (the vector x consists of variables from the first row to the last
and in each row from the first column to the last. Also, since the matrix
is symmetric the variable at ij entry is the same as the variable at ji.)
It is well-known that the eigenvalues of A(x) are real valued continuous
and smooth functions of x. At a given point x_0 compute the eigenvalues
and impose an arbitrary order on them; so we will get l_1(x_0), l_2(x_0),
..., l_n(x_0). Now compute the eigenvalues at new points x_1, x_2, ...,
x_k, ... The problem is that at each new point x_k I also need to compute a
permutation that reorders eigenvalues so that all eigenvalue
functions l_r are continuous and smooth. That is
l_r(x_0), l_r(x_1), ..., l_r(x_k), ...
are the values of the SAME continuous and SMOOTH function. For a simple
example consider the matrix with one variable:
1 x
x 1
Then, the eigenvalues of this matrix are:
l_1(x)=1+x
l_2(x)=1-x.
Now, for various values of x, say, QR method sometimes produces l_1(x) as the
first eigenvalue and sometimes l_2(x). This is true of just about any other
algorithm that I am aware of. (Notice that eigenvalues generated in increasing
or decreasing order do not represent smooth functions.)
The problem is this: Assuming that we can easily compute the eigenvalues
with enough precision, how can I reorder the eigenvalues at each x_k
so that the r'th eigenvalue in my list is the value of the continuous and
smooth function l_r.
Does anyone know how to do this or know of any reference?
Farid Alizadeh
CSci Dept., University of Minnesota, Mpls.
------------------------------
From: Jeff Simon <simon@ncsa.uiuc.edu>
Date: Thu, 28 Sep 89 07:22:21 CDT
Subject: Out of Core Solvers
I am seeking information on software for the solution of non-symmetric
linear systems implemented for out of core operation. The matrix is
banded and solver may be direct or iterative. I greatly appreciate
information forwarded and replies may be sent to:
simon.ncsa.uiuc.edu
Thank you,
Jeff Simon
------------------------------
From: George Corliss <georgec@marque.mu.edu>
Date: 28 Sep 89 03:06:58 GMT
Subject: Multi-dimensional Quadrature Software
I would appreciate pointers to public domain software (Fortran
preferred) for multi-dimensional quadrature. I checked netlib, but
did not see anything promising. Did I miss something? The
application in question is 4-dimensional. The integrand is
moderately smooth, of no special form.
Thanks in advance.
George Corliss, Marquette University, Milwaukee, WI 53233
georgec@marque.mu.edu, ...!uwvax!marque!georgec, 6591CORL@MUCSD.BITNET
------------------------------
From: Jerzy Wasniewski <mfci!wasniews@uunet.UU.NET>
Date: Thu, 28 Sep 89 13:23:44 EDT
Subject: Replacement of EISPACK RSP
What we need is an (IEEE 64-bit) accurate, more efficient replacement of the
RSP EISPACK routine which calculates the eigenvalues and eigenvectors of a
dense, real symmetric (packed) matrix. The algorithms used by RSP are Fortran
translations of the ALGOL TRED3, TQL2, and TRBAK3 procedures described in
Num. Math. 11 (1968) authored by Bowdler, Martin, Reinsch, and Wilkinson.
Jerzy Wasniewski
c/o Multiflow Computer, Inc.,
31 Business Park Drive,
Branford, CT 06405, U.S.A
Tel. office: 203 488 6090
Tel. home (temporary): 203 387 0171
Email address:
wasniewski@multiflow.com
or
na.wasniewski@na-net.stanford.edu
[Editor's comments: What's wrong with RSP? How much more efficient,
or more accurate, do you want or expect? RSP is pretty hard to beat.
Some speedup is available by replacing the QR accumulation of
transformations by inverse iteration using the EISPACK path TRED3,
IMTQLV, TINVIT, TRBAK3. Humberto Madrid wrote a Ph. D. thesis at
the University of New Mexico four years ago where he investigated
"perfect shifts" and "fast Givens" transformations. Jack Dongarra
and Danny Sorensen at Argonne have been touting a divide and
conquer approach for several years. Some recent contributions
by Peter Tang at Argonne and by W. Kahan at Berkeley appear to
guarantee orthogonal of eigenvectors. This approach should find
its was into LAPACK, now under development at Argonne, NYU and NAG.
I guess all this may lead to a 20 to 40% improvement in execution
time, and about the same accuracy, as RSP. That's certainly
worthwhile, but you'll have to wait a little while to have portable,
robust software comparable to that in EISPACK. --Cleve Moler.]
------------------------------
From: Jorge More <more@antares.mcs.anl.gov>
Date: Wed, 27 Sep 89 14:45:16 CDT
Subject: Position at Argonne
ARGONNE NATIONAL LABORATORY
MATHEMATICS AND COMPUTER SCIENCE DIVISION
Advanced Scientific Computing
The Mathematics and Computer Science (MCS) Division of Argonne
National Laboratory invites applications for a regular staff
position in the area of advanced scientific computing and
parallel architectures, with emphasis on numerical linear
algebra, optimization, or partial differential equations.
Qualified candidates will also be considered for the position of
Scientific Director of the Advanced Computing Research Facility.
Applicants with a Ph.D. in (applied) mathematics or computer
science will be given preference; however, outstanding candidates
with degrees from other disciplines will be considered. The
position requires extensive knowledge of methods of computational
mathematics, intimate knowledge of advanced computer
architectures, and familiarity with modern visualization
techniques. Applicants must have an established record of
research accomplishments, as evidenced by publications in
refereed journals and conference proceedings.
The MCS Division offers a stimulating environment for basic
research. Current research programs cover areas of applied
analysis, computational mathematics, and software engineering,
with emphasis on advanced scientific computing. The division
operates the Advanced Computing Research Facility (ACRF), which
comprises a network of advanced-architecture computers, ranging
from an 8-processor Alliant FX/8 to a 16,384-processor Connection
Machine CM-2. A network of Sun and NeXT workstations supports
the general computing needs of the division. Argonne's central
computing facilities include a CRAY X/MP-14; additional access to
supercomputers is provided through the major networks.
The Scientific Director of the ACRF is responsible for keeping
abreast of current developments in advanced scientific computing
and maintaining the facility and the research program that it
supports in the forefront of computer science research. The
Director is assisted by a Deputy Scientific Director. The day-
to-day operation of the facility is the responsibility of the
Manager of the MCS Computing Facilities.
Argonne is a multipurpose national laboratory operated by The
University of Chicago for the U.S. Department of Energy. It is
located 25 miles southwest of Chicago.
Applicants are requested to send a detailed resume to Rosalie L.
Bottino, Employment and Placement, Box J-MCS-37017-83, Argonne
National Laboratory, 9700 S. Cass Avenue, Argonne, IL 60439.
Further information about the position can be obtained from Dr.
Hans G. Kaper, Director, MCS Division (kaper@mcs.anl.gov),
telephone 312-972-7162. Argonne is an equal opportunity/
affirmative action employer. Women and minorities are especially
encouraged to apply.
------------------------------
From: Roger Grimes <rgrimes@atc.boeing.com>
Date: Thu, 28 Sep 89 06:45:06 PDT
Subject: Positions at Boeing Computer Services
Applied Mathematics
Boeing Computer Services
The Applied Mathematics group in Boeing Computer Services,
located in Seattle, Washington, anticipates openings in early
1990 for well qualified individuals in applied numerical
analysis, especially numerical linear algebra. We are looking
for entry level or experienced PhDs with either a dissertation or
post-graduate experience in numerical analysis and an interest in
applying this experience to challenging real world problems.
Problems will be oriented towards applications of numerical analysis
but will include parallel computing and the environment for large
scale computation, with concerns for distribution of tasks and
visualization.
Our group consists of about 40 mathematicians performing
consulting and research work for other parts of The Boeing
Company, for commercial customers, and for governmental agencies.
We require individuals capable of working independently in a
dynamic, multidisciplinary environment on complex algorithm,
analysis, and application software problems. Permanent U.S.
residency is required; U.S. citizenship is perferred.
Qualified applicants should send a resume to:
Roger G. Grimes
Manager, Computational Mathematics
Boeing Computer Services
P.O. Box 24346, M/S 7L-21
Seattle, WA 98124-0346
USA
Questions regarding the position may be sent, via e-mail, to
Roger Grimes at na.grimes@na-net.stanford.edu or
rgrimes@atc.boeing.com.
Boeing is an Equal Opportunity Employer.
------------------------------
From: Tim Kelley <ctk@matctk.ncsu.edu>
Date: Sun, 1 Oct 89 14:03:17 EDT
Subject: Position at NC State
NORTH CAROLINA STATE UNIVERSITY
Department of Mathematics
Our department intends to make a senior level appointment in PDE-related
applied mathematics, beginning in the Fall of 1990. Mathematical analysts
working on optimization or control problems and related computational
questions are especially encouraged to apply. Candidates must
have outstanding research credentials and a demonstrated competence in
teaching. Send a vita and arrange to have at least three letters of
recommendation sent to: J.C.Dunn, Search Committee Chairman, Department of
Mathematics, Box 8205, North Carolina State University, Raleigh, NC 27695-
8205. Address electronic mail inquiries to jcd@ncsumath.bitnet.
The closing date for applications is January 26, 1990. North Carolina
State University is an equal opportunity / affirmative action employer.
------------------------------
End of NA Digest
**************************
-------