Sparse resultants and straight-line programs

We prove that the sparse resultant, redefined by D'Andrea and Sombra and by Esterov as a power of the classical sparse resultant, can be evaluated in a number of steps which is polynomial in its degree, its number of variables and the size of the exponents of the monomials in the Laurent polyno...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Jeronimo, Gabriela Tali, Sabia, Juan Vicente Rafael
Publicado: 2018
Materias:
Algorithms
Sparse resultants
Straight-line programs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07477171_v87_n_p14_Jeronimo
http://hdl.handle.net/20.500.12110/paper_07477171_v87_n_p14_Jeronimo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_07477171_v87_n_p14_Jeronimo
record_format dspace
spelling paper:paper_07477171_v87_n_p14_Jeronimo2023-06-08T15:45:13Z Sparse resultants and straight-line programs Jeronimo, Gabriela Tali Sabia, Juan Vicente Rafael Algorithms Sparse resultants Straight-line programs We prove that the sparse resultant, redefined by D'Andrea and Sombra and by Esterov as a power of the classical sparse resultant, can be evaluated in a number of steps which is polynomial in its degree, its number of variables and the size of the exponents of the monomials in the Laurent polynomials involved in its definition. Moreover, we design a probabilistic algorithm of this order of complexity to compute a straight-line program that evaluates it within this number of steps. © 2017 Elsevier Ltd Fil:Jeronimo, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Sabia, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07477171_v87_n_p14_Jeronimo http://hdl.handle.net/20.500.12110/paper_07477171_v87_n_p14_Jeronimo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Algorithms
Sparse resultants
Straight-line programs
spellingShingle Algorithms
Sparse resultants
Straight-line programs
Jeronimo, Gabriela Tali
Sabia, Juan Vicente Rafael
Sparse resultants and straight-line programs
topic_facet Algorithms
Sparse resultants
Straight-line programs
description We prove that the sparse resultant, redefined by D'Andrea and Sombra and by Esterov as a power of the classical sparse resultant, can be evaluated in a number of steps which is polynomial in its degree, its number of variables and the size of the exponents of the monomials in the Laurent polynomials involved in its definition. Moreover, we design a probabilistic algorithm of this order of complexity to compute a straight-line program that evaluates it within this number of steps. © 2017 Elsevier Ltd
author Jeronimo, Gabriela Tali
Sabia, Juan Vicente Rafael
author_facet Jeronimo, Gabriela Tali
Sabia, Juan Vicente Rafael
author_sort Jeronimo, Gabriela Tali
title Sparse resultants and straight-line programs
title_short Sparse resultants and straight-line programs
title_full Sparse resultants and straight-line programs
title_fullStr Sparse resultants and straight-line programs
title_full_unstemmed Sparse resultants and straight-line programs
title_sort sparse resultants and straight-line programs
publishDate 2018
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07477171_v87_n_p14_Jeronimo
http://hdl.handle.net/20.500.12110/paper_07477171_v87_n_p14_Jeronimo
work_keys_str_mv AT jeronimogabrielatali sparseresultantsandstraightlineprograms
AT sabiajuanvicenterafael sparseresultantsandstraightlineprograms
_version_ 1768542462954962944

Ejemplares similares