Может быть выгодным пользоваться производными от Фурье преобразованиями - например, преобразование Хартли имеет примерно те же свойства для свёртки, но - действительное, а не комплексное. Есть ещё теоретико-числовые преобразования - но это тоже преобразования Фурье, но в конечных полях.
Другие преобразования могут использоваться для каких-то специальных случаев, но они в любом случае неоптимальны.
Возможность факторизации свёртки напрямую связано с тем, что векторы базиса Фурье являются собствеными векторами оператора сдвига.
Jörg Arndt, грамотный и нежадный автор, разместил замечательную книгу и С-библиотеку FXT относящуюся к этой теме
http://www.jjj.de/fxt/fxtpage.html#fxtbook
Быстрая свёртка, Вычисление не через преобразование Фурье
Nov 24 2005, 11:45
