Теория и практика параллельных вычислений
Последовательный алгоритм
Последовательный алгоритм умножения матрицы на вектор может быть представлен следующим образом.
Алгоритм 6.1. Последовательный алгоритм умножения матрицы на вектор
// Алгоритм 6.1 // Поcледовательный алгоритм умножения матрицы на вектор for (i = 0; i < m; i++){ c[i] = 0; for (j = 0; j < n; j++){ c[i] += A[i][j]*b[j] } }
Матрично-векторное умножение – это последовательность вычисления скалярных произведений. Поскольку каждое вычисление скалярного произведения векторов длины n требует выполнения n операций умножения и n-1 операций сложения, его трудоемкость порядка O(n). Для выполнения матрично-векторного умножения необходимо осуществить m операций вычисления скалярного произведения, таким образом, алгоритм имеет трудоемкость порядка O(mn).
