2.2.3. Транспонирование с использованием разбиений на квадраты

Второй алгоритм был впервые предложен Эклуидом [2.6]. Он основан на последовательном транспонировании квадратных фрагментов и является естественным обобщением другого метода, описанного [2.7]. Он также сходен методом, используемым в [2.8].

Пусть А — матрица и , где . Положим и определим для

где определено следующим образом:

- обозначение целой части х. Тогда транспонирование матрицы А можно выполнить за шагов следующим образом.

Шаг 1. Сформируем матриц размерами из последовательных строк А. Каждую такую матрицу можно разбить на матриц возможно, дополнив ее предварительно нулями [не более нулей]. Эти квадратные матрицы можно теперь транспонировать на месте. В результате получим матрицу элементами которой будем считать подматрицы — фрагменты строк. При таком рассмотрении матрица имеет размеры

Определим индуктивно шаг, считая первые М шагов выполненными.

Шаг i. На шаге начнем с матрицы размерами Элементами этой матрицы являются подматрицы — фрагменты строк размерами Затем из строк матрицы строим подматриц Каждая из этих подматриц формируется из тех строк матрицы которые находятся в ней на расстоянии строк друг от друга. Выбор строк для каждой подматрицы выполняется следующим образом. Если обработано строк то выбираются строк, начиная с первой необработанной строки, т. е. строки так, что каждая следующая выбираемая строка отстоит от предыдущей (уже выбранной) на строк 1. Следовательно, типичная подматрица состоит из строк, номера которых в матрице определяются выражением где , а значения из указанных выше диапазонов зафиксированы для каждой подматрицы.

Сформированные подматрицы, при необходимости дополненные нулями, можно разбить на матриц Элементами этих квадратных матриц будем считать фрагменты строк размерами Матрицы транспонируются, и получается матрица с размерами с элементами-подматрицами Эти элементы являются фрагментами строк матрицы-результата А.

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

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

где определяется выражением (2.11). Представление (2.15) очевидным образом получается из главных остатков при последовательном делении на т., (подобно тому, как при обычной системе счисления). Для упрощения будем использовать обозначения

Теперь шаг 1 означает, что матрица А разбита на подматрицы которые затем транспонируются. Следовательно,

поскольку определяют, к какой именно подматрице принадлежит данный элемент.

По индукции предположим, что после Н шагов имеем

Шаг можно теперь описать следующим образом. Будем считать, что матрица разбита на подматрицы размерами Затем внутри каждой подматрицы сформируем матрицы выбирая всевозможные комбинации из строк и столбцов, разделенных строками (столбцами). Это означает, что остаются неизменными, так как они определяют конкретную матрицу с которой мы работаем. То же относится и к поскольку эти значения определяют матрицу к которой принадлежит элемент. В этой матрице элемент перед транспонированием находится в строке и столбце Поэтому после транспонирования его положение в матрице определяется:

Следовательно, Это и доказывает, что занимает правильное положение в Отсюда видно, что транспонирование выполняется как последовательный обмен разрядами в выражении (2.15), которое является представлением номеров строки и столбца в позиционно-численном представлении по смешанному основанию. В частности, если для всех то получаем алгоритм, описанный в [2.7, 2.9].

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

Случай может быть рассмотрен аналогично, если в (2.15) записать

при для . Конечное положение теперь будет где

В этом случае строки матрицы содержат одну или несколько строк матрицы А. Записывая как расчлененную на матрицы где определяется (2.13),

получим А как

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

Если , то, по крайней мере, для некоторых произведений М алгоритм сначала будет транспонировать матрицы где а затем отсекать или расщеплять строки.

Если строки матриц создаются при выводе на внешнее эффективность алгоритма по требуемому числу ячеек ОЗУ на шаге характеризуется

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

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

В дальнейшем покажем (см. подраздел 2.3.1), что значение увеличивается с ростом откуда и следует, что

Если строки матрицы состоящие из нулей, не записываются, то необходимое число операций ввода-вывода будет определяться выражением:

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