Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The probability that a numerical analysis problem is difficult
HTML articles powered by AMS MathViewer

by James W. Demmel PDF
Math. Comp. 50 (1988), 449-480 Request permission

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
  • V. I. Arnol′d, On matrices depending on parameters, Uspehi Mat. Nauk 26 (1971), no. 2(158), 101–114 (Russian). MR 0301242
    • 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. J. W. Demmel, A Numerical Analyst’s Jordan Canonical Form, Dissertation, Computer Science Division, University of California, Berkeley, 1983.
  • 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, DOI 10.1007/BF01400115
    • C. Eckart & G. Young, "The approximation of one matrix by another of lower rank", Psychometrika, v. 1, 1936, pp. 211-218.
  • Herbert Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York, Inc., New York, 1969. MR 0257325
  • 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
  • Alfred Gray, An estimate for the volume of a tube about a complex hypersurface, Tensor (N.S.) 39 (1982), 303–305. MR 836947
  • 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, DOI 10.1016/0040-9383(82)90005-2
  • 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
  • R. W. Hamming, On the distribution of numbers, Bell System Tech. J. 49 (1970), 1609–1625. MR 267809, DOI 10.1002/j.1538-7305.1970.tb04281.x
  • 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, DOI 10.2307/2371512
    • D. Hough, Explaining and Ameliorating the Ill Condition of Zeros of Polynomials, Thesis, Mathematics Department, University of California, Berkeley, CA, 1977. W. Kahan, "Numerical linear algebra," Canad. Math. Bull., v. 9, 1966, pp. 757-801. (Gastinel’s theorem appears here.) W. Kahan, Conserving Confluence Curbs Ill-Condition, Technical Report 6, Computer Science Dept., University of California, Berkeley, August 4, 1972.
  • Tosio Kato, Perturbation theory for linear operators, Die Grundlehren der mathematischen Wissenschaften, Band 132, Springer-Verlag New York, Inc., New York, 1966. MR 0203473
  • Keith Kendig, Elementary algebraic geometry, Graduate Texts in Mathematics, No. 44, Springer-Verlag, New York-Berlin, 1977. MR 0447222
  • Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
    • E. Kostlan, Statistical Complexity of Numerical Linear Algebra, Dissertation, Math. Dept., University of California, Berkeley, 1985.
  • P. Lelong, Fonctions plurisousharmoniques et formes différentielles positives, Gordon & Breach, Paris-London-New York; distributed by Dunod Éditeur, Paris, 1968 (French). MR 0243112
    • A. Ocneanu, On the Volume of Tubes About a Real Variety, unpublished report, Mathematical Sciences Research Institute, Berkeley, 1985. A. Ocneanu, On the Loss of Precision in Solving Large Linear Systems, Technical Report, Mathematical Sciences Research Institute, Berkeley, 1985.
  • 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, DOI 10.1287/moor.12.1.121
  • John R. Rice, A theory of condition, SIAM J. Numer. Anal. 3 (1966), 287–310. MR 211576, DOI 10.1137/0703023
  • Axel Ruhe, Properties of a matrix with a very ill-conditioned eigenproblem, Numer. Math. 15 (1970), 57–60. MR 266416, DOI 10.1007/BF02165660
  • Luis A. Santaló, Integral geometry and geometric probability, Encyclopedia of Mathematics and its Applications, Vol. 1, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac. MR 0433364
  • Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, DOI 10.1090/S0273-0979-1981-14858-8
  • 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
  • G. W. Stewart, Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Rev. 15 (1973), 727–764. MR 348988, DOI 10.1137/1015095
  • Gabriel Stolzenberg, Volumes, limits, and extensions of analytic varieties, Lecture Notes in Mathematics, No. 19, Springer-Verlag, Berlin-New York, 1966. MR 0206337
  • Paul R. Thie, The Lelong number of a point of a complex analytic set, Math. Ann. 172 (1967), 269–312. MR 214812, DOI 10.1007/BF01351593
    • B. L. Van Der Waerden, Modern Algebra, Vol. 1, Ungar, New York, 1953.
  • Hermann Weyl, On the Volume of Tubes, Amer. J. Math. 61 (1939), no. 2, 461–472. MR 1507388, DOI 10.2307/2371513
  • J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
  • J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
  • J. H. Wilkinson, Note on matrices with a very ill-conditioned eigenproblem, Numer. Math. 19 (1972), 176–178. MR 311092, DOI 10.1007/BF01402528
  • J. H. Wilkinson, On neighbouring matrices with quadratic elementary divisors, Numer. Math. 44 (1984), no. 1, 1–21. MR 745082, DOI 10.1007/BF01389751
  • J. H. Wilkinson, Sensitivity of eigenvalues, Utilitas Math. 25 (1984), 5–76. MR 752846
Similar Articles
Additional Information
  • © Copyright 1988 American Mathematical Society
  • Journal: Math. Comp. 50 (1988), 449-480
  • MSC: Primary 65G99; Secondary 15A12, 60D05
  • DOI: https://doi.org/10.1090/S0025-5718-1988-0929546-7
  • MathSciNet review: 929546