ТРАНСПОНИРОВАние матриц

Необходимо определить матрицу D = {d_ij} обратную матрице A = {a_ij}, i, j = 1, …, n.

Рекуррентное соотношения имеют вид:

(1)

где: (2)

Формулы (2) задают схему вычислений, рассмотренную нами при LU-разложении матрицы, только значение равные 1 получают диагональные элементы не нижней (L), а верхней (U) матрицы. На прямоугольной (а не гексагональной) решетке зависимости между вычислениями элементами можно представить в виде потоковой схемы (для n = 4).

Из рекуррентных формул следует, что при большом размере задачи ( )затраты на выполнение скалярного произведения элементов составляет самую значительную часть всех вычислений. При этом для определения элемента (i,j) требуется q-раз выполнить операцию накопления – ход_k, q = j – 1 для и q = i для .

В случае двумерного распараллеливания вычислений по формуле (2) нахождение каждого элемента (i,j) (b_ij или c_ij) осуществляется на ЭМ с координатами (i,j). Каждая машина (i,j) должна хранить в своей памяти соответствующий исходный элемент a_ij и программу обработки. Кроме того, каждая машина (i,2) первого столбца подсистемы должна содержать элемент .

Обработка данных начинается от машины (1,2), которая на первом шаге передачей операнда направо и вычисленного элемента вниз активизирует соседние машины с координатами (1,3) и (2,2) соответственно. На втором шаге машина (1,3) определяет и передаёт его машине (2,3), а принятый операнд ретранслирует в машину (1,4). На этом же шаге машина (2,2) передает b₂₁ в машину (2,3), Нетранслирует принятый операнд с₁₂ в машину (3,2), определяет и передает в ЭМ (2,3) элемент и т.д.