ГЛАВА 2. ЭФФЕКТИВНЫЕ МЕТОДЫ ТРАНСПОНИРОВАНИЯ МАТРИЦ

(Дж.-О. Эклунд)

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

Рассмотрим также непосредственный метод двумерного преобразования Фурье. Сравнение его с методом, предполагающим

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

2.1. Транспонирование матриц в обработке сигналов

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

Один из способов решения этой проблемы заключается в транспонировании матрицы после преобразования по строкам. Другой способ, предложенный в [2.1], вытекает непосредственно из определения быстрого преобразования Фурье (БПФ); при этом необходимо помнить, что БПФ строится как последовательность преобразований над подмассивами и все эти преобразования выполняются с оставлением массива на месте.

Оба подхода основаны на разделимости преобразования Фурье. Двумерное дискретное преобразование Фурье (ДПФ) комплексного массива можно определить следующим образом:

где для удобства обозначено Разделимость означает, что ядро преобразования является произведением двух функций, одна из которых зависит только от а другая — от Это позволяет вычислять преобразование за два шага: сначала

а затем

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

С другой стороны, факт, что сумма в (2.26) также является ДПФ, наводит на мысль о возможности непосредственного вычисления с использованием методов итеративного суммирования для БПФ в сочетании с вводом и выводом преобразованных строк.

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

Важнее, однако, что и одномерные преобразования больших массивов могут быть разбиты на преобразования меньших массивов и транспонирование матриц. В случае ДПФ это можно сделать в соответствии с [2.2].

ДПФ массива можно определить следующим образом:

Теперь, если запишем

и рассмотрим х как матрицы, положив

Так как и

Вычислив сумму за два шага, получим

Здесь для данной строки у сначала вычисляем соответствующую строку Z путем перемножения соответствующих фазовых множителей и суммирования. Затем для данного столбца Z вычисляем его ДПФ, язляющееся соответствующим столбцом У. Для этого необходимо применить транспонирование Z.

Были предложены также другие методы вычисления одномерных и многомерных преобразований в ОЗУ ограниченного объема. Одни методы требуют транспортирования матриц (см., например, [2.2, 2.3]), другие не требуют (см., например, [2.4, 2.5]). Последние, в общем, менее эффективны.