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
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
MR Author ID:
764504
ORCID:
0000-0002-0689-8232
Email:
beltranc@unican.es
L. M. Pardo
Affiliation:
Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, E–39071 Santander, Spain
Email:
luis.pardo@unican.es
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