Multiplicación truncada de polinomios

Abstract

A lo largo de esta memoria, estudiaremos la multiplicación truncada de polinomios, que consiste en un método de multiplicación de polinomios en el que solo nos quedamos con una cantidad del resultado completo ligada a la precisión con la que se esté trabajando. Para ello, presentaremos el algoritmo de Mulders, un método que además de calcular el producto truncado de dos polinomios resulta más eficiente que calcular los términos deseados usando el algoritmo clásico de la escuela. El algoritmo de Mulders necesita de un parámetro a la hora de aplicar un método de divide y vencerás. Estudiamos el parámetro que minimiza el número de multiplicaciones. También estudiamos una variante del algoritmo de Mulders y los comparamos. Finalmente, aplicamos estos algoritmos a un algoritmo de división con cociente y resto subcuadrático.

In this report, we study the short product of two polynomials, which consists of a method of multiplying polynomials in which only the monomials in the product up to a precision is kept. To this end, we present Mulders’ algorithm, a method that, in addition to computing the truncated product of two polynomials, is more efficient than computing only the relevant monomials using the classical schoolbook product. Mulders’ algorithm needs a parameter in order to apply a divide and conquer strategy. We study which is the optimal parameter that minimizes the number of products needed to compute the result. We also study a variant of Mulders’ algorithm and compare them. Finally, we apply these algorithms to a subquadratic algorithm that computes the quotient and remainder of two polynomials.