Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6861167 | Journal of Symbolic Computation | 2018 | 8 Pages |
Abstract
Let M(n) denote the bit complexity of multiplying n-bit integers, let Ïâ(2,3] be an exponent for matrix multiplication, and let lgââ¡n be the iterated logarithm. Assuming that logâ¡d=O(n) and that M(n)/(nlogâ¡n) is increasing, we prove that dÃd matrices with n-bit integer entries may be multiplied inO(d2M(n)+dÏn2O(lgââ¡nâlgââ¡d)M(lgâ¡d)/lgâ¡d) bit operations. In particular, if n is large compared to d, say d=O(logâ¡n), then the complexity is only O(d2M(n)).
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
David Harvey, Joris van der Hoeven,