Sparse resultants and straight-line programs. (July 2018)

• Record Type: Journal Article
• Authors: Jeronimo, Gabriela; Sabia, Juan
• Is Part Of: Journal of symbolic computation. Volume 87(2018)
• Page Start: 14
• Page End: 27
• Publication Date: 2018-07
• Subjects: Sparse resultants -- Straight-line programs -- Algorithms; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.05.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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.