On the complexity of integer matrix multiplication

(with Joris van der Hoeven)

HAL preprint (October 2014).


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) / (n log n) is increasing, we prove that d × d matrices with n-bit integer entries may be multiplied in O(d2 M(n) + dω n 2O(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(d2 M(n)).

Back to the main page