Лекции по параллельным вычислениям. Гергель В.П - 129 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

129
Лекция 10
Перемножение матриц
10.1 Последовательный алгоритм умножения матриц
Умножение матрицы A размера m×n на матрицу B размера n×l приводит к
получению матрицы С размера m×l, каждый элемент которой
ljmibaс
n
k
kjikij
0,0,
1
0
,
т.е. каждый элемент матрицы С вычисляется как скалярное произведение соот-
ветствующих строки матрицы A и столбца матрицы B:
T
jiij
baс ,,
niiii
aaaa
1,1,0,
,,...,,
T
niii
T
j
bbbb
1,1,0,
,...,,
Легко подсчитать, что для реализации перемножения матриц потребуется
m×n×l: операций умножения и m×(n-1)×1 операций сложения. Существуют
приемы, позволяющие перемножить матрицы за меньшее число операций. Од-
нако мы ограничимся рассмотрением алгоритма, реализующего указанный про-
стейший случай. Подсчитаем общее число операций последовательного алго-
ритма для перемножения квадратных n×n-матриц.
Для вычисления одного элемента потребуется
1
2
n
операций (n операций
умножения и
1
n
операций сложения); для вычисления одной строки –
12
nn операций, а общее число операций сложения и умножения для полу-
чения результирующей матрицы C в последовательном алгоритме составит
12
2
nnN
B*A
. (10.1)
Далее рассматриваются два возможных параллельных алгоритма перемножения
матриц при ленточном разбиении и декомпозиции на блоки.

Страницы