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 give a specific method to solve with quadratic complexity the linear systems arising in known algorithms to deal with the sign determination problem, both in the univariate and multivariate setting. In particular, this enables us to improve the complexity bound for sign determination in the univariate case to O(sd2log3d), where s is the number of polynomials involved and d is a bound for their degree. Previously known complexity results involve a factor of d2.376. © 2011 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Linear solving for sign determination
Autor:Perrucci, D.
Filiación:Departamento de Matemática, Universidad de Buenos Aires, Ciudad Universitaria, (1428) Buenos Aires, Argentina
Palabras clave:Complexity; Linear solving; Sign determination; Complexity; Complexity bounds; Complexity results; Linear solving; Quadratic complexity; Sign determination; Univariate; Linear systems
Año:2011
Volumen:412
Número:35
Página de inicio:4715
Página de fin:4720
DOI: http://dx.doi.org/10.1016/j.tcs.2011.05.006
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v412_n35_p4715_Perrucci

Referencias:

  • Basu, S., Pollack, R., Roy, M.-F., (2006) Algorithms in Real Algebraic Geometry, 10. , second ed. Algorithms and Computation in Mathematics Springer-Verlag Berlin
  • Ben-Or, M., Kozen, D., Reif, J., The complexity of elementary algebra and geometry (1986) J. Comput. System Sci., 32 (2), pp. 251-264. , 16th annual ACM-SIGACT symposium on the theory of computing (Washington, D.C., 1984)
  • Canny, J., Improved algorithms for sign determination and existential quantifier elimination (1993) Comput. J., 36 (5), pp. 409-418
  • Coppersmith, D., Winograd, S., Matrix multiplication via arithmetic progressions (1990) J. Symbolic Comput., 9 (3), pp. 251-280
  • Jeronimo, G., Perrucci, D., Sabia, J., On sign conditions over real multivariate polynomials (2010) Discrete Comput. Geom., 44 (1), pp. 195-222
  • Roy, M.-F., Szpirglas, A., Complexity of computation on real algebraic numbers (1990) J. Symbolic Comput., 10 (1), pp. 39-51

Citas:

---------- APA ----------
(2011) . Linear solving for sign determination. Theoretical Computer Science, 412(35), 4715-4720.
http://dx.doi.org/10.1016/j.tcs.2011.05.006
---------- CHICAGO ----------
Perrucci, D. "Linear solving for sign determination" . Theoretical Computer Science 412, no. 35 (2011) : 4715-4720.
http://dx.doi.org/10.1016/j.tcs.2011.05.006
---------- MLA ----------
Perrucci, D. "Linear solving for sign determination" . Theoretical Computer Science, vol. 412, no. 35, 2011, pp. 4715-4720.
http://dx.doi.org/10.1016/j.tcs.2011.05.006
---------- VANCOUVER ----------
Perrucci, D. Linear solving for sign determination. Theor Comput Sci. 2011;412(35):4715-4720.
http://dx.doi.org/10.1016/j.tcs.2011.05.006