К базовым алгоритмам линейной алгебры относятся, прежде всего, алгоритмы вычисления матрично-векторного произведения и алгоритмы вычисления произведения матриц.
Матрично-векторное произведение.
Положим, что в качестве вычислительной системы используется MIMD-система с распределенной памятью, число процессоров в которой равно .
Пусть -матрица , – векторы . Возможны два подхода к вычислению произведения =:

.
Положим для простоты записи, что число строк матрицы кратно количеству процессоров в системе, т.е. что величина кратна величине (так что ). Тогда схему алгоритма можно представить в следующем виде.
  1. Распределяем по процессорам строки матрицы и компоненты вектора так, как показано на Рис.1.
  2. Параллельно на всех процессорах системы вычисляем скалярные произведения соответствующих строк матрицы на вектор :
  3. Передаем на один из процессоров все вычисленные скалярные произведения и формируем вектор
Рис. 1.  К схеме алгоритма матрично-векторного произведения, основанного на использовании скалярных произведений.
Примечание 1
Вычисление матрично-векторного произведения редко является самостоятельной задачей. Поэтому к моменту, когда необходимо вычислить произведение , распределение компонент матрицы и вектора по процессорам системы может отличаться от указанного в первом пункте схемы алгоритма. В этом случае необходим анализ целесообразности перераспределения этих компонент в соответствии со схемой алгоритма. Аналогично, после вычисления произведения может оказаться не нужным передача всех компонент этого вектора на один процессор
С математической точки зрения алгоритм, основанный на использовании скалярных произведений, эквивалентен умножение матрицы на вектор в блочной форме

 (3)

где (*)-матрицы составлены из соответствующих строк матрицы .

Положим для простоты записи, что число столбцов матрицы кратно количеству процессоров в системе, т.е. что величина кратна величине (так что =). Тогда схему алгоритма можно представить в следующем виде.
  1. Распределяем по процессорам столбцы матрицы и компоненты вектора так, как показано на Рис.2.
  2. Параллельно на всех процессорах системы производим следующие вычисления:
    • 1).вычисляем скалярные произведения соответствующих столбцов матрицы на соответствующие компоненты вектора :
    • 2).вычисляем суммы полученных векторов:
  3. Суммируем по схеме сдваивания векторы, полученные на каждом из процессоров, либо передаем их все на один из процессоров, на котором выполняем это суммирование
Относительно алгоритма, основанного на использовании линейных комбинаций столбцов матрицы , справедливо замечание, аналогичное примеч. 1. Заметим также, что в алгоритме, основанном на использовании скалярных произведений, каждое из произведений (см. формулу (3)) может быть с равным успехом вычислено с помощью алгоритма, основанного на использовании линейных комбинаций столбцов матрицы .
Рис. 2.  К схеме алгоритма матрично-векторного произведения, основанного на использовании линейных комбинаций столбцов матрицы A.
Рассмотрим методику оценки эффективности параллельных алгоритмов на примере алгоритма вычисления матрично-векторного произведения с использованием скалярных произведений.
Для простоты записи положим, что время выполнения умножения и сложения двух чисел с плавающей запятой на процессорах одинаково и равно . Положим также, что =. Тогда время вычисления одного скалярного произведения есть и вычислительные затраты каждого из указанных процессоров равны

Коммуникационные расходы каждого из процессоров складываются из расходов на прием компонентов соответствующих векторов , прием компонентов вектора и передачу компонентов результирующего вектора . Таким образом (см. главу 1.2)

где диаметр коммуникационной сети принят равным единице, латентность коммуникационной сети, – длина вещественного числа в байтах, - пропускная способность коммуникационной сети в [].
Итого, время выполнения рассматриваемого алгоритма на процессорах можно оценить величиной


а время выполнения алгоритма на одном процессоре - величиной


Положим, что , . Допустим, кроме того, латентность коммуникационной сети =50*10-6[], а ее пропускная способность . Заметим, что примерно такими параметрами обладает сеть, построенная по технологии SCI, в которой для обмена данными используется MPI. На аппаратном уровне пропускная способностью такой сети достигает примерно 400[Мбайт/c] (при использовании в узловом процессоре 32-разрядной шины PCI с частотой 33 МГц).
Для ускорения алгоритма в результате имеем следующее выражение


которое иллюстрирует рис. 3.
Рис. 3.  Ускорение алгоритма вычисления матрично-векторного произведения с использованием MPI.
Рисунок показывает чрезвычайно низкую эффективность рассмотренного алгоритма: на 4-х, 8-и и 16-и процессорных системах имеет место замедление вычислений; на 64-х процессорной вычислительной системе ускорение не превышает 3. Рисунок получен с помощью следующей MATLAB-программы:
n=100:100:1000;
t=10*10.^(-9);
l=32;
S=50*10.^(-6);
R=80*10.^6;
N=2;
for i=1:1:5
N=N*2;
T1=2*t*n.^2;
TN=(2*t*n.^2)./N+2*S+(((n.^2)./N+n)*l)./R;
SN=T1./TN;
hold on;
plot(n,SN);
end
Влияние на ускорение пропускной способности коммуникационной сети иллюстрирует рис. 4, при построении которого принято, что (пропускная способность максимально возможная для технологии SCI). Рисунок показывает примерно троекратное повышение ускорения.
Заметим, что приведенные оценки эффективность являются упрощенными и дают только грубую оценку эффективности алгоритма. Точная эффективность параллельного алгоритма может быть получена лишь экспериментально - на конкретной вычислительной системе, в конкретной среде программирования и на конкретном наборе данных.
Рис. 4.  Ускорение алгоритма вычисления матрично-векторного произведения без использования MPI.
Матричное умножение.
Пусть - матрица (*), – матрица (*). Рассмотрим задачу вычисления произведения этих матриц =, где – матрица (*).
Алгоритм вычисления произведения может быть построен на основе рассмотрения этого произведения в виде совокупности произведений матрицы на столбец матрицы и использовании предыдущих результатов данного параграфа. Однако при вычислении этого произведения чаще используется блочное представление матриц , , .
Положим для простоты записи, что размеры матриц кратны числу процессоров в системе . Тогда матрицу можно представить в виде


 (4)

где , , и размерность каждого из блоков матриц , , равна, соответственно , , . Из (4) следует, что блок матрицы есть сумма матричных произведений -ой строки блоков матрицы на -й столбец блоков матрицы :

 (5)


Схема параллельного алгоритма, основанного на блочном представлении матриц.
  1. Распределяем по процессорам блоки матриц , так, как показано на рис. 5.
  2. Параллельно на всех процессорах системы производим вычисление компонент соответствующих блоков матрицы :
    • на процессоре - блоков , [1,], образующих первую строку блоков матрицы ;
    • на процессоре - блоков , [1,], образующих второю строку блоков матрицы ;
    • ….
    • на процессоре - блоков , [1,], образующих строку блоков матрицы ;
  3. Передаем на один из процессоров все вычисленные блоки и формируем матрицу (4)

Относительно рассмотренного алгоритма также справедливо примечание, аналогичное примечанию 1. Заметим, кроме того, что легко предложить множество модификаций данного алгоритма, например:
•вместо строкового распределения блоков матрицы по процессорам, можно использовать распределение по столбцам;
•можно использовать разбиение матриц , на блоки таким образом, чтобы общее количество блоков было равно количеству процессоров в системе, и каждому процессору назначать вычисление одного блока
Рассмотренная задача вычисления матрично-векторного произведения и задача умножения матриц носят явно выраженный векторный характер и для их решения более предпочтительным является использование векторно-конвейерных ЭВМ и векторно-параллельных ЭВМ.
Рис. 5.  К схеме алгоритма матричного умножения на основе блочного представления матриц.