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

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

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

(5)

• The I/O complexity of Strassen's matrix multiplication with recomputation
• Iterative Toom-Cook methods for very unbalanced long integer multiplication
• Integer and polynomial multiplication: towards optimal Toom-Cook matrices
• Communication lower bounds for nested bilinear algorithms via rank expansion of Kronecker products
• On the I/O complexity of the Cocke-Younger-Kasami algorithm and of a family of related dynamic programming algorithms

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)