Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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

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

  • [BCSS98] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer-Verlag, New York, 1998. MR 1479636 (99a:68070)
  • [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] C. Beltrán and L.M. 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. MR 2152279
  • [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] J.P. Dedieu, Estimations for the separation number of a polynomial system, J. Symbolic Comput. 24 (1997), no. 6, 683-693. MR 1487794 (99b:65065)
  • [Ded01] -, 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 (2002d:65050)
  • [Ded06] -, Points fixes, zéros et la méthode de Newton, Collection Mathématiques et Applications, Springer, to appear 2006.
  • [Dég01] J. Dégot, A condition number theorem for underdetermined polynomial systems, Math. Comp. 70 (2001), no. 233, 329-335. MR 1458220 (2001f:65060)
  • [Dem88] J. W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), no. 182, 449-480. MR 929546 (89g:65062)
  • [DS01] J.P. Dedieu and M. 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 (2001f:65033)
  • [EGP00] N. Elezovic, C. Giordano, and J. Pecaric, The best bounds in Gautschi's inequality, Math. Inequal. Appl. 3 (2000), no. 2, 239-252. MR 1749300 (2001g:33001)
  • [Fed69] H. Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York Inc., New York, 1969. MR 0257325 (41:1976)
  • [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, third ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720 (97g:65006)
  • [Hei83] J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239-277. MR 716823 (85a:68062)
  • [Hig02] N.J. Higham, Accuracy and stability of numerical algorithms, second ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606 (2003g:65064)
  • [Kah00] W. Kahan, Huge generalized inverses of rank-deficient matrices., Unpublished Manuscript, 2000.
  • [Kim89] M.H. Kim, Topological complexity of a root finding algorithm, J. Complexity 5 (1989), no. 3, 331-344. MR 1018023 (90m:65058)
  • [Kun85] E. Kunz, Introduction to commutative algebra and algebraic geometry, Birkhäuser Boston Inc., Boston, MA, 1985. MR 789602 (86e:14001)
  • [Mal94] G. 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 (95g:65073)
  • [Mum76] D. Mumford, Algebraic geometry. I, Springer-Verlag, Berlin, 1976, Complex projective varieties, Grundlehren der Mathematischen Wissenschaften, No. 221. MR 0453732 (56:11992)
  • [NG47] J. 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)
  • [SS90] G. W. Stewart and J. G. Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press Inc., Boston, MA, 1990. MR 1061154 (92a:65017)
  • [SS93a] M. Shub and S. Smale, Complexity of Bézout's theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459-501. MR 1175980 (93k:65045)
  • [SS93b] -, 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)
  • [SS93c] -, 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)
  • [SS94] -, 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)
  • [SS96] -, Complexity of Bezout's theorem. IV. Probability of success; extensions, SIAM J. Numer. Anal. 33 (1996), no. 1, 128-148. MR 1377247 (97k:65310)
  • [TB97] L.N. Trefethen and D. Bau, III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820 (98k:65002)
  • [Tur48] A. M. Turing, Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math. 1 (1948), 287-308. MR 0028100 (10:405c)
  • [Wil65] J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422 (32:1894)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65G50, 65H10

Retrieve articles in all journals with MSC (2000): 65G50, 65H10

Additional Information

C. Beltrán
Affiliation: Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, E–39071 Santander, Spain

L. M. Pardo
Affiliation: Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, E–39071 Santander, Spain

Keywords: Condition number, geometric integration theory
Received by editor(s): February 6, 2006
Published electronically: February 5, 2007
Additional Notes: This research was partially supported by MTM2004-01167 and FPU program, Government of Spain
Article copyright: © Copyright 2007 American Mathematical Society

American Mathematical Society