The probability that a numerical analysis problem is difficult
Author:
James W. Demmel
Journal:
Math. Comp. 50 (1988), 449480
MSC:
Primary 65G99; Secondary 15A12, 60D05
MathSciNet review:
929546
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Numerous problems in numerical analysis, including matrix inversion, eigenvalue calculations and polynomial zerofinding, share the following property: The difficulty of solving a given problem is large when the distance from that problem to the nearest "illposed" one is small. For example, the closer a matrix is to the set of noninvertible matrices, the larger its condition number with respect to inversion. We show that the sets of illposed problems for matrix inversion, eigenproblems, and polynomial zerofinding all have a common algebraic and geometric structure which lets us compute the probability distribution of the distance from a "random" problem to the set. From this probability distribution we derive, for example, the distribution of the condition number of a random matrix. We examine the relevance of this theory to the analysis and construction of numerical algorithms destined to be run in finite precision arithmetic.
 [1]
V.
I. Arnol′d, Matrices depending on parameters, Uspehi
Mat. Nauk 26 (1971), no. 2(158), 101–114
(Russian). MR
0301242 (46 #400)
 [2]
E. H. Bareiss & J. L. Barlow, Probabilistic Error Analysis of Floating Point and CRD Arithmetics, Dept. of Electrical Engineering and Computer Science, Northwestern University, Report 8102NAM01, 1981.
 [3]
J. W. Demmel, A Numerical Analyst's Jordan Canonical Form, Dissertation, Computer Science Division, University of California, Berkeley, 1983.
 [4]
James
Weldon Demmel, On condition numbers and the distance to the nearest
illposed problem, Numer. Math. 51 (1987),
no. 3, 251–289. MR 895087
(88i:15014), http://dx.doi.org/10.1007/BF01400115
 [5]
C. Eckart & G. Young, "The approximation of one matrix by another of lower rank", Psychometrika, v. 1, 1936, pp. 211218.
 [6]
Herbert
Federer, Geometric measure theory, Die Grundlehren der
mathematischen Wissenschaften, Band 153, SpringerVerlag New York Inc., New
York, 1969. MR
0257325 (41 #1976)
 [7]
Gene
H. Golub and Charles
F. Van Loan, Matrix computations, Johns Hopkins Series in the
Mathematical Sciences, vol. 3, Johns Hopkins University Press,
Baltimore, MD, 1983. MR 733103
(85h:65063)
 [8]
Alfred
Gray, An estimate for the volume of a tube about a complex
hypersurface, Tensor (N.S.) 39 (1982), 303–305.
MR 836947
(87c:53126)
 [9]
Alfred
Gray, Comparison theorems for the volumes of tubes as
generalizations of the Weyl tube formula, Topology 21
(1982), no. 2, 201–228. MR 642000
(83c:53064), http://dx.doi.org/10.1016/00409383(82)900052
 [10]
Phillip
A. Griffiths, Complex differential and integral geometry and
curvature integrals associated to singularities of complex analytic
varieties, Duke Math. J. 45 (1978), no. 3,
427–512. MR
507455 (80k:53101)
 [11]
R.
W. Hamming, On the distribution of numbers, Bell System Tech.
J. 49 (1970), 1609–1625. MR 0267809
(42 #2711)
 [12]
Harold
Hotelling, Tubes and Spheres in nSpaces, and a Class of
Statistical Problems, Amer. J. Math. 61 (1939),
no. 2, 440–460. MR
1507387, http://dx.doi.org/10.2307/2371512
 [13]
D. Hough, Explaining and Ameliorating the Ill Condition of Zeros of Polynomials, Thesis, Mathematics Department, University of California, Berkeley, CA, 1977.
 [14]
W. Kahan, "Numerical linear algebra," Canad. Math. Bull., v. 9, 1966, pp. 757801. (Gastinel's theorem appears here.)
 [15]
W. Kahan, Conserving Confluence Curbs IllCondition, Technical Report 6, Computer Science Dept., University of California, Berkeley, August 4, 1972.
 [16]
Tosio
Kato, Perturbation theory for linear operators, Die
Grundlehren der mathematischen Wissenschaften, Band 132, SpringerVerlag
New York, Inc., New York, 1966. MR 0203473
(34 #3324)
 [17]
Keith
Kendig, Elementary algebraic geometry, SpringerVerlag, New
York, 1977. Graduate Texts in Mathematics, No. 44. MR 0447222
(56 #5537)
 [18]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [19]
E. Kostlan, Statistical Complexity of Numerical Linear Algebra, Dissertation, Math. Dept., University of California, Berkeley, 1985.
 [20]
P.
Lelong, Fonctions plurisousharmoniques et formes
différentielles positives, Gordon & Breach, Paris, 1968
(French). MR
0243112 (39 #4436)
 [21]
A. Ocneanu, On the Volume of Tubes About a Real Variety, unpublished report, Mathematical Sciences Research Institute, Berkeley, 1985.
 [22]
A. Ocneanu, On the Loss of Precision in Solving Large Linear Systems, Technical Report, Mathematical Sciences Research Institute, Berkeley, 1985.
 [23]
J.
Renegar, On the efficiency of Newton’s method in
approximating all zeros of a system of complex polynomials, Math.
Oper. Res. 12 (1987), no. 1, 121–148. MR 882846
(88j:65112), http://dx.doi.org/10.1287/moor.12.1.121
 [24]
John
R. Rice, A theory of condition, SIAM J. Numer. Anal.
3 (1966), 287–310. MR 0211576
(35 #2454)
 [25]
Axel
Ruhe, Properties of a matrix with a very illconditioned
eigenproblem, Numer. Math. 15 (1970), 57–60. MR 0266416
(42 #1322)
 [26]
Luis
A. Santaló, Integral geometry and geometric
probability, AddisonWesley Publishing Co., Reading,
Mass.LondonAmsterdam, 1976. With a foreword by Mark Kac; Encyclopedia of
Mathematics and its Applications, Vol. 1. MR 0433364
(55 #6340)
 [27]
Steve
Smale, The fundamental theorem of algebra and
complexity theory, Bull. Amer. Math. Soc.
(N.S.) 4 (1981), no. 1, 1–36. MR 590817
(83i:65044), http://dx.doi.org/10.1090/S027309791981148588
 [28]
Steve
Smale, Algorithms for solving equations, (Berkeley, Calif.,
1986) Amer. Math. Soc., Providence, RI, 1987, pp. 172–195. MR 934223
(89d:65060)
 [29]
G.
W. Stewart, Error and perturbation bounds for subspaces associated
with certain eigenvalue problems, SIAM Rev. 15
(1973), 727–764. MR 0348988
(50 #1482)
 [30]
Gabriel
Stolzenberg, Volumes, limits, and extensions of analytic
varieties, Lecture Notes in Mathematics, No. 19, SpringerVerlag,
Berlin, 1966. MR
0206337 (34 #6156)
 [31]
Paul
R. Thie, The Lelong number of a point of a complex analytic
set, Math. Ann. 172 (1967), 269–312. MR 0214812
(35 #5661)
 [32]
B. L. Van Der Waerden, Modern Algebra, Vol. 1, Ungar, New York, 1953.
 [33]
Hermann
Weyl, On the Volume of Tubes, Amer. J. Math.
61 (1939), no. 2, 461–472. MR
1507388, http://dx.doi.org/10.2307/2371513
 [34]
J.
H. Wilkinson, Rounding errors in algebraic processes,
PrenticeHall Inc., Englewood Cliffs, N.J., 1963. MR 0161456
(28 #4661)
 [35]
J.
H. Wilkinson, The algebraic eigenvalue problem, Clarendon
Press, Oxford, 1965. MR 0184422
(32 #1894)
 [36]
J.
H. Wilkinson, Note on matrices with a very illconditioned
eigenproblem, Numer. Math. 19 (1972), 176–178.
MR
0311092 (46 #10188)
 [37]
J.
H. Wilkinson, On neighbouring matrices with quadratic elementary
divisors, Numer. Math. 44 (1984), no. 1,
1–21. MR
745082 (85h:65096), http://dx.doi.org/10.1007/BF01389751
 [38]
J.
H. Wilkinson, Sensitivity of eigenvalues, Utilitas Math.
25 (1984), 5–76. MR 752846
(85i:65051)
 [1]
 V. I. Arnol'd, "On matrices depending on parameters", Russian Math. Surveys, v. 26, 1971, pp. 2943. MR 0301242 (46:400)
 [2]
 E. H. Bareiss & J. L. Barlow, Probabilistic Error Analysis of Floating Point and CRD Arithmetics, Dept. of Electrical Engineering and Computer Science, Northwestern University, Report 8102NAM01, 1981.
 [3]
 J. W. Demmel, A Numerical Analyst's Jordan Canonical Form, Dissertation, Computer Science Division, University of California, Berkeley, 1983.
 [4]
 J. W. Demmel, "On condition numbers and the distance to the nearest illposed problem," Numer. Math., v. 51, 1987, pp. 251289. MR 895087 (88i:15014)
 [5]
 C. Eckart & G. Young, "The approximation of one matrix by another of lower rank", Psychometrika, v. 1, 1936, pp. 211218.
 [6]
 H. Federer, Geometric Measure Theory, SpringerVerlag, Berlin and New York, 1969. MR 0257325 (41:1976)
 [7]
 G. H. Golub & C. F. Van Loan, Matrix Computations, Johns Hopkins Univ. Press, Baltimore, MD, 1983. MR 733103 (85h:65063)
 [8]
 A. Gray, "An estimate for the volume of a tube about a complex hypersurface," Tensor (N. S.), v. 39, 1982, pp. 303305. MR 836947 (87c:53126)
 [9]
 A. Gray, "Comparison theorems for the volumes of tubes as generalizations of the Weyl tube formula," Topology, v. 21, 1982, pp. 201228. MR 642000 (83c:53064)
 [10]
 P. A. Griffiths, "Complex differential and integral geometry and curvature integrals associated to singularities of complex analytic varieties," Duke Math. J., v. 45, 1978, pp. 427512. MR 507455 (80k:53101)
 [11]
 R. W. Hamming, "On the distribution of numbers," Bell System Tech. J., v. 49, 1970, pp. 16091625. MR 0267809 (42:2711)
 [12]
 H. Hotelling, "Tubes and spheres in nspaces, and a class of statistical problems," Amer. J. Math., v. 61, 1939, pp. 440460. MR 1507387
 [13]
 D. Hough, Explaining and Ameliorating the Ill Condition of Zeros of Polynomials, Thesis, Mathematics Department, University of California, Berkeley, CA, 1977.
 [14]
 W. Kahan, "Numerical linear algebra," Canad. Math. Bull., v. 9, 1966, pp. 757801. (Gastinel's theorem appears here.)
 [15]
 W. Kahan, Conserving Confluence Curbs IllCondition, Technical Report 6, Computer Science Dept., University of California, Berkeley, August 4, 1972.
 [16]
 T. Kato, Perturbation Theory for Linear Operators, SpringerVerlag, Berlin and New York, 1966. MR 0203473 (34:3324)
 [17]
 K. Kendig, Elementary Algebraic Geometry, SpringerVerlag, Berlin and New York, 1977. MR 0447222 (56:5537)
 [18]
 D. E. Knuth, The Art of Computer Programming, Vol. 2, AddisonWesley, Reading, Mass., 1969. MR 633878 (83i:68003)
 [19]
 E. Kostlan, Statistical Complexity of Numerical Linear Algebra, Dissertation, Math. Dept., University of California, Berkeley, 1985.
 [20]
 P. Lelong, Fonctions plurisousharmoniques et formes différentielles positives, Gordon and Breach, Paris, 1968. MR 0243112 (39:4436)
 [21]
 A. Ocneanu, On the Volume of Tubes About a Real Variety, unpublished report, Mathematical Sciences Research Institute, Berkeley, 1985.
 [22]
 A. Ocneanu, On the Loss of Precision in Solving Large Linear Systems, Technical Report, Mathematical Sciences Research Institute, Berkeley, 1985.
 [23]
 J. Renegar, "On the efficiency of Newton's method in approximating all zeros of systems of complex polynomials," Math. Oper. Res., v. 12, 1987, pp. 121148. MR 882846 (88j:65112)
 [24]
 J. R. Rice, "A theory of condition," SIAM J. Numer. Anal., v. 3, 1966, pp. 287310. MR 0211576 (35:2454)
 [25]
 A. Ruhe, "Properties of a matrix with a very illconditioned eigenproblem," Numer. Math., v. 15, 1970, pp. 5760. MR 0266416 (42:1322)
 [26]
 L. A. Santaló, Integral Geometry and Geometric Probability, Encyclopedia of Mathematics and Its Applications, Vol. 1, AddisonWesley, Reading, Mass., 1976. MR 0433364 (55:6340)
 [27]
 S. Smale, "The fundamental theorem of algebra and complexity theory," Bull. Amer. Math. Soc. (N. S.), v. 4, 1981, pp. 135. MR 590817 (83i:65044)
 [28]
 S. Smale, "Algorithms for solving equations," presented at the International Congress of Mathematicians, Berkeley, 1986. MR 934223 (89d:65060)
 [29]
 G. W. Stewart, "Error and perturbation bounds for subspaces associated with certain eigenvalue problems," SIAM Rev., v. 15, 1973, p. 752. MR 0348988 (50:1482)
 [30]
 G. Stolzenberg, Volumes, Limits, and Extensions of Analytic Varieties, Lecture Notes in Math., vol. 19, SpringerVerlag, Berlin and New York, 1966. MR 0206337 (34:6156)
 [31]
 P. R. Thie, "The Lelong number of a point of a complex analytic set," Math. Ann., v. 172, 1967, pp. 269312. MR 0214812 (35:5661)
 [32]
 B. L. Van Der Waerden, Modern Algebra, Vol. 1, Ungar, New York, 1953.
 [33]
 H. Weyl, "On the volume of tubes," Amer. J. Math., v. 61, 1939, pp. 461472. MR 1507388
 [34]
 J. H. Wilkinson, Rounding Errors in Algebraic Processes, PrenticeHall, Englewood Cliffs, N.J., 1963. MR 0161456 (28:4661)
 [35]
 J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, Oxford, 1965. MR 0184422 (32:1894)
 [36]
 J. H. Wilkinson, "Note on matrices with a very illconditioned eigenproblem," Numer. Math, v. 19, 1972, pp. 176178. MR 0311092 (46:10188)
 [37]
 J. H. Wilkinson, "On neighboring matrices with quadratic elementary divisors," Numer. Math., v. 44, 1984, pp. 121. MR 745082 (85h:65096)
 [38]
 J. H. Wilkinson, "Sensitivity of eigenvalues," Utilitas Math., v. 25, 1984, pp. 576. MR 752846 (85i:65051)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65G99,
15A12,
60D05
Retrieve articles in all journals
with MSC:
65G99,
15A12,
60D05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198809295467
PII:
S 00255718(1988)09295467
Article copyright:
© Copyright 1988 American Mathematical Society
