1. Метод вкладених перетинів Розглянемо тепер ще один підхід до отримання переупорядочивания матриці...

Метод вкладених перетинів

Розглянемо тепер ще один підхід до отримання переупорядочивания матриці - метод вкладених перетинів. Як і в попередньому пункті, для опису методу нам будуть потрібні деякі додаткові відомості з теорії графів.

відстанню між вершинами графа називається довжина найкоротшого шляху, що з'єднує ці вершини.

Найбільша відстань між будь-якими двома вершинами графа називається діаметром графа.

Найбільша відстань від вершини u до будь-якої іншої вершини називається ексцентриситетом вершини і позначається . Таким чином,

Якщо ексцентриситет вершини збігається з діаметром графа, то така вершина називається периферійної.

Псевдоперіферійная вершина u визначається наступною умовою: якщо - будь-яка вершина, для якої виконано умову , То буде виконано і умова e \ left (\ nu \ right) = e \ left (u \ right). Зазначене визначення гарантує, що ексцентриситет псевдоперіферійной вершини буде "близькою" до діаметру графа.

Граф називається зв'язковим, якщо для кожної пари його вершин знайдеться шлях, який їх пов'язує. В іншому випадку граф називають незв'язним. Всякий незв'язних граф складається з двох або більше компонент зв'язності.

Роздільником називається безліч вершин, видалення яких разом з інцидентними їм ребрами призводить до появи незв'язною графа (або до збільшення числа зв'язкових компонент, якщо граф уже був незв'язним). Роздільник називають мінімальним, якщо ніяке його власне підмножина не є роздільником. Роздільник, що складається з однієї вершини, називається розрізає вершиною.

Розбиттям графа називається угруповання вершин графа в попарно непересічні підмножини . Якщо граф незв'язних, і в якості підмножин обрані його компоненти зв'язності, то отримуємо розбиття на компоненти.

Одним з важливих класів розбиття, що використовуються при обробці розріджених матриць, є розбиття на рівні суміжності, тобто виявлення структури рівнів суміжності графа.

Структура рівнів суміжності , Що складається з m + 1 рівня, виходить, якщо зазначені підмножини визначені в такий спосіб:

Нагадаємо, що безліч для вершини є безліччю суміжних їй вершин. Число m називають довжиною структури рівнів суміжності, а ширина структури визначається як максимальна кількість вершин, що складають кожний рівень.

Важливим наслідком з визначення є той факт, що в структурі рівнів суміжності кожен рівень , 0 <i <m, є роздільником графа.

Розбиття на рівні суміжності називають кореневим з коренем , якщо , А кожне наступне безліч суміжно з об'єднанням попередніх, тобто

якщо складається з єдиною вершини u, то кажуть, що структура рівнів має корінь в вершині u.

Розглянемо тепер алгоритм побудови структури рівнів суміжності.

1. У графі V вибирається деяка вершина в якості кореневої. вважаємо .
2. Помічаємо цю вершину (присвоюємо їй перший номер)
3. Перебираємо всі вершини з безлічі , І для кожної його вершини визначаємо Непомічені суміжну їй вершину. Ці суміжні вершини утворюють рівень . Вони позначаються (нумеруються по порядку) і поміщаються в .
4. Якщо безліч непомічених вершин порожньо, то алгоритм завершено, інакше вважаємо i = i + 1, і переходимо на крок 3.

на Мал. 7.35 приведена матриця розрідженій системи лінійних рівнянь (ненульові елементи відзначені символом *) і відповідний їй граф, а на Мал. 7.36 зображена структура рівнів суміжності для даного графа з коренем у вершині 10. Довжина структури дорівнює 3, а ширина - 5. Відзначимо, що безліч вершин {1, 11} першого рівня і безліч вершин {6, 9, 7, 3, 8} другого рівня є роздільниками графа.

Мал.7.35.

Матриця і її графові уявлення
Мал. 7.36. Структура рівнів суміжності

Відповідно до книгами [9], [10] cформуліруем алгоритм відшукання псевдоперіферійной вершини r.

1. У графі V вибрати деяку вершину в якості кореневої.
2. Визначити структуру рівнів суміжності з коренем в r.
3. Вибрати в останньому рівні вершину x з мінімальним ступенем.
4. Визначити структуру рівнів суміжності з коренем в x.
5. якщо , То покласти , І перейти на крок 3.
6. Вузол x є псевдоперіферійним.

Після того, як введені всі необхідні поняття і розглянуті допоміжні алгоритми, сформулюємо ідею методу вкладених перетинів.

Нехай вихідній матриці A з (7.41) відповідає граф G (V, E). У графі G знаходимо роздільник , де . Будемо вважати, що вершини в графі перенумеровані так, що видалення вершини (І інцідентних з ним ребер) призводить до появи двох зв'язкових компонент і з вершинами , , і , , Відповідно. Так як є роздільником, то будь-яка i-я вершина НЕ буде досяжна для жодної j-й вершини з . В цьому випадку всі елементи фактора Холецкого з відповідними номерами будуть рівні 0, і заповнення не відбудеться.

Далі введемо нову нумерацію вершин (яка відповідає перестановці змінних в системі рівнянь): перенумеруем вершини в компонентах послідовно, від 1 до n-1 (для цього достатньо зменшити номера вершин в компоненті , Нумерація в залишиться колишньою), а k-й вершині дамо останній номер n, тобто перенумеруем як .

Потім в кожної виділеної компоненті і проводимо аналогічну процедуру: знаходимо роздільники в і в , Виділяємо чотири нові компоненти зв'язності: і з вершинами , , і , ; і з вершинами , , і , . Наступний крок алгоритму полягає в перенумерации вершин в межах компонент зазначеним вище способом: вершини компонент зв'язності нумеруються послідовно, разделителю присвоюється останній номер. Якщо в якої-небудь компоненті зв'язності не можна знайти роздільник, то в якості відповідного безлічі вибирається саме безліч і нумеруються всі його вершини. Виконання процедури припиняється, якщо всі компоненти зв'язності вичерпані.

При практичної реалізації алгоритму нумерацію можна організувати таким чином: нумерувати всі вершини роздільників S в зворотному порядку (від n до 1), як тільки таку силу-силенну буде отримано; вершини компонент зв'язності G залишаються непронумерованими. Остаточна нумерація вершин (тобто матриця перестановки) визначається безпосередньо після виконання алгоритму.

Слід зазначити, що роздільник S можна вибирати різними способами. Для того, щоб метод вкладених перетинів був максимально ефективним (тобто в результаті переупорядочивания виникали б великі нульові блоки в результуючому факторі L), слід дотримуватися наступних правил:

• по можливості вибирати мінімальний з усіх роздільників (ідеальний випадок - роздільник з однієї вершини):
• що виникають при видаленні роздільник компоненти зв'язності повинні бути приблизно однакового розміру.

Відомий метод вибору підходящого роздільник, описаний в [9], полягає в побудові для графа структури рівнів суміжності з коренем в псевдоперіферійной вершині і виборі малого роздільник з "середнього" рівня.

Дамо формальний опис методу вкладених перетинів. нехай - граф, асоційований з матрицею A. Тоді метод вкладених перетинів буде полягати в наступному.

1. Покласти R = V, n = \ left | V \ right |.
2. Знайти в G (R) зв'язну компоненту G (C) і побудувати для неї структуру рівнів суміжності з коренем в псевдоперіферійной вершині r, тобто .
3. якщо , То покласти S = ​​С і перейти до кроку 4. В іншому випадку покласти і визначити роздільник S як безліч вузлів таке, що
4. Перенумерувати вузли роздільник S числами від n до . покласти і . якщо , То перейти на крок 2.

На кроці 3 алгоритму роздільник S можна отримати простим відкиданням тих вузлів з , Які не суміжні з жодним вузлом з .

Докладне вивчення властивостей розглянутих нами алгоритмів може бути знайдено в книгах [9], [10].

результати експериментів

Для ілюстрації ми повернемося до розкладання розглянутих в п.3.5.3.2 матриць з колекції http://www.cise.ufl.edu/research/sparse/matrices/ . Також як і в минулий раз, порівняємо коефіцієнт заповнення вихідної матриці A, фактора L, отриманого "в лоб", і фактора , Отриманого після застосування перестановки, знайденої методом вкладених перетинів (див. Таблицю і малюнки нижче). Для порівняння наведено коефіцієнт заповнення факт , Отриманого після застосування перестановки, знайденої методом мінімальному обсязі.

Таблиця 7.13. Коефіцієнти заповнення матриці до і після розкладання Матриця A L shallow_water2 4,88281E-05 0,00687 0,00065 0,00075 pwtk 0,00024268 0,00803 0,00281 0,00256 parabolic_fem 1,32902E-05 0,16134 0,00019 0,00017 cfd2 0,000202489 0,02049 0,02048 0,00877

Для наочності наведемо портрети матриць, переупорядочение методом вкладених перетинів.

Мал.7.37.

Матриця shallow_water2, n = 81 920, nz = 204 800
Мал. 7.38. Матриця parabolic_fem, n = 525 825, nz = 2 100 225
Мал. 7.39. Матриця pwtk, n = 217 918, nz = 5 871 175
Мал. 7.40. Матриця cfd2, n = 123 440, nz = 1 604 423
Мал. 7.41. Фактор для shallow_water2, n = 81 920, nz = 2 183 332
Мал. 7.42. Фактор для parabolic_fem, n = 525 825, nz = 26 494 693
Мал. 7.43. Фактор для pwtk, n = 217 918, nz = 66 843 598
Мал. 7.44. Фактор для cfd2, n = 123 440, nz = 156 075 674

Експерименти показують, що метод вкладених перетинів в цілому дає приблизно такі ж коефіцієнти заповнення, що і метод мінімальному обсязі. Значної відмінності є тільки для матриці cfd2, яке пояснюється її особливою структурою - елементи матриці розташовані близько до головної діагоналі (см. Портрет матриці на Мал. 7.24 ), Тому перестановка не дає таких значних (у порівнянні з іншими прикладами) результатів.