2023/02/08 by Bostan, Alin, Neiger, Vincent, Yurkevich, Sergey
#FOS: Computer and information sciences #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.2302.04299
The Nth power of a polynomial matrix of fixed size and degree can be computed by binary powering as fast as multiplying two polynomials of linear degree in~N. When Fast Fourier Transform (FFT) is available, the resulting complexity is softly linear in~N, i.e.~linear in~N with extra logarithmic factors. We show that it is possible to beat binary powering, by an algorithm whose complexity is purely linear in~N, even in absence of FFT. The key result making this improvement possible is that the entries of the Nth power of a polynomial matrix satisfy linear differential equations with polynomial coefficients whose orders and degrees are independent of~N. Similar algorithms are proposed for two related problems: computing the Nth term of a C-finite sequence of polynomials, and modular exponentiation to the power N for bivariate polynomials.