2.2.4. Алгоритм Флойда

Алгоритм разбиения на квадраты обладает таким свойством, что если все сомножители М равны 2 или степеням 2, то он мсркет быть реализован с помощью операций сдвига и маскирования. Это следует из описания, приведенного в подразд. 2.2.3 (см. также [2.7]). Другой алгоритм, предложенный Флойдом, также обладает этим свойством. Он совпадает с алгоритмом разбиения на квадраты, если и может быть применен к любой квадратной матрице непосредственно (без дополнения нулями).

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

1) формируем матрицу которой

2) формируем матрицу которой );

3) рекурсивно, для формируем из сдвигая столбцы, в номерах которых двоичный разряд [см. в (2.15)] равен 1, на мест;

4) формируем матрицу А из полагая

Заметим, что ни ни или самом деле создавать не нужно. Доказательство алгоритма приведено в [2.10].

Используя, скажем, ячеек ОЗУ, можно выполнить шагов алгоритма за один проход, как в алгоритме разбиения на квадраты. Однако этот алгоритм затем требует некоторой дополнительной «бухгалтерии», так как циклический сдвиг элементов охватывает все строки и не может быть выполнен поэтому внутри данной части из строк.

Таким образом, видим, что если используются

ячеек памяти, число операций ввода-вывода

В частности, в [2.10] показано, что если М является степенью 2, то правая часть (2.29) является также нижней границей числа операций ввода-вывода, необходимых для транспонирования матрицы при данном объеме памяти. Следовательно, этот алгоритм, так же как алгоритм разбиения на квадраты и алгоритм, представленный в следующем разделе, минимизирует для данного значения Можно отметить, что ту же самую нижнюю границу получил Стоун [2.11], который также разработал алгоритм, достигающий этой границы. Однако его алгоритм не применим непосредственно к решению этой задачи и не может быть реализован с помощью только операций сдвига и маскирования.

Равенство (2.29) дает только верхнюю границу требуемого числа операций ввода-вывода. В этом отношении оптимальный алгоритм фактически может быть много лучше. Например, оптимальный

мальный алгоритм для матрицы даст по сравнению с верхней границей, равной 30 [2.10]. Не существует, однако, алгоритма, который обеспечивал бы минимальное значение 10 для всех квадратных матриц при заданном значении . Алгоритм Флойда в том виде, как он описан здесь, в общем случае требует затраты большего числа операций ввода-вывода, чем другие алгоритмы, которые здесь рассматриваются. Однако эти алгоритмы обычно требуют несколько большего объема оперативного или внешнего ЗУ. Пример будет приведен в разд. 2.5.

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