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

Презентация:



Advertisements
Похожие презентации
1. МАТРИЦЫ И СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ 1.1. Матрицы. Действия с матрицами Определение 1.1. Таблица вида: (1.1) в которой все – заданные числа, называется.
Advertisements

Линейная алгебра Определители второго порядка Системы из двух линейных уравнений с двумя неизвестными Определители n – ого порядка Методы вычисления определителей.
{ определение – типы матриц – сложение матриц – умножение матриц – свойства операции умножения – умножение матрицы на число – полином от матриц – транспонирование.
§ 3. Ранг матрицы ОПРЕДЕЛЕНИЕ. Минор M k матрицы A называется ее базисным минором, если он отличен от нуля, а все миноры матрицы A более высокого порядка.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Лекция 9 Отношения, графы Определения. Определение. Пусть а и b объекты. Через (а, b) обозначим упорядоченную пару, состоящую из объектов а и b, взятых.
Алгоритм Флойда-Уоршалла Находит кратчайшие расстояния между всеми парами вершин графа Идея: Строится специальная матрица D, элементы которой – кратчайшие.
Линейная алгебра Определители второго порядка Системы из двух линейных уравнений с двумя неизвестными Определители n – ого порядка Методы вычисления определителей.
Метод конечных элемнтов Кафедра Юнеско по НИТ, Рейн Т.С.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.
Графы Волновой метод. Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа
Системы n линейных уравнений с n неизвестными. Определение: Определение. Система n уравнений с n неизвестными в общем виде записывается следующим образом:
1.2. Элементарные преобразования матриц Определение 1.7. Элементарными преобразованиями матрицы А называются следующие преобразования: 1) перестановка.
ВВЕДЕНИЕ В ВЫЧИСЛИТЕЛЬНУЮ МАТЕМАТИКУ Лекция 5 6 октября 2009 ВЫЧИСЛИТЕЛЬНАЯ ЛИНЕЙНАЯ АЛГЕБРА.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
А.В. ПОПОВ Институт кибернетики им. В.М. Глушкова НАН Украины Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами
1. Матрицы Элементы линейной алгебры. Матрицы Матрицей размера m n называется прямоугольная таблица чисел, состоящая из m строк и n столбцов. Числа a.
ВВЕДЕНИЕ В ВЫЧИСЛИТЕЛЬНУЮ МАТЕМАТИКУ Лекция 4 29 сентября 2009 ВЫЧИСЛИТЕЛЬНАЯ ЛИНЕЙНАЯ АЛГЕБРА.
Теория графов Алгоритмы на графах. Медиана графа Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.
Транксрипт:

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

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

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

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

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

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

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 Выбор в множестве узлов 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 Строк – 1130 Половина ширины ленты – 44 Не нулевые элементы Строк – 1130 Половина ширины ленты – 45 Не нулевые элементы Полученные результаты Профиль матрицы жесткости после перенумерации узлов программой GridGen Профиль матрицы жесткости после перенумерации узлов методом Катхилла-Макки

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

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

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

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