Apparently, it can be done with O(n^log_2(3)) -time complexity using a divide-and-conquer algorithm from here. While not O(n log(n)), it may be faster than the fft for reasonably small matrices. I'm hoping reasonably small is on the order n = 32,000.
Apparently, it can be done with O(n^log_2(3)) -time complexity using a divide-and-conquer algorithm from here. While not O(n log(n)), it may be faster than the fft for reasonably small matrices. I'm hoping reasonably small is on the order n = 32,000.