A Truncated Fourier Transform middle product
Andrew Arnold, Éric Schost · ACM communications in computer algebra · 2015
The middle product computes the middle n terms of a (2 n --1)xn polynomial product, with effectively the same cost as computing an n x n polynomial product. The middle product allows for faster power series operations and Newton iteration. Middle product variants of classical, Karatsuba, and FFT-based multiplication algorithms are known. We present a middle product algorithm based on the Truncated Fourier Transform.