On the complexity of integer matrix multiplication. (November 2018) - Harvey, David; van der Hoeven, Joris
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 ) ) .