On the bit-complexity of sparse polynomial and series multiplication (Q1930169)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the bit-complexity of sparse polynomial and series multiplication
scientific article

    Statements

    On the bit-complexity of sparse polynomial and series multiplication (English)
    0 references
    0 references
    0 references
    10 January 2013
    0 references
    The authors compare several classical and new algorithms for the multiplication of multivariate polynomials and power series regarding their asymptotic complexity. It is assumed that the support of the product is known or has a known bound. Often to know the support of the coefficients in the product is the most difficult part for sparse representations. So the emphasis is on the computation of the coefficients of the product. First classical algorithms for sparse and dense polynomials are recalled, including the Kronecker substitution technique as well as a naive algorithm for the multiplication of power series. Then a discussion is given for the sparse multiplication of polynomials for different possible coefficient fields (finite field, integers, rationals, floating point,\dots). For dense truncated power series (which may be considered as sparse infinite series), also the support is known, and efficient algorithms exist. Finally a section is devoted to counting the number of absolutely irreducible factors. All the algorithms are analyzed for their asymptotic complexity, but they are also implemented in C++ and tables with timings are included. Because of the many components of the methods, there is still room for improvement by fine tuning.
    0 references
    sparse multiplication
    0 references
    power series
    0 references
    multi-point evaluation
    0 references
    polynomial factorization
    0 references
    algorithm
    0 references
    computational complexity
    0 references
    0 references
    0 references

    Identifiers