Artículo
Abstract:
We consider first the zero-nonzero determination problem, which consists in determining the list of zero-nonzero conditions realized by a finite list of polynomials on a finite set ZâŠCk with C an algebraic closed field. We describe an algorithm to solve the zero-nonzero determination problem and we perform its bit complexity analysis. This algorithm, which is in many ways an adaptation of the methods used to solve the more classical sign determination problem, presents also new ideas which can be used to improve sign determination. Then, we consider the real-nonreal sign determination problem, which deals with both the sign determination and the zero-nonzero determination problem. We describe an algorithm to solve the real-nonreal sign determination problem, we perform its bit complexity analysis and we discuss this problem in a parametric context. © 2013 Elsevier Inc.
Registro:
| Documento: | Artículo |
| Título: | Zero-nonzero and real-nonreal sign determination |
| Autor: | Perrucci, D.; Roy, M.-F. |
| Filiación: | Departamento de Matemática, FCEN, Ciudad Universitaria, 1428 Buenos Aires, Argentina CONICET, Argentina IRMAR (UMR CNRS 6625), Université de Rennes 1, Campus de Beaulieu, 35042 Rennes cedex, France |
| Palabras clave: | Complexity; Polynomial equations and inequations systems; Sign determination; Bit complexity; Complexity; Finite set; Polynomial equation; Sign determination; Polynomials; Algorithms |
| Año: | 2013 |
| Volumen: | 439 |
| Número: | 10 |
| Página de inicio: | 3016 |
| Página de fin: | 3030 |
| DOI: | http://dx.doi.org/10.1016/j.laa.2013.09.010 |
| Título revista: | Linear Algebra and Its Applications |
| Título revista abreviado: | Linear Algebra Its Appl |
| ISSN: | 00243795 |
| CODEN: | LAAPA |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/paper/paper_00243795_v439_n10_p3016_Perrucci.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00243795_v439_n10_p3016_Perrucci |
Referencias:
- Basu, S., Pollack, R., Roy, M.-F., Algorithms in Real Algebraic Geometry (2006) Algorithms Comput. Math., 10. , second edition Springer-Verlag Berlin
- Basu, S., Pollack, R., Roy, M.-F., Algorithms in Real Algebraic Geometry, , http://perso.univ-rennes1.fr/marie-francoise.roy/, current online version, available at
- Canny, J., Improved algorithms for sign determination and existential quantifier elimination (1993) Comput. J., 36 (5), pp. 409-418
- Lickteig, T., Roy, M.-F., Sylvester-Habicht sequences and fast Cauchy index computations (2001) J. Symb. Comput., 31 (3), pp. 315-341
- Perrucci, D., Linear solving for sign determination (2011) Theor. Comput. Sci., 412 (35), pp. 4715-4720
- Reischert, D., Asymptotically fast computation of subresultants ISSAC '97, pp. 233-240
- Roy, M.-F., Szpirglas, A., Complexity of computation on real algebraic numbers (1990) J. Symb. Comput., 10 (1), pp. 39-51
- Von Zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge University Press New York
Citas:
---------- APA ----------
Perrucci, D. & Roy, M.-F. (2013) . Zero-nonzero and real-nonreal sign determination. Linear Algebra and Its Applications, 439(10), 3016-3030.http://dx.doi.org/10.1016/j.laa.2013.09.010
---------- CHICAGO ----------
Perrucci, D., Roy, M.-F. "Zero-nonzero and real-nonreal sign determination" . Linear Algebra and Its Applications 439, no. 10 (2013) : 3016-3030.http://dx.doi.org/10.1016/j.laa.2013.09.010
---------- MLA ----------
Perrucci, D., Roy, M.-F. "Zero-nonzero and real-nonreal sign determination" . Linear Algebra and Its Applications, vol. 439, no. 10, 2013, pp. 3016-3030.http://dx.doi.org/10.1016/j.laa.2013.09.010
---------- VANCOUVER ----------
Perrucci, D., Roy, M.-F. Zero-nonzero and real-nonreal sign determination. Linear Algebra Its Appl. 2013;439(10):3016-3030.http://dx.doi.org/10.1016/j.laa.2013.09.010
