International research journal

p
i

. Здесь значение 
p
x
, 
присутствующее в результатах обеих прогонок, находится из системы двух уравнений: 
{
𝑥
𝑝
= 𝛼
𝑝+1
𝑥
𝑝+1
+ 𝛽
𝑝+1
𝑥
𝑝+1
= 𝜉
𝑝+1
𝑥
𝑝
+ 𝜂
𝑝+1
𝑥
𝑝
=
𝑓
𝑝
−𝑎
𝑝
𝛽
𝑝
−𝑏
𝑝
𝜂
𝑝+1
𝑐
𝑝
+𝑎
𝑝
𝛼
𝑝
+𝑏
𝑝
𝜉
𝑝+1
(6) 
Определив значение 
𝑥
𝑝
, можно найти все 
𝑥
𝑖
, при 
1 ≤ 𝑖 < 𝑝
в первом потоке, и все значения 
𝑥
𝑖
, при 
𝑝 < 𝑖 ≤ 𝑁
во 
втором потоке. 
Время решения системы последовательным методом прогонки при больших значения размерности системы 
𝑛
определяется как 
𝑇
1
= 10𝑛𝜏
, где 
𝜏
время выполнения одной операции. При параллельной реализации методом 
встречной прогонки время работы алгоритма можно оценить, как 
𝑇
1
= 5𝑛𝜏 + 𝛿
, где 
𝛿
– время обслуживания потоков, 
затрачиваемое при создании и закрытии параллельной секции. В обоих случаях при увеличении размера системы время 
расчета возрастает линейно, но параллельный алгоритм сокращает время примерно в 2 раза. 

---

Международный научно-исследовательский журнал 
▪
 № 5 (95) ▪ Часть 3 ▪ Май 
94 
Большее ускорение можно получить при использовании для распараллеливания блочного алгоритма [5], 
позволяющего нагружать расчетами большее число процессоров (потоков 
p>
2). 
Алгоритм блочной прогонки осуществляет исключение поддиагональных элементов для каждой полосы размера 
𝑚 = [𝑛/𝑝]
строк основной матрицы, т.е. 
k
-й поток обрабатывает строки с номерами 
1 + (𝑘 − 1)𝑚 ≤ 𝑖 ≤ 𝑘𝑚, 𝑘 =
1, … 𝑝.
Например, расчеты для матрицы системы размерности 
n=12
и числе потоков 
𝑝
=
3
, сводятся к параллельному 
решению трех систем размерности
m=4
. 
Поскольку каждая полоса матрицы, соответствующая потоку с номером
𝑘
, (кроме 
𝑘
=
1
) содержит по три 
неизвестных в каждой строке, то после прямого хода в каждой полосе, за исключением первой, появится новый столбец 
коэффициентов. 
Формулы прямого хода алгоритма горизонтально - блочной прогонки позволяют вычислить прогоночные 
коэффициенты
 α
, 
β
и 

для каждой полосы (потока) размера 
𝑚 = [𝑛/𝑝]
по формулам (при 
p=1
верны формулы правой 
прогонки (2)):
𝑥
𝑖
= 𝛼
𝑖+1
𝑥
𝑖+1
+ 𝛽
𝑖+1
+ 𝛾
𝑖+1
𝑥
𝑝𝑚−1
, 𝑖 = (𝑝 − 1)𝑚, . . . , 𝑝𝑚 − 1
,
𝛼
1
=
−𝑏
0
𝑐
0
,
𝛽
1
=
𝑓
0
𝑐
0
, 𝛾
1
=
−𝑎
0
𝑐
0
, 𝛼
𝑖+1
=
−𝑏
𝑖
𝑎
𝑖
𝛼
𝑖
+𝑐
𝑖
,
𝛽
𝑖+1
=
𝑓
𝑖
−𝑎
𝑖
𝛽
𝑖
𝑎
𝑖
𝛼
𝑖
+𝑐
𝑖
,
𝛾
𝑖+1
=
−𝑎
𝑖
𝛾
𝑖
𝑎
𝑖
𝛼
𝑖
+𝑐
𝑖
,
(7) 
Использование в блочном алгоритме формул обратного хода позволяет в каждом потоке исключить 
наддиагональные элементы.
Обратный ход метода вычисляет прогоночные коэффициенты 
m
, 
l
, 
k
: 
𝑥
𝑖
= 𝑚
𝑖+1
𝑥
𝑝𝑚−1
+ 𝑙
𝑖+1
+ 𝑘
𝑖+1
𝑥
𝑚−1
, 𝑖 = 𝑝𝑚 − 1, . . . , 𝑚(𝑝 − 1)
, 
𝑚
𝑚−1
= 𝛼
𝑚−𝑖
, 
𝑙
𝑚−1
= 𝛽
𝑚−𝑖
, 
𝑘
𝑚−1
= 𝛾
𝑚−𝑖
, 𝑚
𝑖
= 𝛼
𝑖
𝑚
𝑖+1
, 
𝑚
𝑖
= 𝛼
𝑖
𝑚
𝑖+1
,
𝑙
𝑖
= 𝛼
𝑖
𝑙
𝑖+1
+ 𝛽
𝑖
,
𝑘
𝑖
= 𝛼
𝑖
𝑘
𝑖+1
+ 𝛾
𝑖
,
(8) 
В итоге матрица коэффициентов исходной системы уравнений принимает блочный вид. 
Затем, с помощью найденных коэффициентов, формируется система уравнений размера (
𝑝 × 𝑝)
с трехдиагональной 
матрицей, состоящая из уравнений на нижних границах каждой полосы вида: 
𝐴
𝑖
𝑥
𝑖−1
− 𝐵
𝑖
𝑥
𝑖
+ С
𝑖
𝑥
𝑖 + 1
= 𝐹
𝑖 
𝑖 = 1, … , 𝑝 − 1 ,
с коэффициентами: 
𝐴
1
= 0
,
𝐵
1
= −𝛼
𝑚
∙ 𝑚
𝑚+1
+ 𝛽
𝑚
, 
𝐶
1
= 1 − 𝛼
𝑚
∙ 𝑘
𝑚+1
, 
𝐹
1
= 𝛼
𝑚
∙ 𝑙
𝑚+1
+ 𝛽
𝑚
. 
𝐴
𝑝
= −𝛾
𝑝∙𝑚
,
𝐵
𝑝
= 1
,
𝐶
𝑝
= 0
, 
𝐹
p
= 𝛽
𝑝∙𝑚
. 
𝐴
𝑖
= −𝛾
𝑚(𝑖+1)
, 
𝐵
𝑖
= −𝛼
𝑚(𝑖+1)
∙ 𝑚
𝑚(𝑖+1)+1
,
𝐶
𝑖
= 1 − 𝛼
𝑚(𝑖+1)
∙ 𝑘
𝑚(𝑖+1)+1
, 
𝐹
𝑖
= 𝛼
𝑚(𝑖+1)
∙ 𝑙
𝑚(𝑖+1)+1
+ 𝛽
𝑚(𝑖+1)
, 
(9) 
Ее решение находится обычным последовательным методом прогонки. 
Далее, с помощью найденных граничных значений неизвестных каждой полосы, остальные неизвестные 
(внутренние переменные в каждом блоке) находятся по формулам: 
𝑥
𝑖
= 𝑚
𝑖+1
∙ 𝑥
𝑗∙𝑚−1
+ 𝑘
𝑖+1
∙ 𝑥
(𝑗−1)𝑚−1
+∙ 𝑙
𝑖+1
, 
𝑖 = (𝑗 − 1)𝑚, … , 𝑗𝑚 − 1, 𝑗 = 1, … 𝑝
(10) 
Эти значения опять можно вычислять независимо в каждом потоке.
Общую трудоемкость параллельного метода прогонки (