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:

In a recent paper (Cucker et al., 2008 [8]) we analyzed a numerical algorithm for computing the number of real zeros of a polynomial system. The analysis relied on a condition number κ(f) for the input system f. In this paper we look at κ(f) as a random variable derived from imposing a probability measure on the space of polynomial systems and give bounds for both the tail P{κ(f)>a} and the expected value E(logκ(f)). © 2011 Elsevier Inc. All rights reserved.

Registro:

Documento: Artículo
Título:A numerical algorithm for zero counting. III: Randomization and condition
Autor:Cucker, F.; Krick, T.; Malajovich, G.; Wschebor, M.
Filiación:Department of Mathematics, City University of Hong Kong, Hong Kong, Hong Kong
Departamento de Matemática, Universidad de Buenos Aires and IMAS, CONICET, Argentina
Departamento de Matemática Aplicada, Universidade Federal Do Rio de Janeiro, Brazil
Centro de Matemática, Universidad de la República, Uruguay
Palabras clave:Average-case analysis; Condition numbers; Finite precision; Rice formula; Zero counting; Average-case analysis; Condition numbers; Finite precision; Rice formula; Zero counting; Number theory; Random variables; Algorithms
Año:2012
Volumen:48
Número:1
Página de inicio:215
Página de fin:248
DOI: http://dx.doi.org/10.1016/j.aam.2011.07.001
Título revista:Advances in Applied Mathematics
Título revista abreviado:Adv. Appl. Math.
ISSN:01968858
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01968858_v48_n1_p215_Cucker

Referencias:

  • Abramowitz, M., Stegun, I., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (1964) National Bureau of Standards Appl. Math. Ser., 55
  • Azaïs, J.-M., Wschebor, M., (2009) Level Sets and Extrema of Random Processes and Fields, , John Wiley and Sons
  • Beltrán, C., Pardo, L.M., On Smales 17 problem: A probabilistic positive solution (2008) Found. Comput. Math., 8, pp. 1-43
  • Beltrán, C., Shub, M., Complexity of Bézouts theorem VII: Distance estimates in the condition metric (2009) Found. Comput. Math., 9, pp. 179-195
  • Borges, C.E., Pardo, L.M., On the probability distribution of data at points in real complete intersection varieties (2008) J. Complexity, 24, pp. 492-523
  • 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
  • Cucker, F., Smale, S., Complexity Estimates Depending on Condition and Round-Off Error (1999) Journal of the ACM, 46 (1), pp. 113-184
  • 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., Krick, T., Malajovich, G., Wschebor, M., A numerical algorithm for zero counting. II: Distance to Ill-posedness and smoothed analysis (2009) J. Fixed Point Theory Appl., 6, pp. 285-294
  • Davidson, K.R., Szarek, S.J., Local operator theory, random matrices and Banach spaces (2001) Handbook of the Geometry of Banach Spaces, pp. 317-366. , W.B. Johnson, J. Lindenstrauss, North-Holland
  • Dembo, A., Zeitouni, O., (1998) Large Deviations Techniques and Applications, , second ed. Springer-Verlag
  • Demmel, J., On condition numbers and the distance to the nearest ill-posed problem (1987) Numer. Math., 51, pp. 251-289
  • Freund, R.M., Vera, J.R., Some characterizations and properties of the "distance to ill-posedness" and the condition measure of a conic linear system (1999) Math. Program., 86, pp. 225-260
  • Gantmacher, F.R., (2000) The Theory of Matrices, , AMS/Chelsea
  • Kostlan, E., (1987) Random Polynomials and the Statistical Fundamental Theorem of Algebra, , unpublished
  • Rump, S.M., III-conditioned matrices are componentwise near to singularity (1999) SIAM Review, 41 (1), pp. 102-112. , PII S0036144598323216
  • Shub, M., Complexity of Bézouts theorem VI: Geodesics in the condition (number) metric (2009) Found. Comput. Math., 9, pp. 171-178
  • Shub, M., Smale, S., Complexity of Bézouts theorem I: Geometric aspects (1993) J. Amer. Math. Soc., 6, pp. 459-501
  • Shub, M., Smale, S., Complexity of Bézouts theorem II: Volumes and probabilities (1993) Computational Algebraic Geometry, 109, pp. 267-285. , F. Eyssette, A. Galligo, Progr. Math. Birkhäuser
  • Shub, M., Smale, S., Complexity of Bézouts theorem III: Condition number and packing (1993) J. Complexity, 9, pp. 4-14
  • Shub, M., Smale, S., Complexity of Bézouts theorem V: Polynomial time (1994) Theoret. Comput. Sci., 133, pp. 141-164
  • Shub, M., Smale, S., Complexity of Bezout's theorem IV: Probability of success; extensions (1996) SIAM Journal on Numerical Analysis, 33 (1), pp. 128-148
  • Wilkinson, J., Note on matrices with a very ill-conditioned eigenproblem (1972) Numer. Math., 19, pp. 176-178

Citas:

---------- APA ----------
Cucker, F., Krick, T., Malajovich, G. & Wschebor, M. (2012) . A numerical algorithm for zero counting. III: Randomization and condition. Advances in Applied Mathematics, 48(1), 215-248.
http://dx.doi.org/10.1016/j.aam.2011.07.001
---------- CHICAGO ----------
Cucker, F., Krick, T., Malajovich, G., Wschebor, M. "A numerical algorithm for zero counting. III: Randomization and condition" . Advances in Applied Mathematics 48, no. 1 (2012) : 215-248.
http://dx.doi.org/10.1016/j.aam.2011.07.001
---------- MLA ----------
Cucker, F., Krick, T., Malajovich, G., Wschebor, M. "A numerical algorithm for zero counting. III: Randomization and condition" . Advances in Applied Mathematics, vol. 48, no. 1, 2012, pp. 215-248.
http://dx.doi.org/10.1016/j.aam.2011.07.001
---------- VANCOUVER ----------
Cucker, F., Krick, T., Malajovich, G., Wschebor, M. A numerical algorithm for zero counting. III: Randomization and condition. Adv. Appl. Math. 2012;48(1):215-248.
http://dx.doi.org/10.1016/j.aam.2011.07.001