Basis-Independent Polynomial Division Algorithm Applied to Division in Lagrange and
Bernstein Basis
Asian Symposium on Computer Mathematics
Proceedings of ASCM 2007
Singapore, 2007
Abstract
Division algorithms for univariate polynomials represented with respect to Lagrange
and Bernstein basis are developed. These algorithms are obtained by abstracting
from the classical polynomial division algorithm for polynomials represented with
respect to the usual power basis. It is shown that these algorithms are
quadratic in the degrees of their inputs, as in the power basis case.