Let denote the bit complexity of multiplying -bit integers, let be an exponent for matrix multiplication, and let be the iterated logarithm. Assuming that and that is increasing, we prove that matrices with -bit integer entries may be multiplied in

bit operations. In particular, if is large compared to , say , then the complexity is only .

Authors: David Harvey, Joris van der Hoeven

Keywords: matrix multiplication, complexity, algorithm, FFT, Bluestein reduction

A.M.S. subject classification: 68W30, 68Q17, 68W40

View: Html, TeXmacs, Pdf, BibTeX