Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

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.
Posted: 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

1. C. Beltrán and L. M. Pardo, Estimates on the distribution of the condition number of singular matrices, Found. Comput. Math. 7 (2007), no. 1, 87–134. MR 2283343 (2008b:65059), http://dx.doi.org/10.1007/s10208-005-0176-2
2. Adi Ben-Israel and Thomas N. E. Greville, Generalized inverses, 2nd ed., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 15, Springer-Verlag, New York, 2003. Theory and applications. MR 1987382 (2004b:15008)
3. Lenore Blum, Lectures on a theory of computation and complexity over the reals (or an arbitrary ring), 1989 lectures in complex systems (Santa Fe, NM, 1989) Santa Fe Inst. Stud. Sci. Complexity Lectures, II, Addison-Wesley, Redwood City, CA, 1990, pp. 1–47. MR 1104440 (92h:68027)
4. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636 (99a:68070)
5. Jacek Bochnak, Michel Coste, and Marie-Françoise Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36, Springer-Verlag, Berlin, 1998. Translated from the 1987 French original; Revised by the authors. MR 1659509 (2000a:14067)
6. Peter Bürgisser, Felipe Cucker, and Martin Lotz, General formulas for the smoothed analysis of condition numbers, C. R. Math. Acad. Sci. Paris 343 (2006), no. 2, 145–150 (English, with English and French summaries). MR 2243310 (2007b:65147), http://dx.doi.org/10.1016/j.crma.2006.05.014
7. Peter Bürgisser, Felipe Cucker, and Martin Lotz, Smoothed analysis of complex conic condition numbers, J. Math. Pures Appl. (9) 86 (2006), no. 4, 293–309 (English, with English and French summaries). MR 2257845 (2007h:65040), http://dx.doi.org/10.1016/j.matpur.2006.06.001
8. S.L. Campbell and C.D. Meyer.
Generalized Inverse of Linear Transformations.
Pitman, 1979.
9. Shiing-shen Chern, On the kinematic formula in integral geometry, J. Math. Mech. 16 (1966), 101–118. MR 0198406 (33 #6564)
10. Dennis Cheung and Felipe Cucker, A note on level-2 condition numbers, J. Complexity 21 (2005), no. 3, 314–319. MR 2138441 (2006a:65201), http://dx.doi.org/10.1016/j.jco.2004.06.004
11. F. Cucker, H. Diao, and Y. Wei, Smoothed analysis of some condition numbers, Numer. Linear Algebra Appl. 13 (2006), no. 1, 71–84. MR 2194973 (2006k:65114), http://dx.doi.org/10.1002/nla.464
12. 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 (88i:15014), http://dx.doi.org/10.1007/BF01400115
13. James W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), no. 182, 449–480. MR 929546 (89g:65062), http://dx.doi.org/10.1090/S0025-5718-1988-0929546-7
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. Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570 (90d:65055)
17. Alfred Gray, Tubes, Addison-Wesley Publishing Company Advanced Book Program, Redwood City, CA, 1990. MR 1044996 (92d:53002)
18. Ralph Howard, The kinematic formula in Riemannian homogeneous spaces, Mem. Amer. Math. Soc. 106 (1993), no. 509, vi+69. MR 1169230 (94d:53114)
19. E. Kostlan, On the distribution of roots of random polynomials, From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990), Springer, New York, 1993, pp. 419–431. MR 1246137
20. J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280. MR 0161339 (28 #4547)
21. 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
22. 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 (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. Michael Shub and Steve Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459–501. MR 1175980 (93k:65045), http://dx.doi.org/10.1090/S0894-0347-1993-1175980-4
25. M. Shub and S. Smale, Complexity of Bezout’s theorem. II. Volumes and probabilities, Computational algebraic geometry (Nice, 1992) Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 267–285. MR 1230872 (94m:68086)
26. Michael Shub and Steve Smale, Complexity of Bezout’s theorem. III. Condition number and packing, J. Complexity 9 (1993), no. 1, 4–14. Festschrift for Joseph F. Traub, Part I. MR 1213484 (94g:65152), http://dx.doi.org/10.1006/jcom.1993.1002
27. M. Shub and S. Smale, Complexity of Bezout’s theorem. V. Polynomial time, Theoret. Comput. Sci. 133 (1994), no. 1, 141–164. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294430 (96d:65091), http://dx.doi.org/10.1016/0304-3975(94)90122-8
28. Michael Shub and Steve Smale, Complexity of Bezout’s theorem. IV. Probability of success; extensions, SIAM J. Numer. Anal. 33 (1996), no. 1, 128–148. MR 1377247 (97k:65310), http://dx.doi.org/10.1137/0733008
29. 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/S0273-0979-1981-14858-8
30. Steve Smale, Complexity theory and numerical analysis, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 523–551. MR 1489262 (99d:65385)
31. Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms, (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 597–606. MR 1989210 (2004d:90138)
32. Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of termination of linear programming algorithms, Math. Program. 97 (2003), no. 1-2, Ser. B, 375–404. ISMP, 2003 (Copenhagen). MR 2004403 (2005b:90069)
33. Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385–463 (electronic). MR 2145860 (2006f:90029), http://dx.doi.org/10.1145/990308.990310
34. Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms and heuristics: progress and open questions, Foundations of computational mathematics, Santander 2005, London Math. Soc. Lecture Note Ser., vol. 331, Cambridge Univ. Press, Cambridge, 2006, pp. 274–342. MR 2277110 (2008a:68261), http://dx.doi.org/10.1017/CBO9780511721571.010
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 Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press Inc., Boston, MA, 1990. MR 1061154 (92a:65017)
38. R. Sulanke and P. Wintgen, Differentialgeometrie und Faserbündel, Birkhäuser Verlag, Basel, 1972 (German). Lehrbücher und Monographien aus dem Gebiete der exakten Wissenschaften, Mathematische Reihe, Band 48. MR 0413153 (54 #1274)
39. John A. Thorpe, Elementary topics in differential geometry, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1994. Corrected reprint of the 1979 original. MR 1329997 (95m:53002)
40. A. M. Turing, Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math. 1 (1948), 287–308. MR 0028100 (10,405c)
41. John von Neumann and H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021–1099. MR 0024235 (9,471b)
42. 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
43. H. Weyl.
The Theory of Groups and Quantum Mechanics.
Dover, New York, 1950.
44. J. H. Wilkinson, Note on matrices with a very ill-conditioned eigenproblem, Numer. Math. 19 (1972), 176–178. MR 0311092 (46 #10188)
45. Richard Wongkew, Volumes of tubular neighbourhoods of real algebraic varieties, Pacific J. Math. 159 (1993), no. 1, 177–184. MR 1211391 (94e:14073)
46. Mario Wschebor, Smoothed analysis of 𝜅(𝐴), J. Complexity 20 (2004), no. 1, 97–107. MR 2031560 (2005g:15041), http://dx.doi.org/10.1016/j.jco.2003.09.003

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|