Chunky and equal-spaced polynomial multiplication
type: Item
instance of: scholarly article
title: Chunky and equal-spaced polynomial multiplication
zbMATH Open document ID: 1217.65038
author: Daniel S. Roche
published in: Journal of Symbolic Computation
publication date: 2011-06-01T00:00:00Z
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).
reviewed by: Martin D. Buhmann
Mathematics Subject Classification ID: 65D15
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 12Y05
zbMATH DE Number: 5903425
zbMATH Keywords: polynomial multiplication
zbMATH Keywords: adaptive algorithms
zbMATH Keywords: sparse polynomials
zbMATH Keywords: chunky multiplication
zbMATH Keywords: optimal chunk size
MaRDI profile type: Publication
full work available at URL: j.jsc.2010.08.013
OpenAlex ID: W1655250744
cites work: On fast multiplication of polynomials over arbitrary algebras
cites work: Comparing the speed of programs for sparse polynomial multiplication
cites work: Early termination in sparse interpolation algorithms
cites work: Polynomial Division Using Dynamic Arrays, Heaps, and Packed Exponent Vectors
cites work: A framework for adaptive sorting
cites work: Fast multiplication of large numbers
cites work: Q5601777
cites work: The geobucket data structure for polynomials
DOI: 10.1016/J.JSC.2010.08.013
description: scientific article; zbMATH DE number 5903425