Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

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

Author(s): C. Beltrán; L. M. Pardo.
Journal: Math. Comp. 76 (2007), 1393-1424.
MSC (2000): Primary 65G50, 65H10
Posted: February 5, 2007
Retrieve article in: PDF

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:

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

DOI: 10.1090/S0025-5718-07-01963-1
PII: S 0025-5718(07)01963-1
Keywords: Condition number, geometric integration theory
Received by editor(s): February 6, 2006
Posted: February 5, 2007
Additional Notes: This research was partially supported by MTM2004-01167 and FPU program, Government of Spain
Copyright of article: Copyright 2007, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google