2.2.6. Алгоритм прямоугольных разбиений

Последний алгоритм, который мы рассмотрим, впервые был предложен в [2.13]. Этот алгоритм состоит в последовательном транспонировании подматриц порядка где — множители М и соответственно Позже Рамапрайян [2.8] обобщил алгоритмы на случай, когда , где определяются численной оптимизацией требуемого времени вычислений.

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

Тогда на шаге, входная матрица где рассматривается как матрица , элементами которой являются матрицы представляющие собой фактически подматрицы А. Эта секционированная матрица рассматривается как матрица из которой селективно считываются в оперативную память матрицы т.{Хпи где они транспонируются и записываются в Строки в считываемые матрицы выбираются как в [2.13], т. е. с шагом Таким образом, матрица А будет построена из блоков размерами и на шаге будет сформирована матрица содержащая А.

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

Если алгоритм совпадает с алгоритмом, приведенным в [2.13]. В противном случае матрица на шаге превращается в минимальную для данных пр матрицу, с которой работает алгоритм [2.13].

Требуемый объем памяти определяется выражением

где при второе слагаемое может быть опущено.

Число операций ввода-вывода