Теория и практика параллельных вычислений
Постановка задачи
Умножение матрицы A размера m?n и матрицы B размера n?l приводит к получению матрицы С размера m?l, каждый элемент которой определяется в соответствии с выражением:
|
(7.1) |
Как следует из (7.1), каждый элемент результирующей матрицы С есть скалярное произведение соответствующих строки матрицы A и столбца матрицы B:
|
(7.2) |
Этот алгоритм предполагает выполнение m·n·l операций умножения и столько же операций сложения элементов исходных матриц. При умножении квадратных матриц размера n?n количество выполненных операций имеет порядок O(n3). Известны последовательные алгоритмы умножения матриц, обладающие меньшей вычислительной сложностью (например, алгоритм Страссена (Strassen’s algorithm)), но эти алгоритмы требуют больших усилий для их освоения, и поэтому в данной лекции при разработке параллельных методов в качестве основы будет использоваться приведенный выше последовательный алгоритм. Также будем предполагать далее, что все матрицы являются квадратными и имеют размер n?n.
