**Today's Topics:**

- Growth Factor Conjecture Disproved
- Use of Reusable Code by Numerical Programmers
- Position at University of Haifa
- Position at University of British Columbia
- Fellowship at Sandia National Laboraties
- Positions at Manchester University

From: Nick Higham and Nick Trefethen

<MBBGSNH%CMS.Manchester-Computing-Centre.AC.UK>

Date: Tue, 13 Nov 90 10:43:56 GMT

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

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

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

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

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

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

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

-------