LEC-30 (Материалы к лекциям)

15

Лекция № 30

12.4.2. Профильные методы.

Несколько более сложной схемой использования разреженности являются методы, в котором удается извлечь выгоду из изменения так называемый оболочки или профиля . Оболочка матрицы А, обозначаемая через Еnv(A) определяется как:

Еnv(A)={ { i , j }, 0  i-j  _i(A) }

То же самое можно записать посредством столбцовых индексов f_i(A)

f_i(A)=min{j , a_ij0} т.е. Еnv(A)={{i,j}, f_i(A)j<i}

Величина Еnv(A) называется профилем или размером оболочки А. Справедлива формула: Еnv(A)=

Введём ещё одно понятие – ширина фронта.

Для матрицы А i-ая ширина фронта определяется как

k>i и для некоторого l ≤ i

Заметим, что есть число «активных» строк на i-м шаге разложения, т.е. число строк оболочки А , которые пересекают i-й столбец.

Величину обычно называют шириной фронта или волновым фронтом А. Нижеприведённый пример иллюстрирует это понятие.

Очевидно, что Еnv(A)= ;

Доказывается, что число операций, необходимых при разложении А в произведение 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-й шириной фронта.

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

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

12.4.2.1. Обратный алгоритм Катхилла-Макки (вариант Джорджа 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.