2.6. Метод Андерсона для непосредственного вычисления многомерного ДПФ

Андерсон [2.1] предложил альтернативный метод решения задачи ДПФ матрицы, записанной построчно в ЗУ с произвольным доступом. Поскольку внешняя сумма (2.26) является ДПФ для фиксированного I, очевидно, что для ее вычисления можно использовать БПФ. Основная идея использования БПФ заключается в том, что ДПФ массива может быть вычислено итеративным суммированием, при котором каждая сумма в свою очередь является ДПФ. Если, в частности, размер массива М является степенью 2, то каждая частичная сумма может рассматриваться как двухточечные ДПФ. Тогда (см., например, [2.16] или [2.17]) на шаге, преобразуются две точки с индексами и двоичные представления которых отличаются точно в позиции I. При этом результирующий массив оказывается представленным в двоично-инвертированном порядке, но можно так

переупорядочить исходный массив, что результирующие значения будут следовать в естественном порядке (см. также [2.18]).

Обнаружив, что сумма в (2.26) вычисляется для всех можно действовать следующим образом. На шаге в оперативную память считываются пары строк, для которых индексы отличаются точно в позиции их двоичного представления. Затем на месте выполняется двухэлементное ДПФ для всех столбцов. Эти модифицированные строки записываются снова на свои старые места. После шагов получаем нужное преобразование, но расположенное в двоично-инвертированном порядке. Однако это не составляет никакой проблемы, поскольку известен ключ для перестановки, который можно использовать либо при вводе, либо при дальнейшей обработке. Безотносительно к тому, как учитывается двоичная инверсия, можно заметить, что адресация строк полностью аналогична адресации в методе разбиения на квадраты (и в алгоритме Флойда) для транспонирования матриц.

Эта аналогия между двумя методами распространяется на любые возможные обобщения. В обоих случаях можно снизить время ввода-вывода, рассматривая более двух строк одновременно. Действительно, если матрица содержит элементов и есть возможность хранить в оперативной памяти строк, то число операций ввода-вывода

Если М и являются степенями 2, то совпадает с . Кроме того, метод обобщается на произвольную факторизацию М, так же как и БПФ, и сохраняется аналогия с методами транспонирования, описанными в разд. 2.2. Следовательно, эффективность, измеренная с точки зрения операций ввода-вывода, остается той же самой и в этом случае.

Непосредственный метод принципиально прост за счет того, что он сам основан на использовании свойств быстрых алгоритмов (например, БПФ). Его достоинство проявляется также в возможности обрабатывать на месте произвольную матрицу. Однако метод обладает рядом недостатков, о которых будет сказано в следующем разделе.