Пусть - заданная невырожденная матрица (*), – известный (*1)-вектор, а – неизвестный (*1)-вектор. Рассмотрим систему линейных алгебраических уравнений

 (1)

Положим, что матрица является плотной.
Простейший вариант метода исключения Гаусса.
имеет вид:
  1. Итерация 1. Полагаем . Находим в первом столбце первый ненулевой элемент матрицы (если такой элемент отсутствует, то матрица – вырожденная и вычисления заканчиваются). Здесь - расширенная -матрица системы (1), т.е.

  2. Если 1, то меняем местами строки 1 и матрицы .
  3. Из каждого элемента -строки матрицы вычитаем величину , т.е. полагаем
     (2)

    где - -строка матрицы . При этом для всех элемент в первом столбце обращается в ноль.
  4. Итерация 2. В полученной матрице зафиксируем первую строку и первый столбец. Для оставшейся -матрицы повторим шаги 1 – 3. В результате получится матрица .
  5. Итерация 3. В матрице зафиксируем две первых строки и два первых столбца. Для оставшейся -матрицы повторим шаги 1 – 3. В результате получится матрица .
  6. И т.д.
После завершения итераций система (1) преобразуется к системе вида
 (3)

Заметим, что в последней формуле игнорирована перестановка элементов вектора в результате прямого хода исключения Гаусса.

  1. Итерация 1. Из -го уравнения системы (3) имеем
     (4)

  2. Итерация 2. Из формулы (4) и -го уравнения системы (3) имеем
     (5)

  3. И т.д
В вычислительной практике простейший метод исключения Гаусса используется редко из-за его неустойчивости к вычислительным погрешностям. Обычно используется метод исключения Гаусса с выбором ведущего элемента. Рассмотренная схема при этом усложняется необходимостью отыскания на каждой итерации максимального по модулю элемента в соответствующем столбце матрицы, а также необходимостью перестановки столбцов матрицы.
Заметим, что метод исключения Гаусса устойчив, в частности, если матрица – симметрична и положительно определена и является матрицей с диагональным преобладанием.
Простейший параллельный алгоритм метода исключения Гаусса.
Положим прежде, что количество процессоров в MIMD-системе с распределенной памятью равно и данные распределены по процессорам так, как показано на рис. 1. Здесь --ая строка матрицы .
Схема простейшего параллельного алгоритма метода исключения Гаусса имеет следующий вид.


  1. Итерация 1. Рассылаем первую сроку матрицы процессорам ,,...,.
  2. По формуле (2) параллельно на каждом из процессоров вычисляем компоненты строки матрицы , [2,].
  3. Итерация 2. Рассылаем вторую сроку матрицы процессорам ,,...,.
  4. По формуле (2) параллельно на каждом из процессоров вычисляем компоненты строки матрицы , [3,].
  5. И т.д.

  6. Итерация 1. По формуле (4) на процессоре вычисляем величину .
  7. Посылаем эту величину процессорам ,,...,.
  8. Итерация 2. По формуле (5) на процессоре вычисляем величину .
  9. Посылаем эту величину процессорам ,,...,.
  10. И т. д
Рис. 1.  К схеме параллельного алгоритма метода исключения Гаусса. . Ai -i-ая строка матрицы A.
Заметим прежде, что после завершения работы рассмотренного алгоритма все компоненты вектора окажутся на процессоре .
Легко видеть, что рассмотренная схема простейшего алгоритма метода исключения Гаусса порождает проблему сильной несбалансированности загрузки процессоров системы. Действительно, после завершения первой итерации прямого хода процессор простаивает вплоть последней итерации обратного хода. Аналогично, после завершения второй итерации прямого хода процессор простаивает вплоть до итерации (-1) обратного хода, а затем снова простаивает вплоть до завершения вычислений. И т.д.
Модификации простейшего параллельного алгоритма метода исключения Гаусса.
Рассмотрим более реалистичную ситуацию, когда - количество уравнений системы (1) превышает количество процессоров в вычислительной системе. Для простоты записи положим, что .
Слоистая схема хранения матрицы. При этом первые строк матрицы можно расположить на процессоре , вторые строк - на процессоре . И т.д. В данном случае первый процессор будет простаивать после итераций, второй процессор – после 2 – итераций. И т.д. Однако в здесь можно организовать параллельные вычисления и пересылки данных, что несколько повышает сбалансированность загрузки процессоров. Так, после завершения процессором первой итерации возможно параллельное вычисление этим процессором компоненты строки матрицы и посылка строки процессорам ,,...,.
Циклическая слоистая схема хранения матрицы. При этом строки матрицы размещаются на процессорах следующим образом:
Такая схема хранения практически снимает проблему несбалансированности загрузки процессоров.
Все рассмотренные схемы хранения матрицы используют хранение по строкам. Легко получить модификации простейшего алгоритма метода исключения Гаусса при хранении этой матрицы по столбцам.
Если является симметричной положительно определенной матрицей, то вместо гауссового исключения часто используется разложение Холесского, когда матриц представляется в виде =, где - нижняя треугольная матрица.
Для решения системы (1) также применяется представление матрицы в виде =, где – ортогональная, а – верхняя треугольная матрицы. Представление = может быть получено с помощью преобразования Хаусхолдера и преобразования Гивенса.
В вычислительной практике, например, при решении краевых задач для уравнений в частных производных методом конечных разностей и методом конечных элементов, возникают СЛАУ с разреженными (ленточными) матрицами . Решение таких задач может быть получено с помощью метода исключения Гаусса и упомянутых выше других прямых методов. Разработано также множество специальных прямых методов, ориентированных на ленточные системы, например, блочные методы, метод циклической редукции и пр. Отметим, что при решении ленточных СЛАУ как на последовательных, так и на параллельных вычислительных системах, для хранения матрицы целесообразно использовать не двумерный (*) массив, а совокупность одномерных массивов для хранения отличных от нуля диагоналей матрицы , либо один одномерный массив, в котором диагонали матрицы хранятся последовательно друг за другом.