The I/O complexity of Toom-Cook integer multiplication

DOI10.1137/1.9781611975482.123MaRDI QIDQ5236309zbMATH OpenOpenAlexFDO

Authors Gianfranco Bilardi, Lorenzo De Stefani

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975482.123

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Integer and polynomial multiplication: towards optimal Toom-Cook matrices
• The I/O complexity of Strassen's matrix multiplication with recomputation
• Faster integer multiplication
• Faster integer multiplication
• Integer multiplication in time \(O(n\log n)\)

Cited in

(4)

• Communication lower bounds for nested bilinear algorithms via rank expansion of Kronecker products
• Iterative Toom-Cook methods for very unbalanced long integer multiplication
• Integer and polynomial multiplication: towards optimal Toom-Cook matrices
• The I/O complexity of Strassen's matrix multiplication with recomputation

This page was built for publication: The I/O complexity of Toom-Cook integer multiplication

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