Аннотация:Работ а Башева. А. А. по священа ре а лизации а лгоритмов
восстановления геометрической информации в сетке. Это актуальная тема,
так как данный подход позволяет сократить время расчета задачи на данной
с етке путем ее более каче ственной декомпозиции по узлам
многопроцессорной системы.
В данной работе рассматриваются алгоритмы основанные на методе
силового воздействия вершин графа. Были реализованы алгоритмы
Фрюхтермана-Рейнгольда и Yifan Hu. Также были разработан многопоточный
вариант алгоритма, который позволяет производить вычисления с
асимптотический ограничением O(|V| * log(|V|)) на итерацию. И
параллельный вариант алгоритма, который позволяет распараллелить
построение квадродерева и тем самым ускорить работу алгоритма.
Реализованные алгоритмы хорошо масштабируются.
Было произведено сравнение декомпозиции полученного с помощью
Metis и восстановленной геометрической информации и обычного Metis, без
геометрической информации. В случае работы с геометрической
информацией удалось получить более качественную декомпозиции по
метрике количества разрезанных между доменами ребер.