On the complexity of integer matrix multiplication. (November 2018)

• Record Type: Journal Article
• Authors: Harvey, David; van der Hoeven, Joris
• Is Part Of: Journal of symbolic computation. Volume 89(2018)
• Page Start: 1
• Page End: 8
• Publication Date: 2018-11
• Subjects: 68W30 -- 68Q17 -- 68W40; Matrix multiplication -- Complexity -- Algorithm -- FFT -- Bluestein reduction; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.11.001
• Languages: English
• ISSNs: 0747-7171

Abstract

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 ) ) .