NA Digest Sunday, November 18, 1990 Volume 90 : Issue 40
Today's Editor: Cleve Moler
Today's Topics:
-------------------------------------------------------
From: Nick Higham and Nick Trefethen
<MBBGSNH%CMS.Manchester-Computing-Centre.AC.UK>
Date: Tue, 13 Nov 90 10:43:56 GMT
Subject: Growth Factor Conjecture Disproved
We are very pleased to announce that Nick Gould, of the Atlas Centre at the
Rutherford Appleton Laboratory near Oxford, has disproved the longstanding
conjecture that the growth factor for Gaussian elimination with complete
pivoting applied to real N-by-N matrices is bounded by N. Using a package
LANCELOT designed for large-scale nonlinear optimization, Gould has found a
13-by-13 matrix for which the growth factor is 13.0205.
The "complete pivoting conjecture" is perhaps not very important as far as
applications are concerned, but it is undeniably one of the most famous
open problems in numerical analysis. Many well-known numerical analysts
have worked hard on it. With the new discovery Gould has shown why all
attempts to prove the conjecture have failed.
The growth factor in Gaussian elimination is the ratio of the largest
number that appears at any stage of the elimination to the largest element
in the original matrix. J.H. Wilkinson's backward error analysis of the
early 1960s showed that Gaussian elimination is numerically stable as long
as the growth factor remains small. For complete pivoting, in which the
pivot element is selected as the largest element from the whole remaining
active submatrix at each stage, Wilkinson obtained an upper bound for the
growth factor that behaves asymptotically like N**(0.5+log(N)/4).
Wilkinson noted that the bound is not sharp, that observed growth factors
are invariably of order 1, and that no matrix had been discovered for
which the growth exceeds N. In 1968 C. Cryer published the famous
conjecture.
Let g(N) denote the maximum growth factor over all real matrices of
dimension N. Previous research into the complete pivoting conjecture has
established the results g(1) = 1, g(2) = 2, g(3) = 2.25, g(4) = 4,
and g(5) < 5.005. "Record" growth factors for N = 5, 6 and 7 have been
obtained numerically by Day and Peterson, using an optimization package,
but none exceeded N. Gould's new calculations establish g(13) >= 13.0205,
and also g(14) > 14, g(15) > 16 and g(16) > 18.
The difficulty with treating the complete pivoting conjecture as an
optimization problem is that the obvious formulation, expressed in terms of
the N**2 unknown entries of the matrix, is extremely nonlinear. Gould
recognised that by taking the unknown variables to be all of the O(N**3)
matrix entries that appear throughout the elimination, one can make the
problem much closer to linear. This insight appears to have been
fundamental to his success in breaking the conjecture. The other
ingredient, the LANCELOT package, is currently under development by Gould,
Andrew Conn and Philippe Toint.
As well as settling the complete pivoting conjecture, Gould's work raises
the hope that further understanding of the behaviour of the growth factor
might be achieved with the help of numerical experiments. Several
questions remain unanswered. Chief among these is: How big can the growth
factor be for complete pivoting? We now know it can be bigger than N, but
by how much?
All of these are questions of worst-case behavior. The algorithm almost
invariably used in practice is Gaussian elimination with partial pivoting,
which uses only row interchanges rather than row and column interchanges.
Here, the problem of stability is quite different, for it has been known
for many years that the worst-case behavior is catastrophically unstable:
g(N) = 2**(N-1). Nevertheless, decades of experience and extensive
numerical experiments have shown that in practice, Gaussian elimination
with partial pivoting is highly stable, with growth factors of order N or
less for all but a tiny proportion of matrices. This phenomenon of
average-case stability is still not fully understood.
Gould's paper, titled "On growth in Gaussian elimination with complete
pivoting", will appear in 1991 in the SIAM Journal on Matrix Analysis and
Applications. His email address is nimg@ib.rl.ac.uk or
na.gould@na-net.stanford.edu.
-- Nick Higham and Nick Trefethen
------------------------------
From: Michael A. Delong <mad5c@amsun19.apma.Virginia.EDU>
Date: Fri, 9 Nov 90 00:34:16 -0500
Subject: Use of Reusable Code by Numerical Programmers
1. A large share of computer resources is used by engineers that are not
"computer people".
2. Software development & maintenance time can be reduced by employing
reusable code (numerical libraries, object-oriented programming, etc).
I'm devising a survey to gauge use of reusable code by numerical programmers.
If this is a topic that interests you, and you would like to contribute a
question (or an opinion) please e-mail me at
mad5c@virginia.edu or
mad5c@eagle.larc.nasa.gov or
mad5c@msr.epm.ornl.gov.
Thank you.
Mike Delong.
------------------------------
From: Yitzhak Weit <RSMA604%HAIFAUVM.BITNET@Forsythe.Stanford.EDU>
Date: Mon, 12 Nov 90 09:42:15 IST
Subject: Position at University of Haifa
POSITION IN COMPUTER SCIENCE AT THE UNIVERSITY OF HAIFA IN ISRAEL
The Department of Mathematics and Computer Science at the University of
Haifa, Haifa, Israel, anticipates a tenure track openning for a candidate
in computer science, starting October 1991. The department offers B.A.,
M.A., and ph.D. degrees in mathematics and in "Mathematics and Computer
Science".
Strong research and teaching ability and a ph.D in any area of computer
science are required. Send resume and list of publications plus one copy
of preprints/reprints of papers. Please supply names and mailing
addresses of three or more references (electronic addresses
and telephone and Fax numbers of these references will be appreciated).
Send applications or requests for further information to:
Prof. Yitzhak Weit, Chairman, Dept. of Mathematics and Computer Science,
University of Haifa, Mt. Carmel, Haifa 31999, Israel.
(e-mail: rsma604@haifauvm.bitnet).
------------------------------
From: Uri Ascher <ascher@cs.ubc.ca>
Date: 13 Nov 90 10:25 -0800
Subject: Position at University of British Columbia
Our Math Department has a position in Numerical Computation.
To the attached ad let me add that Vancouver is a
beautiful city, with very accessible mountains, beaches and
wilderness.
Uri Ascher
POSITION IN NUMERICAL COMPUTATION AT THE UNIVERSITY OF BRITISH COLUMBIA
The Mathematics Department at UBC is looking for outstanding
candidates for a tenure track Assistant Professorship
in Numerical Computation to begin 1 July 1991.
Exceptional candidates in other areas of Applied
Mathematics may also be considered. For an exceptionally well-
qualified candidate, this position may be upgraded to a non-
tenured junior Associate Professorship. Applicants should have a
demonstrated research record of high quality and have
demonstrated interest and ability in teaching. It is expected that a
successful candidate would become an active member of the
Institute of Applied Mathematics. Preference will be given to
candidates who have one or more years of postdoctoral
experience. This position is subject to budgetary approval. The
salary will be commensurate with experience and research
record.
Applicants should send a C.V. including list of publications,
statement of research and teaching interests and arrange for
three letters of recommendation to be sent directly to: Dr. Dale
Rolfsen, Head, Department of Mathematics, University of British
Columbia, Vancouver, B.C. Canada V6T 1Y4. Applications must be
received before January 1, 1991. In accordance with Canadian
immigration requirements, preference will be given to
Canadian citizens and permanent residents of Canada. The
University of British Columbia is committed to the Federal
Government's employment equity program and encourages
applications from all qualified individuals.
------------------------------
From: Richard C. Allen <rcallen@cs.sandia.gov>
Date: Thu, 15 Nov 90 08:04:57 MST
Subject: Fellowship at Sandia National Laboraties
APPLIED MATHEMATICAL SCIENCES RESEARCH FELLOWSHIP
Mathematics and Computational Science Department
Sandia National Laboratories
The Mathematics and Computational Sciences Department at Sandia
National Laboratories invites outstanding candidates to apply for the
1991 AMS Research Fellowship. The Fellowship is supported by the
Applied Mathematical Sciences Research Program of the U.S. Department
of Energy.
AMS Fellowships at Sandia provide an exceptional opportunity for
innovative research in scientific computing on advanced architectures,
and are intended to promote the transfer of technology from the
laboratory research environment to industry and academia through the
advanced training of new computational scientists. Candidates must be
U.S. citizens, must have earned a recent Ph.D. degree or the
equivalent in computer science or mathematics, and should have a
strong interest in advanced computing research.
Sandia's Mathematics and Computational Science Department maintains
strong programs in theoretical computer science, analytical and
computational mathematics, computational physics and engineering,
advanced computational approaches for parallel computers, graphics,
and architectures and languages. Sandia provides a unique parallel
computing environment, including a 1024-processor NCUBE/ten hypercube,
a 1024-processor NCUBE 2 hypercube, a Connection Machine-2, and
several large Cray supercomputers.
The fellowship appointment is for a period of one year, and may be
renewed for a second year. It includes a highly competitive salary,
moving expenses, and a generous professional travel allowance.
Applicants should send a resume, a statement of research goals, and
three letters of recommendation to Robert H. Banks, Division 3531-AMS,
Sandia National Laboratories, P.O. Box 5800, Albuquerque, NM 87185.
The closing date for applications is January 31, 1991, and the
position will commence during 1991.
For further information contact Richard C. Allen, Jr. at (505) 844-
2248 or by E-mail, RCALLEN@CS.SANDIA.GOV.
Equal Opportunity Employer M/F/V/H
U.S. Citizenship is Required
------------------------------
From: Nick Higham <MBBGSNH%CMS.Manchester-Computing-Centre.AC.UK>
Date: Fri, 16 Nov 90 13:44:31 GMT
Subject: Positions at Manchester University
UNIVERSITY OF MANCHESTER
TWO LECTURERS
IN
APPLIED MATHEMATICS
Applications are invited for two lectureships in Applied Mathematics.
Candidates should possess a Ph.D. and have a strong track record of
research, or have demonstrated strong research potential.
The present research interests of the Applied Mathematics Group include
fluid mechanics, solid mechanics and astrophysics, but
suitably qualified candidates will be considered in
any area of Applied Mathematics, widely interpreted.
Initial salary will be in the range 12,086-13,495 pounds per annum
and 17,455-22,311 pounds per annum.
Application forms (returnable by December 21st, 1990) are obtainable from
the Registrar, The University, Manchester, M13 9PL (Tel: 061-275 2028).
Quote reference 333/90.
The University is an Equal Opportunity Employer.
------------------------------
End of NA Digest
**************************
-------