Другие задачи для кластера

Кроме задачи Дирихле есть и другие задачи для кластера. На самом деле можно взять любое дифференциальное уравнение, перевести его к какой-либо конечно-разностной схеме и решать. Можно уже пойти дальше и применить метод конечных элементов. Всем этим я мог бы заниматься, но не занимаюсь. А всё потому что у меня сменился научный руководитель и тема. Опишу пару задач, которые я тоже делал, но они оказались довольно простыми и особо я на них не зацикливался. Это была проба пера и технологии MPI.

Метод Гаусса

Остановимся подробней на задаче решения системы линейных алгебраических уравнений методом Гаусса. Эта задача представлена формулой (1).

(1)

Для расспараллеливания этой задачи, а так же реализации схемы разделения секрета, разобьём исходную матрицу на блоки, причём размерность A много больше D. Таким образом получаем формулу (2).

(2)

Приведём систему к виду (3). Для этого вычислим обратную матрицу A^-1 и матричные произведения CA^-1B и CA^-1F₁.

(3)

Затем найдём промежуточное решение, используя формулу (4), и возвратим данные на клиентскую машину:

(4)

После чего значения X вычисляются на клиентской машине. При данной схеме распараллеливания блок D и часть вектора F₂ не будут скомпрометированы, так как не попадут в ЦОД, а будут обрабатываться только на машине клиента. Для того чтобы злоумышленник получил всю матрицу M, по которой он мог бы восстановить моделируемый объект ему необходимо перебрать все возможные матрицы D и вектора F₂. При должном размере этих блоков задача перебора станет принципиально нерешаемой.

Хотелось бы отметить, что для матрицы M, размерность которой слишком велика, т. е. матрица не помещается в оперативную память одной клиентской машины целиком, при реализации данной параллельной схемы будет так же получен выигрыш в памяти и скорости.

Формула Фробениуса

Другая массовая задача, вычисление обратной матрицы может быть решена с помощью формулы Фробениуса:

(5)

Где и A^-1 существуют. Для данной задачи, как и для предыдущей матрица разбивается на блоки, но все эти блоки обрабатываются в ЦОД. Сначала обращается матрица A, затем считаются произведения C A^-1 и C A^-1 B. После чего считается разность D — C A^-1 B и обращается матрица H. Затем вычисляются -H^-1 C A^-1 и -A^-1 B H^-1. Последним этапом можно вычисляется A^-1 + A^-1 B H^-1 C A^-1.

Оставшиеся задачи

Если предыдущие задачи были мной запрограммированы, то следующие ещё нет. И я не знаю буду ли я это делать или нет. С одной стороны это интересно, но с другой это довольно накладно и никакого вознаграждения.

1. Задача объекта в потоке и завихрениях среды.
2. Задача о колебаниях мембраны в потоке.
3. Задача области давления.
4. Посмотреть алгоритмы дискретной математики (теории графов) и возможно запрограммировать их.