Chunky and equal-spaced polynomial multiplication

DOI10.1016/J.JSC.2010.08.013MaRDI QIDQ540329zbMATH OpenOpenAlexFDO

Authors Daniel S. Roche

Publication date 1 June 2011

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2010.08.013

zbMATH Keywords

adaptive algorithmschunky multiplicationoptimal chunk sizepolynomial multiplicationsparse polynomials

Mathematics Subject Classification ID

Algorithms for approximation of functions (65D15) Symbolic computation and algebraic computation (68W30)

Review text

A typical problem of computer algebra is addressed in this paper, namely the efficient multiplication of large polynomials. Here, a certain type of polynomials, called chunky, is considered, where there are chunks of nonvanishing coefficients near to each other (i.e., with similar powers or indices). This does not allow a worst-case analysis as is usual, but a new fairly efficient way to analyse the problem of multiplication. Algorithms are given for this new approach and it is proved that they are still of the same efficiency in the worst case as the previous methods, but are better in many other cases. (The first algorithm is about chunky multiplication, and the second algorithm about optimal chunk size computation.) The optimal chunk size is studied as well as the case when the coefficients of the polynomial are not chunky but are spaced at equal distances apart (again, from the exponent or index point of view; algorithms for equal-spaced multiplication and conversion).

Recommendations

• scientific article; zbMATH DE number 3866580
• On the choice of a multiplication algorithm for polynomials and polynomial matrices
• Parallel multiplication and powering of polynomials
• On fast multiplication of polynomials over arbitrary algebras
• scientific article; zbMATH DE number 3856407

Cites work

• A framework for adaptive sorting
• Comparing the speed of programs for sparse polynomial multiplication
• Early termination in sparse interpolation algorithms
• Fast multiplication of large numbers
• scientific article; zbMATH DE number 3322464 (Why is no real title available?)
• On fast multiplication of polynomials over arbitrary algebras
• Polynomial Division Using Dynamic Arrays, Heaps, and Packed Exponent Vectors
• The geobucket data structure for polynomials

Cited in

(5)

• Polynomial modular product verification and its implications
• scientific article; zbMATH DE number 3866580 (Why is no real title available?)
• On the complexity of multivariate blockwise polynomial multiplication
• On exact division and divisibility testing for sparse polynomials
• Fast interpolation and multiplication of unbalanced polynomials

This page was built for publication: Chunky and equal-spaced polynomial multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540329)