Краткий вывод алгоритма Кули-Тьюки

М. С. Беспалов

Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых, институт прикладной математики, физики и информатики, ул. Горького, 87, Владимир, 600000, Российская Федерация

Аннотация: В статье предложена окончательная форма матричной записи алгоритма быстрого преобразования Фурье (Fast Fourier Transform, FFT) для произвольного составного порядка. Предлагается, чтобы алгоритм начинался с обратной перестановки, а не включал совершенную перестановку на каждом шаге алгоритма. Обратная матрица перестановок представлена как $b$-произведение единичных матриц ($b$-произведение является новым типом тензорного произведения матриц, введенным автором ранее).

Ключевые слова: быстрое преобразование Фурье, тензорное произведение матриц.

УДК: 517.58

MSC: 65T50