2.4. Оптимизация алгоритма разбиение на квадраты и алгоритма «ввод строки-вывод столбца»

Результаты подразд. 2.3.2 можно использовать теперь для поиска оптимального способа транспонирования произвольной матрицы с помощью алгоритма разбиения на квадраты или алгоритма «ввод строки-вывод столбца».

Более точно, будем минимизировать требования к объему памяти для заданного числа просмотров данных. Это не всегда обеспечивает минимум числа операций ввода-вывода, но отклонения от минимума малы (см. подразд. 2.3.2). Более того, если оптимум с точки зрения требуемого объема памяти достигнут без введения нулевых строк то требования к числу операций ввода-вывода также минимальны (см. подразд. 2.2.3). И наконец, так как число просмотров данных, необходимое для матрицы Ограничено сверху или — можно найти (приблизительный) оптимум и с точки зрения объема памяти, и с точки зрения числа операций ввода-вывода при заданных относительных стоимостях памяти и операций обмена.

Сначала остановимся на случае Тогда для данного можно действовать следующим образом.

1. Положить (Тогда

2. Найти наименьшее произведение при используя поскольку согласно

3. Вычислить необходимое число ячеек оперативной памяти в соответствии с (2.25).

4. Найти лучшее произведение для которого (Мы должны рассматривать только эти произведения, так как Заметим, что потому что

5. Если такое М найдено, заменить М на М и повторить

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

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

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

Например, если то и потребуется 125 ячеек памяти с использованием трех шагов. Но матрица может быть транспонирована за 3 шага с помощью 81 ячейки Заметим, что по теореме 2 вслед за транспонированием матриц за шагов надо выполнить объединение строк которое при никогда не может дать лучшего результата.

В табл. 2.1 приведен пример работы этого метода для матрицы .

Таблица 2.1. Требования к объему памяти для транспонирования матрицы при оптимальных

2.5. Примеры

(см. скан)

(кликните для просмотра скана)

4. Прямоугольный метод:

5) Метод «ввод строк-вывод столбца»: