Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Алгоритм минимальной степени.

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

Логика алгоритма.

Пусть в графе помечены узлы {x1,…,xi-1}. Число ненулевых элементов в этих столбцах графа заполнения в дальнейшем не меняется. Для уменьшения числа ненулевых элементов i-го столбца в еще не факторизованной подматрице на место i-го столбца нужно перевести столбец с наименьшим числом ненулевых элементов. Другими словами алгоритм минимальной степени можно рассматривать, как метод уменьшения заполненности путем локальной минимизации.

Описание алгоритма.

Пусть есть непомеченный граф G₀ = (X,E).

Шаг 1 (инициализация). i←1.

Шаг 2(выбор минимальной степени). В графе исключения G_i-1 = (X_i-1 ,E_i-1) выбрать узел x_i имеющий в G_i-1 наименьшую степень.

Шаг 3 (преобразование графа). Построить новый граф исключения G_i= (X_i,E_i), исключая из G_i-1 узел x_i.

Шаг 4 (цикл или остановка). i←i+1. Если I> |X| - остановка. В противном случае перейти к шагу 2.

В качестве иллюстрации приведем таблицу.

Примечание. На отдельных шагах может быть несколько узлов с минимальной степенью. В таком случае мы выбираем произвольный из таких узлов. Однако различные стратегии выбора в подобной стратегии неоднозначности дают различные варианты алгоритма минимальной степени.

11.4.4. Определение начального узла

Цель состоит в том, чтобы найти пару узлов, удаленных друг от друга на максимальное или почти максимальное расстояние. Значительный практический опыт свидетельствует, что такие узлы хороши в качестве начальных для нескольких алгоритмов упорядочения, в том числе для алгоритма RCM (Reverse Cuthill-McKee)

Расстояние d(x,y) между двумя узлами x и y связного графа G=(X,E) есть просто длина кратчайшего пути, соединяющего эти узлы.

Эксцентриситет узла Х: e(x)=max{d(x,y), где yX}

Диаметр графа G: (G)=max{e(x), xX}

или эквивалентно: (G)=max{d(x,y), x,yX}

Узел xX называется периферийным, если эксцентриситет равен диаметру графа, т.е. если e(x)= (G).

Пример графа:

При этом периферийные узлы X₂, X₅, X₇.

Таким образом, наша цель состоит в описании эвристического эффективного алгоритма для определения узлов с большим эксцентриситетом.

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

Основной конструкцией алгоритма является корневая структура уровней

Алгоритм принадлежит Гиббсу и соавторам (1976г.)

Шаг 1. инициализация: выбрать в Х произвольный узел r.

Шаг 2. построение структуры уровней:

а) построить структуру уровней с корнем в r .

б) определить e(r).

Шаг 3. стягивание последнего уровня: выбрать в последнем уровне узел Х с минимальной степенью.

Шаг 4. построение структуры уровней:

а) построить структуру уровней с корнем в Х.

б) если e(x) > e(r), положить r  x и перейти к шагу 3.

Шаг 5 (финиш). Узел Х является псевдопериферийным.

Для построения структуры уровней возьмем в качестве начального узел 10.

Выбираем в последнем уровне узел 5 с минимальной степенью (могли бы взять узел 3) и снова строим структуру уровней..

Строим структуру уровней от узла 3.

Таким образом, судя по эксцентриситету в качестве периферийных могут выступать узлы 3,5 и 8.

Мы уже убедились ранее, что перенумерация, производимая от узла 3 привела к профилю, равному 18. Применим алгоритм RCM, начиная от узла 8.

11.5. Сравнение методов упорядочения матриц.

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

Перечислим классы наиболее эффективных методов.

1. Ленточные методы (LR, CM).

2. Профильные методы (RСМ).

3. Универсальные разреженные методы (QMD).

4. Методы фактор-деревьев для конечно-элементных и конечно-разностных задач (RQT).

5. Методы параллельных сечений для конечно-элементных задач (IWD).

6. Методы вложенных сечений (ND).

LR – алгоритм Розена

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

RCM - обратный алгоритм Катхилла-Макки.

RQT - алгоритм древовидного разбиения.

IWD - алгоритм параллельных сечений.

QMD - алгоритм минимальной степени.

ND - алгоритм вложенных сечений.

Нельзя заранее сказать - какой метод лучше, т.к. типы разреженности весьма разнообразны.

Главными критериями являются:

Характеристики

Список файлов лекций