Michael Monagan

Computer algebra systems like Maple and Mathematica spend most of their time doing either polynomial arithmetic or linear algebra. For polynomials in one variable of degree n, the Fast Fourier Transform gives us an O(n log n) multiplication algorithm...