Sparse resultants and straight-line programs
| Autor: | Gabriela Jeronimo, Juan Sabia |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Polynomial
Monomial Matemáticas SPARSE RESULTANTS 010103 numerical & computational mathematics 0102 computer and information sciences 01 natural sciences Matemática Pura purl.org/becyt/ford/1 [https] STRAIGHT-LINE PROGRAMS ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION 0101 mathematics Mathematics Discrete mathematics Algebra and Number Theory Degree (graph theory) ALGORITHMS purl.org/becyt/ford/1.1 [https] Order (ring theory) Sparse approximation Randomized algorithm Power (physics) Algebra Computational Mathematics 010201 computation theory & mathematics CIENCIAS NATURALES Y EXACTAS |
| Zdroj: | CONICET Digital (CONICET) Consejo Nacional de Investigaciones Científicas y Técnicas instacron:CONICET |
| ISSN: | 0747-7171 |
| DOI: | 10.1016/j.jsc.2017.05.005 |
| Popis: | 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. Fil: Jeronimo, Gabriela Tali. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina Fil: Sabia, Juan Vicente Rafael. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect