Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The probability that a numerical analysis problem is difficult

Author: James W. Demmel
Journal: Math. Comp. 50 (1988), 449-480
MSC: Primary 65G99; Secondary 15A12, 60D05
MathSciNet review: 929546
Full-text 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 "ill-posed" one is small. For example, the closer a matrix is to the set of non-invertible matrices, the larger its condition number with respect to inversion. We show that the sets of ill-posed 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.

References [Enhancements On Off] (What's this?)

  • [1] V. I. Arnol′d, Matrices depending on parameters, Uspehi Mat. Nauk 26 (1971), no. 2(158), 101–114 (Russian). MR 0301242
  • [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 81-02-NAM-01, 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 ill-posed problem, Numer. Math. 51 (1987), no. 3, 251–289. MR 895087, 10.1007/BF01400115
  • [5] C. Eckart & G. Young, "The approximation of one matrix by another of lower rank", Psychometrika, v. 1, 1936, pp. 211-218.
  • [6] Herbert Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York Inc., New York, 1969. MR 0257325
  • [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
  • [8] Alfred Gray, An estimate for the volume of a tube about a complex hypersurface, Tensor (N.S.) 39 (1982), 303–305. MR 836947
  • [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, 10.1016/0040-9383(82)90005-2
  • [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
  • [11] R. W. Hamming, On the distribution of numbers, Bell System Tech. J. 49 (1970), 1609–1625. MR 0267809
  • [12] Harold Hotelling, Tubes and Spheres in n-Spaces, and a Class of Statistical Problems, Amer. J. Math. 61 (1939), no. 2, 440–460. MR 1507387, 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. 757-801. (Gastinel's theorem appears here.)
  • [15] W. Kahan, Conserving Confluence Curbs Ill-Condition, 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, Springer-Verlag New York, Inc., New York, 1966. MR 0203473
  • [17] Keith Kendig, Elementary algebraic geometry, Springer-Verlag, New York-Berlin, 1977. Graduate Texts in Mathematics, No. 44. MR 0447222
  • [18] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
  • [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-London-New York (Distributed by Dunod éditeur, Paris), 1968 (French). MR 0243112
  • [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, 10.1287/moor.12.1.121
  • [24] John R. Rice, A theory of condition, SIAM J. Numer. Anal. 3 (1966), 287–310. MR 0211576
  • [25] Axel Ruhe, Properties of a matrix with a very ill-conditioned eigenproblem, Numer. Math. 15 (1970), 57–60. MR 0266416
  • [26] Luis A. Santaló, Integral geometry and geometric probability, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac; Encyclopedia of Mathematics and its Applications, Vol. 1. MR 0433364
  • [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, 10.1090/S0273-0979-1981-14858-8
  • [28] Steve Smale, Algorithms for solving equations, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 172–195. MR 934223
  • [29] G. W. Stewart, Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Rev. 15 (1973), 727–764. MR 0348988
  • [30] Gabriel Stolzenberg, Volumes, limits, and extensions of analytic varieties, Lecture Notes in Mathematics, No. 19, Springer-Verlag, Berlin-New York, 1966. MR 0206337
  • [31] Paul R. Thie, The Lelong number of a point of a complex analytic set, Math. Ann. 172 (1967), 269–312. MR 0214812
  • [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, 10.2307/2371513
  • [34] J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
  • [35] J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
  • [36] J. H. Wilkinson, Note on matrices with a very ill-conditioned eigenproblem, Numer. Math. 19 (1972), 176–178. MR 0311092
  • [37] J. H. Wilkinson, On neighbouring matrices with quadratic elementary divisors, Numer. Math. 44 (1984), no. 1, 1–21. MR 745082, 10.1007/BF01389751
  • [38] J. H. Wilkinson, Sensitivity of eigenvalues, Utilitas Math. 25 (1984), 5–76. MR 752846

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

Article copyright: © Copyright 1988 American Mathematical Society