Fast Matrix Computation of Subresultant Polynomial Remainder Sequences

We present an improved (faster) variant of the matrix-triangularization subresultant prs method for the computation of a greatest common divisor of two polynomials A and B (of degrees d_A and d_B, respectively) along with their polynomial remainder sequence [1]. The computing time of our fast method is 0(n2+ßlog ∥C∥2), for standard arithmetic and 0(((n1+ß+n3 log ∥C∥)(log n+ log ∥C∥)2) for the Chinese remainder method, where n = d_A + d_B, ∥C∥ is the maximal coefficient of the two polynomials and the best known ß < 2.356. By comparison, the computing time of the old version is 0(n5 log ∥C∥2 ).Our improvement is based on the work of Malaschonok [12] who proposed a new, recursive method for the solution of systems of linear equations in integral domains with complexity Onß over the integers (same as the complexity of matrix multiplication).In this paper we present an overview of the two methods mentioned above and show how they are combined into a fast matrix method for computing polynomial remainder sequences. An example is also presented to clarify the concepts.