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.

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

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.

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, DOI https://doi.org/10.1016/j.crma.2005.05.012

C. Beltrán and L.M. Pardo, Estimates on the distribution of the condition number of singular matrices., Found. Comput. Math. To appear (2006).

---, On Smale‘s 17th problem: A probabilistic positive answer, Found. Comput. Math. To appear (2006).

Jean-Pierre Dedieu, Estimations for the separation number of a polynomial system, J. Symbolic Comput. 24 (1997), no. 6, 683–693. MR 1487794, DOI https://doi.org/10.1006/jsco.1997.0161

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

---, Points fixes, zéros et la méthode de Newton, Collection Mathématiques et Applications, Springer, to appear 2006.

Jérôme Dégot, A condition number theorem for underdetermined polynomial systems, Math. Comp. 70 (2001), no. 233, 329–335. MR 1458220, DOI https://doi.org/10.1090/S0025-5718-00-00934-0

James W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), no. 182, 449–480. MR 929546, DOI https://doi.org/10.1090/S0025-5718-1988-0929546-7

Jean-Pierre Dedieu and Mike Shub, On simple double zeros and badly conditioned zeros of analytic functions of $n$ variables, Math. Comp. 70 (2001), no. 233, 319–327. MR 1680867, DOI https://doi.org/10.1090/S0025-5718-00-01194-7

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, DOI https://doi.org/10.7153/mia-03-26

Herbert Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York Inc., New York, 1969. MR 0257325

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).

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

Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277. MR 716823, DOI https://doi.org/10.1016/0304-3975%2883%2990002-6

Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606

W. Kahan, Huge generalized inverses of rank-deficient matrices., Unpublished Manuscript, 2000.

Myong-Hi Kim, Topological complexity of a root finding algorithm, J. Complexity 5 (1989), no. 3, 331–344. MR 1018023, DOI https://doi.org/10.1016/0885-064X%2889%2990029-0

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

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, DOI https://doi.org/10.1016/0304-3975%2894%2900065-4

David Mumford, Algebraic geometry. I, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties; Grundlehren der Mathematischen Wissenschaften, No. 221. MR 0453732

John von Neumann and H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021–1099. MR 24235, DOI https://doi.org/10.1090/S0002-9904-1947-08909-6

G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154

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, DOI https://doi.org/10.1090/S0894-0347-1993-1175980-4

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, DOI https://doi.org/10.1007/978-1-4612-2752-6_19

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, DOI https://doi.org/10.1006/jcom.1993.1002

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, DOI https://doi.org/10.1016/0304-3975%2894%2990122-8

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, DOI https://doi.org/10.1137/0733008

Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820

A. M. Turing, Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math. 1 (1948), 287–308. MR 28100, DOI https://doi.org/10.1093/qjmam/1.1.287

J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422