2.7. Обсуждение результатов

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

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

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

Упомянем некоторые менее важные различия между методами. Предположим, что надо выполнить прямое и обратное преобразование матрицы и что выбраны достаточно сложными составными числами, чтобы не приходилось увеличивать матрицы, дополняя их нулями. Предположим, что элементов заполняют оперативную память, и что — целое, тогда

На основе этих выражений можно показать, что если если . Например, если , то но если то . Можно заметить, также, что если минимальный объем памяти для выполнения пары преобразований, независимо от времени ввода-вывода, меньше для непосредственного метода.

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

Алгоритм Флойда может работать с любой квадратной матрицей, используя только операции сдвига и маскирования, и распространяется на прямоугольные матрицы так, как описано в подразд. 2.2.3. Однако три других алгоритма не обладают этим «двоичным» свойством, поскольку они используют расширение в форме (2.15). С другой стороны, они могут выполнять транспонирование с меньшими затратами операций ввода-вывода при чуть большем объеме памяти. Эти три алгоритма требуют также специального этапа оптимизации, который достаточно прост для метода разбиения на квадраты, и алгоритма «ввод строки-вывод столбца», но несколько более сложен для алгоритма разбиения на прямоугольники.

Последний алгоритм также несколько сложнее по своей сущности, так как число и длины строк изменяются во время транспонирования, даже если размеры матриц являются составными числами.

В общем, более простые алгоритмы разбиения на квадраты и «ввод строки-вывод столбца» почти всегда эффективны. Поэтому они предпочтительнее, если не требуется реализации только посредством сдвигов и маскирования, когда можно использовать алгоритм Флойда.