Введение
Алгоритм Брюна — это алгоритм быстрого преобразования Фурье (FFT), основанный на необычном рекурсивном подходе к факторизации полиномов, предложенный Г. Бруном в 1978 году для степеней двойки и обобщенный Х. Мураками в 1996 году для произвольных четных составных размеров. Поскольку его операции используют только вещественные коэффициенты до финальной стадии вычислений, он изначально был предложен как способ эффективного вычисления дискретного преобразования Фурье (DFT) для вещественных данных. Однако алгоритм Брюна не получил широкого распространения, так как подходы, основанные на стандартном алгоритме Кули–Тьюки FFT, были успешно адаптированы для работы с вещественными данными с сопоставимой или даже большей эффективностью. Более того, существуют данные, свидетельствующие о том, что алгоритм Брюна может быть менее точным, чем алгоритм Кули–Тьюки при ограниченной числовой точности. Тем не менее, алгоритм Брюна демонстрирует альтернативную алгоритмическую структуру, которая может быть использована для представления как самого себя, так и алгоритма Кули–Тьюки, что позволяет взглянуть на FFT под новым углом и комбинировать оба алгоритма, а также применять другие обобщения.
Bruun's algorithm is a fast Fourier transform (FFT) algorithm based on an unusual recursive polynomial factorization approach, proposed for powers of two by G. Bruun in 1978 and generalized to arbitrary even composite sizes by H. Murakami in 1996. Because its operations involve only real coefficients until the last computation stage, it was initially proposed as a way to efficiently compute the discrete Fourier transform (DFT) of real data. Bruun's algorithm has not seen widespread use, however, as approaches based on the ordinary Cooley–Tukey FFT algorithm have been successfully adapted to real data with at least as much efficiency. Furthermore, there is evidence that Bruun's algorithm may be intrinsically less accurate than Cooley–Tukey in the face of finite numerical precision
Nevertheless, Bruun's algorithm illustrates an alternative algorithmic framework that can express both itself and the Cooley–Tukey algorithm, and thus provides an interesting perspective on FFTs that permits mixtures of the two algorithms and other generalizations.
Кули Туки как множительное множительное
Стандартный алгоритм децимирования в частоте (DIF) с радиксом r Cooley–Tukey тесно связан с рекурсивной факторизацией. Например, алгоритм Cooley–Tukey с радиксом 2 DIF раскладывается на и . Эти операции по модулю уменьшают степень многочлена на 2, что соответствует уменьшению размера задачи вдвое. Однако, вместо непосредственной рекурсивной факторизации , алгоритм Cooley–Tukey сначала вычисляет x2(zωN), сдвигая все корни (с помощью коэффициента поворота), чтобы затем применить рекурсивную факторизацию к обеим подзадачам. То есть, Cooley–Tukey гарантирует, что все подзадачи также являются DFT, в то время как это не всегда верно для произвольной рекурсивной факторизации (например, факторизации Бруна, описанной ниже).
Обобщение на произвольные корни
Факторизация Бруна, и, следовательно, алгоритм Бруна FFT, был обобщен для обработки произвольных четных составных длин, то есть для деления степени многочлена на произвольный радикс (фактор), следующим образом. Сначала мы определяем множество многочленов φN,α(z) для положительных целых чисел N и для α в :
Обратите внимание, что все многочлены, которые появляются в факторизации Бруна, описанной выше, могут быть записаны в этой форме. Нули этих многочленов равны для в случае, и для в случае. Следовательно, эти многочлены могут быть рекурсивно разложены на множители для радикса (фактора) r следующим образом: