Умножение матрицы на вектор. Пусть А матрица mn, а х вектор длины n. Тогда произведение можно записать двумя способами или, где аi i-я строка матрицы А, аi i-й столбец матрицы А, а x, y скалярное произведение.
Различие способов записи можно рассматривать как различие двух способов доступа к данным, что приводит к разным алгоритмам и для задач матричного умножения и решения линейных систем.
Пусть система состоит из р процессоров. Рассмотрим сначала векторно-матричное произведение с помощью линейных комбинаций. Предположим, что p n и xi и ai приписаны процессору i. Все произведения xiai вычисляются с максимальным параллелизмом, а затем выполняются сложения по методу сдваивания.
Причем синхронизация в данной модели не требуется. Алгоритм скалярных произведений в некоторых отношениях более привлекателен. Пусть p m, x и ai приписаны процессору i. Каждый процессор выполняет свое скалярное произведение, и при этом паралелизм максимален. Выбор алгоритма вычислений зависит от целого ряда обстоятельств.
Матрично-векторное умножение неизбежно является частью более широкого процесса вычислений, и основную роль играет способ хранения матрицы А и вектора х. Еще одно существенное соображение желаемое расположение результата по окончании умножения в первом случае результат размещается в памяти одного процессора, тогда как в другом он размещен между процессорами. В реальных системах n и m значительно больше числа процессоров, и каждому процессору передаются несколько строк или столбцов. 1.2.