Пусть перемножаемые матрицы
и
имеют порядок
. Количество процессов
является квадратом,
квадратный корень которого кратен
. В этом случае
и
. В алгоритме Фокса
матрицы разделяются среди процессов в виде клеток шахматной доски. При этом
процессы рассматриваются как виртуальная двухмерная
сетка, и каждому
процессу назначена подматрица
каждого множителя. Реализуется отображение:
Оно определяет сетку процессов: процесс
относится к строке и
столбцу, заданному
. Процесс с рангом
назначается на подматрицы:
и
Например, если
,
, и
, то A будет
разделена следующим образом (рис. 4).
Процесс 0:  |
Процесс 1:  |
Процесс 2:  |
Процесс 3:  |
Процесс 4:  |
Процесс 5:  |
Процесс 6:  |
Процесс 7:  |
Процесс 8:  |
Рис. 4. Разделение матрицы на подматрицы
В алгоритме Фокса, подматрицы блоков,
и
, где
, перемножаются и
собираются в процессе
.
Алгоритм состоит в следующем:
-
- for(step = 0; step < q; step++) {
Выбрать подматрицу A в каждой строке
для всех процессов.
В каждой строке для всех процессов разослать
сетку подматриц, выбранную в этой строке для
других процессов в этой строки.
В каждом процессе, перемножить полученную подматрицу
A на подматрицу B, находящуюся в процессе.
В каждом процессе, отослать подматрицу B процессу,
расположенному выше. (Для процессов первой строки
отослать подматрицу в последнюю строку.)
}
Подматрицей, выбранной для

-ой строки является

, где