Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We show a Condition Number Theorem for the condition number of zero counting for real polynomial systems. That is, we show that this condition number equals the inverse of the normalized distance to the set of ill-posed systems (i.e., those having multiple real zeros). As a consequence, a smoothed analysis of this condition number follows. © 2009 Birkhäuser Verlag Basel/Switzerland.

Registro:

Documento: Artículo
Título:A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
Autor:Cucker, F.; Krick, T.; Malajovich, G.; Wschebor, M.
Filiación:Department of Mathematics, City University of Hong Kong, Kowloon, Hong Kong
Departamento de Matemática, Universidad de Buenos Aires and CONICET, Buenos Aires, Argentina
Departamento de Matemática Aplicada, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
Centro de Matemática, Universidad de la República, Montevideo, Uruguay
Palabras clave:Condition numbers; Polynomial systems; Smoothed analysis; Zero counting
Año:2009
Volumen:6
Número:2
Página de inicio:285
Página de fin:294
DOI: http://dx.doi.org/10.1007/s11784-009-0127-4
Título revista:Journal of Fixed Point Theory and Applications
Título revista abreviado:J. Fixed Point Theory Appl.
ISSN:16617738
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16617738_v6_n2_p285_Cucker

Referencias:

  • Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, (Springer)
  • Bürgisser, P., Cucker, F., Lotz, M., The probability that a slightly perturbed numerical analysis problem is difficult (2008) Math. Comp, 77, pp. 1559-1583
  • Cheung, D., Cucker, F., Probabilistic analysis of condition numbers for linear programming (2002) J. Optim. Theory Appl, 114, pp. 55-67
  • Cheung, D., Cucker, F., Solving linear programs with finite precision: I. Condition numbers and random programs (2004) Math. Program, 99, pp. 175-196
  • Cheung, D., Cucker, F., Hauser, R., Tail decay and moment estimates of a condition number for random linear conic systems (2005) SIAM J. Optim, 15, pp. 1237-1261
  • Cox, D., Little, J., O'Shea, D., Using Algebraic Geometry (1998) Grad. Texts In Math, 185. , Springer, New York
  • Cucker, F., Hauser, R., Lotz, M., (2008) Adversarial Smoothed Analysis, , Preprint
  • Cucker, F., Krick, T., Malajovich, G., Wschebor, M., A numerical algorithm for zero counting. I: Complexity and accuracy (2008) J. Complexity, 24, pp. 582-605
  • Cucker, F., Wschebor, M., On the expected condition number of linear programming problems (2003) Numer. Math, 94, pp. 419-478
  • D'Andrea, C., Jeronimo, G., (2008) Rational Formulas For Traces In Zero-dimensional Algebras, , Preprint
  • Demmel, J., On condition numbers and the distance to the nearest ill-posed problem (1987) Numer. Math, 51, pp. 251-289
  • Demmel, J., The probability that a numerical analysis problem is difficult (1988) Math. Comp, 50, pp. 449-480
  • Edelman, A., Eigenvalues and condition numbers of random matrices (1988) SIAM J. Matrix Anal. Appl, 9, pp. 543-556
  • Edelman, A., (1989) Eigenvalues and Condition Numbers of Random Matrices, , Ph.D. Thesis, M.I.T
  • Hauser, R., Müller, T., Conditioning of random conic systems under a general family of input distributions (2009) Found. Comput. Math, 9, pp. 335-358
  • Gel 'fand, I.M., Kapranov, M.M., Zelevinsky, A.V., (1994) Discriminants, Resultants, and Multidimensional Determinants, , Birkhäuser Boston, Boston, MA
  • Jouanolou, J.-P., Cours Dea, , University of Strasbourg
  • Malajovich, G., Rojas, J.M., High probability analysis of the condition number of sparse polynomial systems (2004) Theoret. Comput. Sci, 315, pp. 524-555
  • Rice, J.R., A theory of condition (1966) SIAM J. Numer. Anal, 3, pp. 217-232
  • Shub, M., Smale, S., Complexity of Bézout's theorem I: Geometric aspects (1993) J. Amer. Math. Soc, 6, pp. 459-501
  • Shub, M., Smale, S., Complexity of Bézout's theorem II: Volumes and probabilities (1993) Computational Algebraic Geometry, Progr. Math, 109, pp. 267-285. , In: F. Eyssette and A. Galligo (eds.), Birkhäuser
  • Spielman, D.A., Teng, S.-H., Smoothed analysis of algorithms (2002) Proc. Int. Congress Math, I, pp. 597-606. , In:, (Beijing, 2002)
  • Smale, S., On the efficiency of algorithms of analysis (1985) Bull. Amer. Math. Soc, 13, pp. 87-121
  • Smale, S., (1997) Complexity theory and numerical analysis, 6, pp. 523-551. , Acta Numer., Cambridge Univ. Press, In: A. Iserles (ed.)
  • Todd, M.J., Tunçel, L., Ye, Y., Characterizations, bounds and probabilistic analysis of two complexity measures for linear programming problems (2001) Math. Program, 90, pp. 59-69

Citas:

---------- APA ----------
Cucker, F., Krick, T., Malajovich, G. & Wschebor, M. (2009) . A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis. Journal of Fixed Point Theory and Applications, 6(2), 285-294.
http://dx.doi.org/10.1007/s11784-009-0127-4
---------- CHICAGO ----------
Cucker, F., Krick, T., Malajovich, G., Wschebor, M. "A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis" . Journal of Fixed Point Theory and Applications 6, no. 2 (2009) : 285-294.
http://dx.doi.org/10.1007/s11784-009-0127-4
---------- MLA ----------
Cucker, F., Krick, T., Malajovich, G., Wschebor, M. "A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis" . Journal of Fixed Point Theory and Applications, vol. 6, no. 2, 2009, pp. 285-294.
http://dx.doi.org/10.1007/s11784-009-0127-4
---------- VANCOUVER ----------
Cucker, F., Krick, T., Malajovich, G., Wschebor, M. A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis. J. Fixed Point Theory Appl. 2009;6(2):285-294.
http://dx.doi.org/10.1007/s11784-009-0127-4