Пусть Ts - время работы последовательного алгоитма, Tp - время работы параллельного алгоитма, A - ускорение, E - эффективность.

Общая трудоемкость последовательного алгоритма пропорциональна n^3. Для параллельного алгоритма на каждой итерации каждый процессор выполняет умножение имеющихся на процессоре полос матриц А и В (размер полос равен n/p, следовательно, общее количество выполняемых при этом умножении операций равно n^3/p^2). Поскольку число итераций алгоритма совпадает с количеством процессоров, сложность параллельного алгоритма без учета затрат на передачу данных может быть определена при помощи выражения

Tp=(n^3/p^2)*p=n^3/p

Так как A=Ts/Tp, то:

A=(n^3)/((n^3)/p)=p
E=(n^3)/[((n^3)/p)*p]=1

Мы получили идеальные показатели эффективности, но на практике это не всегда выполняется.
Для уточнения полученных соотношений оценим более точно количество вычислительных операций алгоритма и учтем затраты на выполнение операций передачи данных между процессорами.
С учетом числа и длительности выполняемых операций время выполнения вычислений параллельного алгоритма может быть оценено следующим образом:

Tp(calc)=[(n^2)/p]*[2n-1]*t
t - время выполнения одной элементарной скалярной операции

Для оценки коммуникационной сложности параллельных вычислений будем предполагать, что все операции передачи данных между процессорами в ходе одной итерации алгоритма могут быть выполнены параллельно. Объем передаваемых данных между процессорами определяется размером полос и составляет n/p строк или столбцов длины n. Общее количество параллельных операций передачи сообщений на единицу меньше числа итераций алгоритма (на последней итерации передача данных не является обязательной). Тем самым, оценка трудоемкости выполняемых операций передачи данных может быть определена как

Tp(comm)=(p-1)*(a+w*n*(n/p)/b)
a - латентность, b - пропускная способность сети передачи данных, а w - размер элемента матрицы в байтах. Тогда

Tp=(n^2/p)(2n-1)*t+(p-1)*(a+w*n*(n/p)/b)