Рассмотрим эллиптическое уравнение в частных производных - уравнение Пуассона
 (1)

где - заданная скалярная функция двух аргументов, определенная на единичном квадрате , - искомая функция, заданная на границе множества (см. Рис.1).
Рис. 1.  Множество Ω и его дискретизация.
Покроем множество равномерной сеткой с шагом по обоим координатным направлениям и обозначим (см. Рис. 1). Аппроксимировав производные в уравнении (1) центральными конечными разностями второго порядка, получим систему уравнений
 (2)

относительно неизвестных значений функции во внутренних узлах сетки (в узлах, которые лежат на границе области , значения этой функции, согласно постановке задачи, известны).
Положим, что для системы (1) выполнены условия существования и единственности решения. Не будем затрагивать вопросы сходимости используемой разностной схемы к решению сходного уравнения.
Легко видеть, что система уравнений (2) представляет собой систему линейных алгебраических уравнений относительно неизвестных . Положим и запишем эту систему в привычном виде
 (3)

где -вектор и -матрица определяются следующим образом:


Здесь - -матрица, – единичная -матрица. Вектор в уравнении (3) имеет размерность и состоит из величин , скорректированных в приграничных точках сетки при помощи известных значений функции на границе области .
Система линейных алгебраических уравнений (3) является ленточной (содержит пять отличных от нуля диагоналей) и может быть, вообще говоря, решена методами, рассмотренными в главе 3, или методом переупорядочивания неизвестных.
Рассмотрим решение системы (3) итерационным методом типа метода Якоби. Итерационную формулу построим, исходя непосредственно из формулы (2), следующим образом:
 (4)

Формула (4) показывает, что приближение к решению уравнения (1) в точке на -ой итерации вычисляется на основе среднего арифметического значений функции (,) в ближайших «слева», «справа», «снизу» и «сверху» узлах сетки на предыдущей итерации (итерация при считается нулевой). При этом все значения могут быть вычислены параллельно.
В качестве условия окончания итераций (4) можно использовать условие
 (5)

где - заданная константа.
Положим, что количество узлов сетки по горизонтали и вертикали кратно количеству процессоров в вычислительной системе, т.е. величина кратна величине и .
Схема параллельного итерационного метода типа метода Якоби.
  1. Строим сетку и разбиваем область по узлам этой сетки на подобласти . Расширяем каждую из подобластей двумя дополнительными рядами узлов по узлов в каждом, а каждую из областей - одним аналогичным дополнительным рядом узлов (см. Рис.2). Распределяем по процессорам расширенные подобласти так, как показано на Рис.2. Полагаем счетчик числа итераций .
  2. Параллельно на всех процессорах системы задаем некоторое начальное приближение к решению задачи :
  3. Параллельно на всех процессорах системы по формуле (4) вычисляем следующее приближение к решению уравнения (1):
  4. Параллельно на всех процессорах системы обмениваемся вычисленными значениями в смежных рядах узлов и записываем эти значения в дополнительные ряды узлов:
      • посылаем процессору значения в ряде узлов ,
      • принимаем от процессора значения в ряде узлов и записываем их в дополнительный ряд ;
    • на процессоре параллельно
      • посылаем процессору значения в ряде узлов ,
      • принимаем от процессора значения в ряде узлов и записываем их в дополнительный ряд ;
      • посылаем процессору значения в ряде узлов ,
      • принимаем от процессора значения в ряде узлов и записываем их в дополнительный ряд ;
    • ….;
    • на процессоре параллельно
      • посылаем процессору значения в ряде узлов ,
      • принимаем от процессора значения в ряде узлов и записываем их в дополнительный ряд ;
  5. Параллельно на всех процессорах системы вычисляем значение величины, необходимые для проверки условия окончания итераций (5):
  6. Передаем вычисленные значения на один из процессоров системы и проверяем выполнение условия (5);
  7. Если условие (5) выполнено, то передаем одному из процессоров значения в «своих» узлах и заканчиваем вычисления. Иначе, переходим к п. 3 для выполнения следующей итерации
Рис. 2.  Распределение расширенных подобластей по процессорам системы.
Рассмотренная схема параллельного алгоритма адекватна параллельной вычислительной системе с топологией коммуникационной сети типа "линейка"(см. главу 1.1). В этом случае наравне с разбиением области на подобласти по вертикали, можно использовать разбиение по горизонтали.
Рассмотрим ситуацию, когда вычислительная система имеет топологию коммуникационной сети типа «двумерная решетка» или «двумерный тор». В этом случае может быть рациональна иная схема декомпозиции области на подобласти. Положим, что процессоры вычислительной системы объединены коммуникационной сетью в двумерную -решетку (см. Рис. 3) и количество узлов сетки по горизонтали и вертикали кратно , т.е. . Разобьем область на подобласти и расширим каждую из подобластей , кроме граничных, четырьмя дополнительными рядами узлов по узлов в каждом, каждую из граничных подобластей, кроме угловых – тремя аналогичными дополнительными рядами узлов, а каждую из угловых подобластей - двумя аналогичными дополнительными рядами узлов (см. Рис.3).
Рис. 3.  Декомпозиция области Ω на подобласти и образование расширенных подобластей.
Распределим по процессорам расширенные подобласти так, как показано на Рис.4.
Рис. 4.  Распределение подобластей по процессорам системы.
Схема параллельного алгоритма в этом случае отличается от рассмотренной схемы только межпроцессорными обменами. Так процессор, которому распределена не граничная подобласть, на каждой итерации должен получить значения в соответствующих рядах узлов от ближайших своих соседей «слева», «справа», «снизу», «сверху» и передавать им значения в «своих» граничных рядах (см. Рис.5).
Рис. 5.  Схема обменов данными между соседними подобластями.