# On the complexity of integer matrix multiplication

(with Joris van der Hoeven)

HAL preprint (October 2014).

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

Back to the main page