On the complexity of integer matrix multiplication

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 in O(d²M(n)+d^ωn2^{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²M(n)).