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

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

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

Для наших целей граф G=(X,E) можно представить себе состоящим из конечного множества узлов, или вершин, вместе с множеством Е ребер, которые суть неупорядоченные пары вершин. Упорядочение (помечивание)  графа G=(X,E) есть попросту отображение множества {1,2,..., N} на Х; здесь N - число узлов G. Граф G, помеченный посредством , будем обозначать через G^=(X^,Е).

Пусть А - симметричная матрица порядка N.

Упорядоченный (помеченный) граф матрицы А, обозначаемый G^А=(X^А,Е^А), - это граф, для которого N вершин G^А пронумерованы числами от 1 до N и {X_i, X_j}Е^А тогда и только тогда,

когда а_ij = а_ij 0, i j. Здесь Х_i- узел Х^А с меткой i.

Чтобы подчеркнуть соответствие i-го диагонального элемента матрицы с узлом i ее графа, мы указываем этот элемент как i в кружочке. Внедиагональные элементы обозначены символом *.

Непомеченный граф А представляет структуру А без упоминаний о каком-либо конкретном упорядочении. Отыскание хорошей перестановки для А можно рассматривать как отыскание хорошего помечивания для ее графа.

Например:

Два узла Х и Y из G называются смежными, если {X,Y}Е. Если Y X ( Y есть подмножество X), то смежное множество для Y есть Аdj(Y)={xX-Y{X,Y}E для некоторого yY.

Другими словами Аdj(Y) - есть множество узлов G, не принадлежащих Y, но смежных хотя бы с одним узлом из Y.

Y={X₁, X₂} Аdj(Y)=X₃, X₄, X₆

Для YX степень Y, обозначаемая через Dеg (Y) есть число Аdj(Y).

Для примера Dеg(X₂)=3.

Подграф G(Y) -это граф матрицы, полученный из матрицы G вычеркиванием всех строк и столбцов, кроме тех, которые соответствуют Y.

Пусть Y=( X₂, X₃, X₆), тогда, если исходный граф G^A

Матрица подграфа G(Y) G(Y)

Этот же пример иллюстрирует понятие связности графа. Если X и Y -различные узлы G, то путем из X в Y длины L 1 называется упорядоченное множество из L+1 различных узлов (V₁, V₂,..., V_i+1), такое, что V_i+1 Аdj(V_i), i=1,2,...,L, причем V₁=x, V_L+1=y.

Граф называют связным, если каждая пара различных узлов соединена хотя бы одним путем. В противном случае G несвязен и состоит из двух или более связных компонент.

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

случае, если узлы i и j принадлежат одному и тому же конечному элементу.

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

Если методом конечных элементов решается двумерная задача, то получается двумерная сетка и скелетный граф является пло­ским. Если применяются треугольные элементы с тремя узлами, то конечноэлементный граф совпадает со своим скелетом, и, сле­довательно, также представляет собой плоский граф. Однако любой другой тип элементов, даже простые четырехугольники с че­тырьмя узлами, порождает граф, не являющийся плоским. Графы не являющиеся плоскими, но имеющие плоский скелет, назы­ваются почти плоскими графами. Указанное определение легко обобщается на случай трех пространственных измерений.

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

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

1. Хранение графа в двух массивах.

Пусть G=(X,E) - граф с узлами. Списком смежности для xX называется список, содержащий все узлы из Аdj(X).

Структура смежности графа G - это просто множество списков смежности для всех xX.

Такую структуру можно реализовать очень просто и экономично, храня списки смежности последовательно в одномерном массиве ADJNCY; дополнительный индексный массив XADJ длины N+1 содержит указатели начала каждого списка смежности в массиве ADJNCY.

Из программистских соображений часто бывает удобно иметь в XADJ дополнительную компоненту, так, чтобы переменная XADJ(N+1) указывала адрес первой свободной ячейки в массиве ADJNCY. Ясно, что общая длина массивов при такой схеме хранения равна: X+2E+1

Для доступа к соседям данного узла можно воспользоваться следующим программным сегментом:

........................

NBRBEG=XADJ(NODE)

NBREND=XADJ(NODE+1) -1

IF(NBREND.LT. NBRBEG) GO TO 200

DO 100 J= NBRBEG, NBREND

NABOR=ADJNCY(I)

.........................

100 CONTINUE

200

2. Таблица связей

Распространенной схемой хранения является простая таблица связей, имеющая N строк и m столбцов, где m=max{Deg(х)}.

Список смежности i-го узла хранится в i-ой строке. Эта схема хранения может быть очень неэффективной, если многие узлы имеют степень меньшую, чем m.

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

3. Эту трудность можно преодолеть, вводя поле связей.

Значением указателя HEAD(i) является начало списка смежности i-го узла; при этом в массиве NBRS находим соседа узла i, а в массиве LINK - указатель расположения следующего соседа этого узла.

Пусть, например, нужно отыскать соседей узла 5. Значение HEAD(5) равно 8. Обращаемся к NBRS(8) и получаем 3. Это один из соседей узла 5. Переходим к LINK(8) и находим там 2. Это значит, что следующего соседа узла 5 нужно искать в NBRS(2), где хранится 6.

Наконец, находим LINK(2)= -5, что указывает окончание списка смежности для узла 5. (Вообще отрицательная связь -i указывает окончание списка смежности для узла i). Общая длина массивов при таком способе представления графа равна: X+4E .

Если в массивах NBRS и LINK достаточно места, то легко можно добавлять новые ребра. Например, чтобы добавить к структуре смежности ребро {3,6}, изменим список смежности узла 3, полагая LINK(13)=1, NBRS(13)=6 HEAD(3)=13. Аналогичным образом изменим список смежности узла 6, полагая LINK(14)=5, NBRS(14)=3, HEAD(6)=14.

11.4. Методы упорядочения матриц и сопутствующие алгоритмы.

При упорядочивании имеется целый набор методов:

1. Ленточные методы.

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

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

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

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

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

7. Другие методы

Повторим, что при решении линейной системы Ax=b общий подход состоит в том, чтобы сначала найти перестановку или упорядочение P данной задачи. Затем система записывается в виде (РАР^T)(Рх)=Рb и тот же, например, метод Гаусса применяется к симметричной положительно определенной матрице РАР^T, что приводит к треугольному разложению LL^T. Решая эквивалентную переупорядоченную систему часто можно достичь уменьшения запросов к машинной памяти и времени ее исполнения.

11.4.1.Ленточные методы

Задача оптимальной нумерации узловых неизвестных сводится к задаче такой нумерации вершин графа , при которой максимальная величина разности номеров смежных вершин была бы минимальной (Тьюарасон, Розен).

Сложность сформулированной задачи об оптимальной нумерации узлов СКЭ во многом обусловлена большим числом возможных вариантов нумерации. Действительно, если число узлов сетки равно n, то существует n! возможных перестановок номеров узлов. Таким образом, даже при n=15 количество вариантов нумерации узлов составляет n! 10¹².

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

Это один из простейших подходов к решению разреженных систем.

Говоря приблизительно, цель здесь состоит в таком упорядочении матрицы, чтобы ненулевые элементы PAP^T группировались возле главной диагонали.

Такие упорядочения широко используются в практике.

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

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

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

Пусть (А)=max( _i(А) ) - ширина ленты; Band(A)- область матрицы, удаленная от главной диагонали не более, чем на (А) позиций.

Band(A)={ i , j } для 0 < i – j  (A)

Применение ленточного метода подразумевает, что нули вне Band(A) игнорируются. Нули же внутри ленты обычно хранятся, хотя их присутствие часто используется на этапе численного решения.

Использование разреженности основано на соотношении:

Band(A)= Band(L+L^T)

Обычным методом хранения симметричной ленточной матрицы является уже разобранная ранее диагональная схема хранения (Мартин, 1971г). Такая схема очень проста и вполне эффективна, если _i(A) не слишком меняется с изменением i. Число операций, необходимых для разложения матрицы А с шириной ленты  (в предположении, что лента Band( L+L^T ) полностью заполнена) равно:

Число операций, необходимых для решения системы Ах=b методом Холесского при известном множителе Холесского L равно:

2( +1)N - ( +1)

Ниже приведен простой пример, иллюстрирующий уменьшение ширины ленты матрицы путем перенумерования вершин соответствующего графа. После изменения номеров вершин графа , который соответствует матрице В, получается граф , которому соответствует матрица . В матрицах В и ширина ленты равна соответственно 5 и 3.



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

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