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