Space- and time-efficient polynomial multiplication

DOI10.1145/1576702.1576743MaRDI QIDQ2883831zbMATH OpenOpenAlexFDO

Authors Daniel S. Roche

Publication date 13 May 2012

Published in Proceedings of the 2009 international symposium on Symbolic and algebraic computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1576702.1576743

Mathematics Subject Classification ID

Numerical approximation and computational geometry (primarily algorithms) (65D99) Numerical algorithms for computer arithmetic, etc. (65Y04) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3856407
• On fast multiplication of polynomials over arbitrary algebras
• Integer multiplication in time \(O(n\log n)\)
• Faster polynomial multiplication via multipoint Kronecker substitution
• Polynomial multiplication over finite fields in time O(n n)

Cited in

(14)

• Time-space efficient algorithms for computing convolutions and related problems
• On fast multiplication of polynomials over arbitrary algebras
• Dense polynomial multiplication with reduced array manipulation overhead
• Code Generation for Polynomial Multiplication
• Impact of Intel's new instruction sets on software implementation of \(GF(2)[x]\) multiplication
• Low-Weight Polynomial Form Integers for Efficient Modular Multiplication
• Fast Multiplication for Skew Polynomials
• Generic reductions for in-place polynomial multiplication
• Nearly Optimal Sparse Polynomial Multiplication
• Complexity and performance results for non FFT-based univariate polynomial multiplication
• Quantum circuits for high-degree and half-multiplication for post-quantum analysis
• In-place fast polynomial modular remainder
• In-place accumulation of fast multiplication formulae
• Faster polynomial multiplication via multipoint Kronecker substitution

This page was built for publication: Space- and time-efficient polynomial multiplication

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