Computational schemes for subresultant chains (Q831961)

One of the main tools in computer algebra to deal with polynomials is Subresultant polynomials. For example, they provide fraction algorithms for computing the greatest common divisor of two polynomials, with a good behaviour under specialization and they have multiple properties over integral domains. They are also used in algorithms performing quantifier elimination or cylindrical algebraic decomposition. In summary, there have been many papers about Subresultants for the last 25 years. In this article, the authors combine several already existing algorithms for efficiently computing Subresultant polynomials (in the standard basis). Actually, three main different schemes for computing the Subresultant chain are presented. The first one takes advantage of the Half-GCD algorithm . The second one computes subresultants speculatively by modular techniques and it is also based on Half-GCD. The third one introduces an optimization for subresultant chain computations by improving Ducos' subresultant chain algorithm. An extensive and impressive experimentation can be found in Section 5, where the authors discuss several implementations and performance of their algorithms and they compare their performance against the NTL library and Maple 2020. Finally, let me add that their code is part of the Basic Polynomial Algebra Subprograms (BPAS) library available at \url{https://bpaslib.org}. For the entire collection see [Zbl 1482.68009].