Адаптивные сетки

В предыдущих статьяъ был предложен метод разделения данных при решении задачи Дирихле для уравнения Лапласа. В данной статье рассматривается аналогичная задача, но с использованием адаптивных сеток. Адаптивные сетки это сетки с непостоянным размером ячеек. Где надо у их ячеек большой шаг. Где надо наоборот мелкий, для более точного решения.

Сетки типа восьмеричное дерево

При решении задачи конечно-разностным методом может возникнуть потребность в измельчении сетки для того, чтобы получить более равномерное решение на границе области. Подобный подход имеет место быть на задачах малой размерности. В случае задачи большой размерности уменьшение шага сетки в два раза может привести к увеличению времени расчёта более чем в 4 раза, поскольку размер сетки увеличится в 4 раза. Для того чтобы падение производительности не было таким резким используются адаптивные сетки, т. е. сетки с переменным шагом. В литературе наибольший обзор получил тип сеток «восьмеричное дерево». Сетка такого типа в подобластях, значения которых наиболее интересны, декомпозируется на несколько сеток с размером шага отличным в 2 раза, затем эти сетки накладываются друг на друга. Пример такой сетки можно увидеть на рис.1.

Рис. 1. Пример сетки типа « восьмеричное дерево»

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

Сетки с последовательно уменьшающимся шагом

Кроме сеток типа «восьмеричное дерево» можно применять сетки с последовательно уменьшающимся шагом. В данном случае шаг постепенно уменьшается в q раз, где q — коэффициент сгущения сетки. Благодаря такому подходу отсутствуют места резкого уменьшения сетки, а значит, ошибки, полученные из-за наложения, так же будут нивелированы. Конечно разностные аналоги для сетки с постоянным шагом:

Будут изменены для сетки с переменным шагом:

Рассмотрим область G с L-образным объектом внутри неё. Наибольший интерес в данной задаче представляет граничная область внутреннего угла L-объекта. На рис.2. представлена графическая постановка задачи.

Рис. 2. Графическая постановка задачи с L-объектом

Для решения поставленной задачи разобьём область на 14 подобластей, одна из которых будет решаться на машине клиента, а другие на стороне ЦОД. После вычислений полученное решение будет вновь объединено в одну область. Разбиение можно увидеть на рис.3.

Рис. 3. Разбиение задачи на 14 подобластей

Данное разбиение является примером схемы разделения секрета. Наиболее важная область 1 должна обрабатываться только на вычислительном устройстве клиента. Не имея данных о форме и границе объекта, владелец ЦОД не сможет их восстановить по граничным значениям области 1, поскольку для этого ему будет необходимо решить обратную задачу. Следует отметить, что для более точного описания процесса протекающего на границе внутреннего угла L-объекта, подсетки областей 7, 4 и 8 будут сгущаться в сторону внутреннего угла.

Для данной постановки задачи было проведено несколько численных экспериментов на кластере, который состоит из 4-х узлов, содержащих по два четырёх-ядерных процессора Intel Xeon X5472 3.0GHz Quad Core и по 8 Гб оперативной памяти PC2-5300 ECC. Узлы соединены между собой каналом в 1 Гбит. Время вычислений, можно увидеть в таблице 1.

Таблица 1. Результаты экспериментов