Алгоритм Катхилла-Макки. 2 Основные определения Граф можно представить себе состоящим из конечного множества узлов, или вершин, вместе с множеством ребер, - презентация

1 Алгоритм Катхилла-Макки

2 2 Основные определения Граф можно представить себе состоящим из конечного множества узлов, или вершин, вместе с множеством ребер, которые по сути есть неупорядоченные пары вершин Граф можно представить себе состоящим из конечного множества узлов, или вершин, вместе с множеством ребер, которые по сути есть неупорядоченные пары вершин Упорядочение графа есть отображение множества на Упорядочение графа есть отображение множества на Пусть - симметричная матрица порядка N. Упорядоченный граф матрицы, обозначаемый – это граф, для которого N вершин пронумерованы числами от 1 до N и тогда и только тогда, когда Пусть - симметричная матрица порядка N. Упорядоченный граф матрицы, обозначаемый – это граф, для которого N вершин пронумерованы числами от 1 до N и тогда и только тогда, когда

3 3 Матрица и ее помеченный граф

4 4 Основные определения Два узла называются смежными, если Два узла называются смежными, если Для степень, обозначаемая, есть число Для степень, обозначаемая, есть число Путем из x в y длины l>=1 называется упорядоченное множество из l+1 различных узлов Путем из x в y длины l>=1 называется упорядоченное множество из l+1 различных узлов Эксцентриситет узла x есть Эксцентриситет узла x есть Диаметр графа Диаметр графа Узел называется периферийным, если Узел называется периферийным, если

5 5 Машинное представление графа

6 6 Матрица жесткости метода естественных соседей, МКЭ, MFEM является разреженной, симметричной, положительно определенной. Матрица жесткости метода естественных соседей, МКЭ, MFEM является разреженной, симметричной, положительно определенной. Решение СЛАУ матрицы жесткости Количество ненулевых элементов в строке равно количеству естественных соседей, а позиция ненулевых элементов зависит от номера узла. Профиль матрицы жесткости Строк – 1130 Половина ширины ленты – 1128 Не нулевые элементы

7 7 Определение первоначального узла r. Присвоение этому узлу номер 1, т.е. x(1)=r Определение первоначального узла r. Присвоение этому узлу номер 1, т.е. x(1)=r Для каждого узла i найти всех ненумерованных соседей. Перенумеровать соседей в порядке возрастания степеней. Для каждого узла i найти всех ненумерованных соседей. Перенумеровать соседей в порядке возрастания степеней. Обратное упорядочение Катхилла-Макки y(i)=x(N- i+1) Обратное упорядочение Катхилла-Макки y(i)=x(N- i+1) Перенумерация узлов сетки методом Катхилла-Макки

8 8 Выбор в множестве узлов X произвольного узла r Выбор в множестве узлов X произвольного узла r Построение структуры уровней l(r) с корнем в r Построение структуры уровней l(r) с корнем в r Стягивание последнего уровня – выбор в последнем уровне узла x с минимальной степенью и построение новой системы l(x) уровней с корнем в x. Стягивание последнего уровня – выбор в последнем уровне узла x с минимальной степенью и построение новой системы l(x) уровней с корнем в x. Если глубина l(x) >l(r), то r=x и выполняем снова шаг 2. Если глубина l(x) >l(r), то r=x и выполняем снова шаг 2. Определение первоначального узла методом Гиббса Представление матрицы жесткости в виде графа

9 9 Строк – 1130 Половина ширины ленты – 44 Не нулевые элементы Строк – 1130 Половина ширины ленты – 45 Не нулевые элементы Полученные результаты Профиль матрицы жесткости после перенумерации узлов программой GridGen Профиль матрицы жесткости после перенумерации узлов методом Катхилла-Макки

10 10 Профильный метод хранения СЛАУ Обозначим столбцовый индекс первого ненулевого элемента в строке Обозначим столбцовый индекс первого ненулевого элемента в строке i-ой шириной ленты назовем i-ой шириной ленты назовем Оболочкой A назовем Оболочкой A назовем

11 11 Профильная схема хранения

12 12 Решение СЛАУ методом Холесского с профильной схемой хранения матрицы где – симметричная положительно определенная матрица размером Применение метода Холесского приводит к треугольному разложению: где - нижняя треугольная матрица с положительными диагональными элементами. Отсюда Замена приводит к системе из двух треугольных СЛАУ: Рассмотрим решение системы линейных алгебраических уравнений:

13 13 Сравнение скорости работы методов решения СЛАУ