Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

The probability that a slightly perturbed numerical analysis problem is difficult


Authors: Peter Bürgisser, Felipe Cucker and Martin Lotz
Journal: Math. Comp. 77 (2008), 1559-1583
MSC (2000): Primary 65Y20; Secondary 65F35, 65H20.
DOI: https://doi.org/10.1090/S0025-5718-08-02060-7
Published electronically: January 30, 2008
MathSciNet review: 2398780
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove a general theorem providing smoothed analysis estimates for conic condition numbers of problems of numerical analysis. Our probability estimates depend only on geometric invariants of the corresponding sets of ill-posed inputs. Several applications to linear and polynomial equation solving show that the estimates obtained in this way are easy to derive and quite accurate. The main theorem is based on a volume estimate of $ \varepsilon$-tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a spherical disk of radius $ \sigma$. Besides $ \varepsilon$ and $ \sigma$, this bound depends only on the dimension of the sphere and on the degree of the defining equations.


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

  • 1. C. Beltrán and L.M. Pardo.
    Estimates on the distribution of the condition number of singular matrices.
    Found. Comput. Math., 7:87-134, 2007. MR 2283343 (2008b:65059)
  • 2. A. Ben-Israel and T.N.E. Greville.
    Generalized Inverses: Theory and Applications.
    Springer-Verlag, 2nd edition, 2003. MR 1987382 (2004b:15008)
  • 3. L. Blum.
    Lectures on a theory of computation and complexity over the reals (or an arbitrary ring).
    In E. Jen, editor, Lectures in the Sciences of Complexity II, pages 1-47. Addison-Wesley, 1990. MR 1104440 (92h:68027)
  • 4. L. Blum, F. Cucker, M. Shub, and S. Smale.
    Complexity and Real Computation.
    Springer, 1998. MR 1479636 (99a:68070)
  • 5. J. Bochnak, M. Coste, and M.-F. Roy.
    Real algebraic geometry, volume 36 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3).
    Springer-Verlag, Berlin, 1998. MR 1659509 (2000a:14067)
  • 6. P. Bürgisser, F. Cucker, and M. Lotz.
    General formulas for the smoothed analysis of condition numbers.
    C. R. Acad. Sc. Paris, 343:145-150, 2006. MR 2243310 (2007b:65147)
  • 7. P. Bürgisser, F. Cucker, and M. Lotz.
    Smoothed analysis of complex conic condition numbers.
    J. Math. Pures et Appl., 86:293-309, 2006. MR 2257845 (2007h:65040)
  • 8. S.L. Campbell and C.D. Meyer.
    Generalized Inverse of Linear Transformations.
    Pitman, 1979.
  • 9. S.-S. Chern.
    On the kinematic formula in integral geometry.
    J. Math. Mech., 16:101-118, 1966. MR 0198406 (33:6564)
  • 10. D. Cheung and F. Cucker.
    A note on level-2 condition numbers.
    J. of Complexity, 21:314-319, 2005. MR 2138441 (2006a:65201)
  • 11. F. Cucker, H. Diao, and Y. Wei.
    Smoothed analysis of some condition numbers.
    Numer. Lin. Alg. Appl., 13:71-84, 2005. MR 2194973 (2006k:65114)
  • 12. J. Demmel.
    On condition numbers and the distance to the nearest ill-posed problem.
    Numer. Math., 51:251-289, 1987. MR 895087 (88i:15014)
  • 13. J. Demmel.
    The probability that a numerical analysis problem is difficult.
    Math. Comp., 50:449-480, 1988. MR 929546 (89g:65062)
  • 14. J. Dunagan, D.A. Spielman, and S.-H. Teng.
    Smoothed analysis of Renegar's condition number for linear programming.
    Preprint available at http://theory.lcs.mit.edu/~spielman, 2003.
  • 15. C. Eckart and G. Young.
    The approximation of one matrix by another of lower rank.
    Psychometrika, 1:211-218, 1936.
  • 16. G. Golub and C. Van Loan.
    Matrix Computations.
    John Hopkins Univ. Press, 1989. MR 1002570 (90d:65055)
  • 17. A. Gray.
    Tubes.
    Addison-Wesley Publishing Company Advanced Book Program, Redwood City, CA, 1990. MR 1044996 (92d:53002)
  • 18. R. Howard.
    The kinematic formula in Riemannian homogeneous spaces.
    Mem. Amer. Math. Soc., 106(509):vi+69, 1993. MR 1169230 (94d:53114)
  • 19. E. Kostlan.
    On the distribution of the roots of random polynomials.
    In M. Hirsch, J.E. Marsden, and M. Shub, editors, From Topology to Computation: Proceedings of the Smalefest, pages 419-431. Springer-Verlag, 1993. MR 1246137
  • 20. J. Milnor.
    On the Betti numbers of real varieties.
    In Proc. AMS, volume 15, pages 275-280, 1964. MR 0161339 (28:4547)
  • 21. J. Renegar.
    On the efficiency of Newton's method in approximating all zeros of systems of complex polynomials.
    Math. of Oper. Research, 12:121-148, 1987. MR 882846 (88j:65112)
  • 22. L. A. Santaló.
    Integral geometry and geometric probability.
    Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. MR 0433364 (55:6340)
  • 23. I. R. Shafarevich.
    Basic algebraic geometry.
    Springer-Verlag, New York, 1974.
    Translated from the Russian by K. A. Hirsch, Die Grundlehren der mathematischen Wissenschaften, Band 213. MR 0366917 (51:3163)
  • 24. M. Shub and S. Smale.
    Complexity of Bézout's theorem I: geometric aspects.
    J. Amer. Math., 6:459-501, 1993. MR 1175980 (93k:65045)
  • 25. M. Shub and S. Smale.
    Complexity of Bézout's theorem II: volumes and probabilities.
    In F. Eyssette and A. Galligo, editors, Computational Algebraic Geometry, volume 109 of Progress in Mathematics, pages 267-285. Birkhäuser, 1993. MR 1230872 (94m:68086)
  • 26. M. Shub and S. Smale.
    Complexity of Bézout's theorem III: condition number and packing.
    Journal of Complexity, 9:4-14, 1993. MR 1213484 (94g:65152)
  • 27. M. Shub and S. Smale.
    Complexity of Bézout's theorem V: polynomial time.
    Theoretical Computer Science, 133:141-164, 1994. MR 1294430 (96d:65091)
  • 28. M. Shub and S. Smale.
    Complexity of Bézout's theorem IV: probability of success; extensions.
    SIAM J. of Numer. Anal., 33:128-148, 1996. MR 1377247 (97k:65310)
  • 29. S. Smale.
    The fundamental theorem of algebra and complexity theory.
    Bull. Amer. Math. Soc., 4:1-36, 1981. MR 590817 (83i:65044)
  • 30. S. Smale.
    Complexity theory and numerical analysis.
    In A. Iserles, editor, Acta Numerica, pages 523-551. Cambridge University Press, 1997. MR 1489262 (99d:65385)
  • 31. D.A. Spielman and S.-H. Teng.
    Smoothed analysis of algorithms.
    In Proceedings of the International Congress of Mathematicians, volume I, pages 597-606, 2002. MR 1989210 (2004d:90138)
  • 32. D.A. Spielman and S.-H. Teng.
    Smoothed analysis of termination of linear programming algorithms.
    Math. Programm. Series B, 97:375-404, 2003. MR 2004403 (2005b:90069)
  • 33. D.A. Spielman and S.-H. Teng.
    Smoothed analysis: Why the simplex algorithm usually takes polynomial time.
    Journal of the ACM, 51(3):385-463, 2004. MR 2145860 (2006f:90029)
  • 34. D.A.. Spielman and S.-H. Teng.
    Smoothed analysis of algorithms and heuristics.
    In Foundations of Computational Mathematics, Santander 2005, volume 331 of London Mathematical Society, Lecture Note Series, pages 274-342. Cambridge University Press, 2006. MR 2277110
  • 35. M. Spivak.
    A comprehensive introduction to differential geometry. Vol. I.
    Publish or Perish Inc., Wilmington, Del., second edition, 1979.
  • 36. M. Spivak.
    A comprehensive introduction to differential geometry. Vol. III.
    Publish or Perish Inc., Wilmington, Del., second edition, 1979.
  • 37. G.W. Stewart and J. Sun.
    Matrix Perturbation Theory.
    Academic Press, 1990. MR 1061154 (92a:65017)
  • 38. R. Sulanke and P. Wintgen.
    Differentialgeometrie und Faserbündel.
    Birkhäuser Verlag, Basel, 1972.
    Lehrbücher und Monographien aus dem Gebiete der exakten Wissenschaften, Mathematische Reihe, Band 48. MR 0413153 (54:1274)
  • 39. J. A. Thorpe.
    Elementary topics in differential geometry.
    Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1994. MR 1329997 (95m:53002)
  • 40. A.M. Turing.
    Rounding-off errors in matrix processes.
    Quart. J. Mech. Appl. Math., 1:287-308, 1948. MR 0028100 (10:405c)
  • 41. J. von Neumann and H.H. Goldstine.
    Numerical inverting matrices of high order.
    Bull. Amer. Math. Soc., 53:1021-1099, 1947. MR 0024235 (9:471b)
  • 42. H. Weyl.
    On the Volume of Tubes.
    Amer. J. Math., 61(2):461-472, 1939. MR 1507388
  • 43. H. Weyl.
    The Theory of Groups and Quantum Mechanics.
    Dover, New York, 1950.
  • 44. J. Wilkinson.
    Note on matrices with a very ill-conditioned eigenproblem.
    Numer. Math., 19:176-178, 1972. MR 0311092 (46:10188)
  • 45. R. Wongkew.
    Volumes of tubular neighbourhoods of real algebraic varieties.
    Pacific J. of Mathematics, 159:177-184, 2003. MR 1211391 (94e:14073)
  • 46. M. Wschebor.
    Smoothed analysis of $ \kappa(a)$.
    J. of Complexity, 20:97-107, 2004. MR 2031560 (2005g:15041)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65Y20, 65F35, 65H20.

Retrieve articles in all journals with MSC (2000): 65Y20, 65F35, 65H20.


Additional Information

Peter Bürgisser
Affiliation: Department of Mathematics, University of Paderborn, Germany
Email: pbuerg@upb.de

Felipe Cucker
Affiliation: Department of Mathematics, City University of Hong Kong, Kowloon Tong, Hong Kong
Email: macucker@cityu.edu.hk

Martin Lotz
Affiliation: Department of Mathematics, City University of Hong Kong, Kowloon Tong, Hong Kong
Email: lotzm@upb.de

DOI: https://doi.org/10.1090/S0025-5718-08-02060-7
Keywords: Condition numbers, smooth analysis, tubular neighborhoods of algebraic surfaces.
Received by editor(s): September 28, 2006
Received by editor(s) in revised form: April 23, 2007
Published electronically: January 30, 2008
Additional Notes: Part of these results were announced in C.R. Acad. Sci. Paris, Ser. I 343 (2006) 145–150.
The first author was partially supported by DFG grant BU 1371.
The second and third authors were partially supported by CityU SRG grant 7001860.
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society