On the complexity of the Lickteig–Roy subresultant algorithm. (May 2019)

• Record Type: Journal Article
• Authors: Lecerf, Grégoire
• Is Part Of: Journal of symbolic computation. Volume 92(2019)
• Page Start: 243
• Page End: 268
• Publication Date: 2019-05
• Subjects: Resultant -- Subresultant -- Euclidean sequence -- gcd -- Half-gcd -- Algorithm; 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.2018.04.017
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In their 1996 article, Lickteig and Roy introduced a fast "divide and conquer" variant of the subresultant algorithm which avoids coefficient growth in defective cases. The present article concerns the complexity analysis of their algorithm over effective rings endowed with the partially defined division routine. We achieve essentially the same kind of complexity bound as over effective fields. As a consequence we obtain new convenient complexity bounds for gcds, especially when coefficients are in abstract polynomial rings where evaluation/interpolation schemes are not supposed to be available.