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
Publicado: 2011
Materias:
Complexity
Linear solving
Sign determination
Complexity bounds
Complexity results
Quadratic complexity
Univariate
Linear systems
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v412_n35_p4715_Perrucci
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 paper:paper_03043975_v412_n35_p4715_Perrucci
record_format dspace
spelling paper:paper_03043975_v412_n35_p4715_Perrucci2025-07-30T18:07:15Z Linear solving for sign determination 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. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v412_n35_p4715_Perrucci 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
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.
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
publishDate 2011
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v412_n35_p4715_Perrucci
http://hdl.handle.net/20.500.12110/paper_03043975_v412_n35_p4715_Perrucci
_version_ 1840321966575190016

Ejemplares similares