АльМасри Параллельные методы решения СЛАУ на вычислительном кластере

3.Классификация параллельных методов решения СЛАУ

Метод Гаусса–Зейделя. Пусть решаемая система представлена в виде[1-2]

Итерационная схема Гаусса–Зейделя следует из этого представления системы:

или

Приведем метод Гаусса–Зейделя к стандартному виду:

Стандартная форма метода позволяет выписать его итерационную матрицу и провести над ней очевидные преобразования:

Представим метод Гаусса–Зейделя в координатной форме для системы общего вида:

Координатная форма метода Гаусса–Зейделя отличается от координатной формы метода Якоби лишь тем, что первая сумма в правой части итерационной формулы содержит компоненты вектора решения не на k-й, а на (k+1)-й итерации.

Параллельный алгоритм метода Гаусса–Зейделя

Отличие метода Гаусса–Зейделя от метода простой итерации заключается в том, что новые значения вектора вычисляются не только на основании значений предыдущей итерации, но и с использованием значений уже вычисленных на данной итерации .

Текст последовательной программы для вычисления новых значений компонент вектора представлен ниже.

void GaussZeidel (double *A, double *X, int size)

/* задана матрица А, начальное приближение вектора Х,

размерность матрицы size, вычисляем новое значение вектора Х */

{ unsigned int i, j;

double Sum;

for (i = 0; i < size; ++i) {

Sum = 0;

for (j = 0; j < i; ++j)

Sum += A[ind(i,j,size)] * X[j];

for (j = i+1; j < size; ++j)

Sum += A[ind(i,j,size)] * X[j];

X[i]=(A[ind(i,size,size)] – Sum) / A[ind(i,i,size)];

}

Рис. 2. Процедура вычисления значений вектора по методу Гаусса-Зейделя

Следующая система уравнений описывает метод Гаусса-Зейделя.

Вычисления каждой координаты вектора зависят от значений, вычисленных на предыдущей итерации, и значений координат вектора вычисленных на данной итерации. Поэтому нельзя реализовывать параллельный алгоритм, аналогичный методу простой итерации: каждый процесс не может начинать вычисления пока, не закончит вычисления предыдущий процесс.

Можно предложить следующий модифицированный метод Гаусса–Зейделя для параллельной реализации. Разделим вычисления координат вектора по процессам аналогично методу простой итерации. Будем в каждом процессе вычислять свое количество координат вектора по методу Гаусса Зейделя, используя только вычисленные значения вектора данного процесса. Различие в параллельной реализации по сравнению с методом простой итерации заключается только в процедуре вычисления значений вектора (вместо процедуры Iter_Jacoby используем процедуру Gauss-Seidel).

void GaussZeidel(int size, int MATR_SIZE, int first)

/* задана матрица А, размерность матрицы MATR_SIZE, количество

вычисляемых элементов вектора в данном процессе size, вычисляем новые

значения вектора Х с номера first, используя значения вектора Х */

{ int i, j;

double Sum;

for (i = 0; i < size; ++i) {

Sum = 0;

for (j = 0; j < i+first; ++j)

Sum += A[ind(i,j,MATR_SIZE)] * X[j];

for (j = i+1+first; j < MATR_SIZE; ++j)

Sum += A[ind(i,j,MATR_SIZE)] * X[j];

X[i+first]=(A[ind(i,MATR_SIZE,MATR_SIZE)] – Sum) /

A[ind(i,i+first, MATR_SIZE)];

}

Рис. 1. Процедура вычисления значений вектора по методу Гаусса–Зейделя(параллельная версия)