Linear solving for sign determination

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 univa...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Perrucci, D.
Formato: JOUR
Materias:
Complexity
Linear solving
Sign determination
Complexity bounds
Complexity results
Quadratic complexity
Univariate
Linear systems
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03043975_v412_n35_p4715_Perrucci
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03043975_v412_n35_p4715_Perrucci
record_format dspace
spelling todo:paper_03043975_v412_n35_p4715_Perrucci2023-10-03T15:20:24Z Linear solving for sign determination Perrucci, D. Complexity Linear solving Sign determination Complexity Complexity bounds Complexity results Linear solving Quadratic complexity Sign determination Univariate Linear systems 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03043975_v412_n35_p4715_Perrucci
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Complexity
Linear solving
Sign determination
Complexity
Complexity bounds
Complexity results
Linear solving
Quadratic complexity
Sign determination
Univariate
Linear systems
spellingShingle Complexity
Linear solving
Sign determination
Complexity
Complexity bounds
Complexity results
Linear solving
Quadratic complexity
Sign determination
Univariate
Linear systems
Perrucci, D.
Linear solving for sign determination
topic_facet Complexity
Linear solving
Sign determination
Complexity
Complexity bounds
Complexity results
Linear solving
Quadratic complexity
Sign determination
Univariate
Linear systems
description 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.
format JOUR
author Perrucci, D.
author_facet Perrucci, D.
author_sort Perrucci, D.
title Linear solving for sign determination
title_short Linear solving for sign determination
title_full Linear solving for sign determination
title_fullStr Linear solving for sign determination
title_full_unstemmed Linear solving for sign determination
title_sort linear solving for sign determination
url http://hdl.handle.net/20.500.12110/paper_03043975_v412_n35_p4715_Perrucci
work_keys_str_mv AT perruccid linearsolvingforsigndetermination
_version_ 1807320522458923008

Ejemplares similares