On the probability distribution of condition numbers of complete intersection varieties and the average radius of convergence of Newton’s method in the underdetermined case

Beltrán, C.; Pardo, L.

doi:10.1090/S0025-5718-07-01963-1

On the probability distribution of condition numbers of complete intersection varieties and the average radius of convergence of Newton's method in the underdetermined case

Authors: C. Beltrán and L. M. Pardo
Journal: Math. Comp. 76 (2007), 1393-1424
MSC (2000): Primary 65G50, 65H10
DOI: https://doi.org/10.1090/S0025-5718-07-01963-1
Published electronically: February 5, 2007
MathSciNet review: 2299780
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In these pages we show upper bound estimates on the probability distribution of the condition numbers of smooth complete intersection algebraic varieties. As a by-product, we also obtain lower bounds for the average value of the radius of Newton's basin of attraction in the case of positive dimension affine complex algebraic varieties.

[BCSS98] 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
[Bel06] C. Beltrán, Sobre el Problema 17 de Smale: Teoría de la Intersección y Geometría Integral, Ph.D. Thesis., Universidad de Cantabria, 2006.
[BP05] Carlos Beltrán and Luis Miguel Pardo, Upper bounds on the distribution of the condition number of singular matrices, C. R. Math. Acad. Sci. Paris 340 (2005), no. 12, 915–919 (English, with English and French summaries). MR 2152279, https://doi.org/10.1016/j.crma.2005.05.012
[BP06a] C. Beltrán and L.M. Pardo, Estimates on the distribution of the condition number of singular matrices., Found. Comput. Math. To appear (2006).
[BP06b] -, On Smale`s 17th problem: A probabilistic positive answer, Found. Comput. Math. To appear (2006).
[Ded97] Jean-Pierre Dedieu, Estimations for the separation number of a polynomial system, J. Symbolic Comput. 24 (1997), no. 6, 683–693. MR 1487794, https://doi.org/10.1006/jsco.1997.0161
[Ded01] Jean-Pierre Dedieu, Newton’s method and some complexity aspects of the zero-finding problem, Foundations of computational mathematics (Oxford, 1999) London Math. Soc. Lecture Note Ser., vol. 284, Cambridge Univ. Press, Cambridge, 2001, pp. 45–67. MR 1836614
[Ded06] -, Points fixes, zéros et la méthode de Newton, Collection Mathématiques et Applications, Springer, to appear 2006.
[Dég01] Jérôme Dégot, A condition number theorem for underdetermined polynomial systems, Math. Comp. 70 (2001), no. 233, 329–335. MR 1458220, https://doi.org/10.1090/S0025-5718-00-00934-0
[Dem88] James W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), no. 182, 449–480. MR 929546, https://doi.org/10.1090/S0025-5718-1988-0929546-7
[DS01] Jean-Pierre Dedieu and Mike Shub, On simple double zeros and badly conditioned zeros of analytic functions of 𝑛 variables, Math. Comp. 70 (2001), no. 233, 319–327. MR 1680867, https://doi.org/10.1090/S0025-5718-00-01194-7
[EGP00] Neven Elezović, Carla Giordano, and Josip Pečarić, The best bounds in Gautschi’s inequality, Math. Inequal. Appl. 3 (2000), no. 2, 239–252. MR 1749300, https://doi.org/10.7153/mia-03-26
[Fed69] Herbert Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York Inc., New York, 1969. MR 0257325
[GLSY05] M. Giusti, G. Lecerf, B. Salvy, and J.P. Yakoubsohn, On location and approximation of clusters of zeros: case of embedding dimension one, Found. Comp. Mathematics, to appear (2005).
[GVL96] Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
[Hei83] Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277. MR 716823, https://doi.org/10.1016/0304-3975(83)90002-6
[Hig02] Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606
[Kah00] W. Kahan, Huge generalized inverses of rank-deficient matrices., Unpublished Manuscript, 2000.
[Kim89] Myong-Hi Kim, Topological complexity of a root finding algorithm, J. Complexity 5 (1989), no. 3, 331–344. MR 1018023, https://doi.org/10.1016/0885-064X(89)90029-0
[Kun85] Ernst Kunz, Introduction to commutative algebra and algebraic geometry, Birkhäuser Boston, Inc., Boston, MA, 1985. Translated from the German by Michael Ackerman; With a preface by David Mumford. MR 789602
[Mal94] Gregorio Malajovich, On generalized Newton algorithms: quadratic convergence, path-following and error analysis, Theoret. Comput. Sci. 133 (1994), no. 1, 65–84. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294426, https://doi.org/10.1016/0304-3975(94)00065-4
[Mum76] David Mumford, Algebraic geometry. I, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties; Grundlehren der Mathematischen Wissenschaften, No. 221. MR 0453732
[NG47] John von Neumann and H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021–1099. MR 24235, https://doi.org/10.1090/S0002-9904-1947-08909-6
[SS90] G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
[SS93a] 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, https://doi.org/10.1090/S0894-0347-1993-1175980-4
[SS93b] 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, https://doi.org/10.1007/978-1-4612-2752-6_19
[SS93c] 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, https://doi.org/10.1006/jcom.1993.1002
[SS94] 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, https://doi.org/10.1016/0304-3975(94)90122-8
[SS96] 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, https://doi.org/10.1137/0733008
[TB97] Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820
[Tur48] A. M. Turing, Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math. 1 (1948), 287–308. MR 28100, https://doi.org/10.1093/qjmam/1.1.287
[Wil65] J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422