2.2.2. Решение системы линейных уравнений методом Гаусса с помощью вс типов «решётка» и «линейка»

Рассмотрим широко известный алгоритм рещения СЛАУ отличающийся простотой реализации. Пусть дана система линейных уравнений (2.2.24):

a₁₁ x₁ + a₁₂х₂ +…+ a_1nх_n = a_1,n+1

a₂₁ x₁ + a₂₂ х₂ +…+ a_2nх_n = a_2,n+1

… (2.2.24)

a_n1 x₁ + a_n2 x₂ +…+ a_nn x_n = a_n,n+1

Решение системы уравнений по компактной схеме [25] заключается в последовательном определении х_n, x_n-1, ..., x₁ из системы уравнений:

x₁ + c₁₂х₂ +…+ c_1nх_n =c_1,n+1

c₁₂ х₂ +…+ a_1nх_n = a_2,n+2

…

x_n = c_n,n+1

Эта система получается как результат разложения исходной матрицы на треугольные матрицы согласно формулам (2.2.25):

(2.2.25)

b

После вычислений «прямого хода» метода Гаусса получается матрица:

Из рекуррентных соотношений следует, что любой (i,j)-элемент матрицы получается как разность между исходным элементом а_ij и суммой парных произведений ранее определенных значений b_ik, находящихся в рассматриваемой строке слева, и соответствующих значений с_kj, расположенных в рассматриваемом столбце сверху от вычисляемого значения. При определении значений с_ij необходимо также выполнить деление на значение b_ii. Использование метода без выбора ведущего элемента пред­полагает, что все b_ii, i = 1, ... , n, отличны от нуля, и деление на b_ii не приводит к по­тере точности.

Граф информационных зависимостей алгоритма получения треугольных матриц 4х4 показан на рисунке 2.2.8.

Рисунок 2.2.8. ГУЗ алгоритма получения треугольных матриц для п = 4

Значения x_i , i = n, n - 1, ... , 1, вычисляются по формуле:

Значение х_n находим при разложении матрицы. Последующие значе­ния х_i формируются как разность с_i,n+1 и суммы парных произведений предыдущих вычисленных значений х_п,..., x_i-1 на соответствующие значения с_i,n, ... , c_i,i-1.

Граф информационных зависимостей для п = 4 показан на рисунке 2.2.9.

2.2.9. Граф информационных зависимостей для п = 4

Поиск неизвестных по элементам верхней треугольной матрицы осуществляется с помощью обратного хода алгоритма Гаусса.

2.2.3. Исполнение алгоритма Гаусса на «решётке» n*n вm

Рассмотрим два характерных случая выполнения алгоритма Гаусса: выполнение на ВС, содержащей n² ВМ (решетке п*п.) и ВС, состоящей из n ВМ (линейке), где n – число неизвестных системы уравнений.

Пусть ВС с п² ВМ имеет граф межмодульных связей в котором, каждая вер­шина с индексами (i,j) графа информационных связей, приведенного на рисунке 2.2.8, отображается в соответствующий ВМ_ij, i = 1, ... , п, j = 2, ... , п + 1. Информационным связям между операторами алгоритма соответствуют передачи данных по межмо­дульным линиям связи.

Будем полагать, что для программирования передачи данных в передающем ВМ используется оператор send x (а), где х принимает значение u(up), d(down), l(left), r(right) в за­висимости от того, какому соседу предназначены для передачи данные а. Аналогично, в принимающем ВМ программирование выборки из входных очередей выполняется посредством оператора receiver x (b), где х принимает значения u, d, l, r в зависимос­ти от того, от какой ВМ идёт приём данных. Принятый элемент данных - b.

Предположим, что в каждый ВМ_ij. начиная с j = 3 по j = п + 1 передан соот­ветствующий элемент a_ij исходной матрицы коэффициентов системы уравнений, а ВМ_i2 содержат по два элемента а_i1 и a_i2.

Вычисления начинаются в ВМ₁₂, который определяет значение 1/b₁₁ = 1/а₁₁ и посылает его правому соседу ВМ₁₃, после чего тот вычисляет с₁₂ = а₁₂/b₁₁ и посылает нижнему соседу ВМ₂₂. Прием данных стартует вычисления в ВМ₁₃ и ВМ₂₂.

ВМ₁₃ передает полученное значение 1/b₁₁ своему правому соседу ВМ₁₄ и вычис­ляет с₁₃ = а₁₃/b_11. Вычисленное значение с₁₃ передается нижнему соседу ВМ₂₃.

ВМ₂₂, получив с₁₂, пересылает это значение нижнему соседнему ВМ₃₂, затем по­сылает хранящееся в нем значение b₂₁ = а₂₁ правому соседнему ВМ₂₃, а также вычис­ляет 1/b₂₂ = 1/(a₂₂- b₂₁с₁₂). Далее значение 1/b₂₂ передается в ВМ₂₃.

После описанных выше действий стартуют ВМ₃₂, ВМ₂₃ и ВМ₁₄. Таким об­разом вычисления ВМ начинаются при приёме данных. Прямой ход заканчивается в ВМ_n,n+1.

Обратный ход инициируется ВМ_n,n+1, который сразу по завершении прямого хода имеет вычисленное значение х_n, он передаёт его верхнему соседу ВМ_n-1,n+1 . Получив это значение, ВМ_n-1,n+1 передает его верхнему соседнему ВМ_n-2,n+1, а так­же использует, совместно с полученным от соседнего ВМ_n-1,n значением с_n-1,n, для вычисления x_n-l = c_n-1,n+l - c_n-l,nx_n. Далее х_п-1 передается в ВМ_n-2,п+1. Обратный ход завершается определением х₁ в ВМ_1,n+1.

Представленный способ выполнения параллельных вычислений по алгоритму Гаусса позволяет получить следующую оценку времени реализации [26]: Т_n*n = 5n-4 при общем числе операций порядка n³ / 3, что дает оценку ускорения параллельных вы­числений порядка п² /15.