INVESTIGADORES
PERRUCCI Daniel Roberto
artículos
Título:
Linear Solving for Sign Determination
Autor/es:
DANIEL PERRUCCI
Revista:
THEORETICAL COMPUTER SCIENCE
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2011 vol. 412 p. 4715 - 4720
ISSN:
0304-3975
Resumen:
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(sd^2 log^3d), where s is the number of polynomials involved and d is a bound for their degree. Previously known complexity results involve a factor of d^2.376.