6CAD-CAE-23 Упорядочение (1014142), страница 7

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

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

Доказывается, что число операций, необходимых при разложении А в произведение LL^T выражается формулой:

, а число операций, необходимых для решения системы Ах=b при известном разложении А= LL^T, равно .

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

Рассмотрим пример. Пусть дан звездный граф с N узлами. Если N=9, то упорядочение с минимальным профилем и упорядочение с минимальной шириной ленты приведет к матрицам:

В этом примере число операций, необходимых при разложении матрицы, упорядоченной так, чтобы профиль был минимален, есть величина порядка N. В то же время это же число для матрицы, упорядоченной так, чтобы ширина ленты была минимальна, будет порядка N³, а L имеет порядка N² ненулевых элементов.

Интерпретация на языке графов.

Пусть симметричной матрице A размером N x N сопоставлен неориентированный граф G^A= (X^A, E^A), узлы которого помечены в соответствии с нумерацией строк А: Х^А = {х₁, …..,х_N}.

Если i<j, то включения {i,j } и равносильны.

Для i=1,………,N справедливо равенство: .

Рассмотрим прежнюю матрицу и соответствующий ей помеченный граф.

Смежными множествами здесь будут:

; ;

ø

Можно их сравнить со строчными индексами элементов оболочки в каждом столбце. Множество будет именоваться i-м фронтом помеченного графа, а число элементов этого множества (как и раньше) – i-й шириной фронта.

Ярким представителем профильных методов является обратный алгоритм Катхилла-Макки, основой которого служит обратное упорядочение.

Упорядочение, получаемое обращением упорядочения Катхилла – Макки, часто гораздо сильнее уменьшает профиль, чем первоначальное переупорядочивание, хотя ширина ленты остается неизменной. Это упорядочивание было названо обратным упорядочением Катхилла – Макки.

Обратный алгоритм Катхилла-Макки (вариант Джорджа 1971)

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

Так как схему Катхилла-Макки можно рассматривать как метод уменьшения ширины ленты матрицы посредством локальной минимизации чисел _i, то это приводит к предположению, что эту схему можно использовать и для уменьшения профиля матрицы.

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

Это упорядочение было названо обратным упорядочением Катхилла-Макки (RCM) (Reverse Cuthill-McKee). Позднее было доказано, что обратная схема всегда не хуже прямой в отношении хранения и обработки оболочки. (Liu 1975).

Для связного графа алгоритм RCM можно описать следующим образом.

Шаг 1. Определить начальный узел r и выполнить присвоение Х₁  r (вопрос о выборе начального узла разбирается в дальнейшем).

Шаг 2. (Основной цикл). Для i=1,...,N найти всех ненумерованных соседей узла X_i и занумеровать их в порядке возрастания степеней.

Шаг 3. (Обратное упорядочение). Обратное упорядочение Катхилла-Макки есть y₁, y₂, ... , y_N, где yi=X_N-i+1 для i=1,...,N .

В случае, если граф G^A несвязен, описанный выше алгоритм можно применять к каждой связной компоненте графа по очереди. Если начальный узел задан, алгоритм относительно прост.

Рассмотрение этого алгоритма будем проводить применительно к матрице, структура которой задана следующим графом:

Предположим, что в качестве начального узла взят узел 7 , т.е. Х₁=7.

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

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