Return to Revisions

6 of 8

edited title

edited Jan 3, 2012 at 18:02

Fast algorithms for Moore matrix using FFT

This question is with regard to Elkies' answer to the above post.

What is the complexity of computing the determinant of a given $n \times n$ full rank Moore matrix modulo some integer?

Vandermonde determinant can be computed using FFT techniques in $O(n\log^{a}{n})$ for some $a \in \mathbb{R}_{+}$.

Can Moore determinant be likewise reduced from $O(n^{3})$ to $O(n\log^{b}{n})$ for some $b \in \mathbb{R}_{+}$ (if so is there a reference)?

asked Dec 28, 2011 at 4:09