НОУ ІНТУЇТ | лекція | Множення розріджених матриць

1. Методи рішення систем з розрідженій матрицею В даному розділі будуть розглянуті питання, що стосуються...
2. Базові алгоритми обробки розріджених матриць
3. Множення матриці на вектор
4. транспонування матриці
5. матричне множення
6. Метод Холецкого для розріджених матриць
7. Метод мінімальному обсязі

Методи рішення систем з розрідженій матрицею

В даному розділі будуть розглянуті питання, що стосуються вирішення СЛАР з розрідженими матрицями. У попередніх розділах неявно малося на увазі, що ми працюємо з щільними матрицями.

Поняття розрідженій матриці можна визначити багатьма способами, суть яких полягає в тому, що в розрідженій матриці "багато" нульових елементів. Зазвичай кажуть, що матриця розріджена, якщо вона містить відмінних від нуля елементів. В іншому випадку матриця вважається щільною. Типовим випадком розрідженості є обмеженість числа ненульових елементів в одному рядку від 1 до k, де . Завдання лінійної алгебри з розрідженими матрицями виникають у багатьох областях, наприклад, при вирішенні диференціальних рівнянь в приватних похідних, при вирішенні багатомірних задач локальної оптимізації. У п. 7.3 ми вже познайомилися з методами розв'язування СЛАР з трехдіагональной матрицею, яка, будучи стрічкової, відноситься також і до класу розріджених матриць.

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

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

Зберігання розрідженій матриці

Існують різні формати зберігання розріджених матриць. Одні призначені для зберігання матриць спеціального виду (наприклад, стрічкових), інші забезпечують роботу з матрицями загального вигляду. Нижче розглянемо деякі вельми поширені способи подання розріджених матриць, інформацію про інші способи можна знайти, наприклад, в [10].

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

• масив ненульових елементів матриці A (позначимо його як values);
• масив номерів рядків матриці A, що відповідають елементам масиву values ​​(позначимо його як rows);
• масив номерів стовпців матриці A, що відповідають елементам масиву values ​​(позначимо його як cols);

Даний спосіб представлення називають повним, оскільки представлена ​​вся матриця А, і неврегульованим, оскільки елементи матриці можуть зберігатися в довільному порядку.

Як приклад розглянемо розріджену матрицю

яка може бути представлена ​​в координатному форматі як

values ​​= (1, -1, -3, -2, 5, 4, 6, 4, -4, 2, 7, 8, -5);

rows = (1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5);

cols = (1, 2, 4, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5).

Хоча багато математичні бібліотеки підтримують матрично-векторні операції в координатному форматі, даний формат забезпечує повільний доступ до елементів матриці, і є витратним по використовуваної пам'яті. У розглянутому вище прикладі надмірність по пам'яті чином проявляється в масиві rows, в якому малі координати зберігаються неоптимальним чином.

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

Відповідно до даної схемою для зберігання матриці A потрібно три одновимірних масиву:

• масив ненульових елементів матриці A, в якому вони перераховані по рядках від першої до останньої (позначимо його знову як values);
• масив номерів стовпців для відповідних елементів масиву values ​​(позначимо його як cols);
• масив покажчиків позицій, з яких починається опис чергового рядка (позначимо його pointer). Опис k-го рядка зберігається в позиціях з pointer [k] -й по (pointer [k + 1] -1) -у масивів values ​​і cols. Якщо pointer [k] = pointer [k + 1], то k-й рядок порожня. Якщо матриця A складається з n рядків, то довжина масиву pointer буде n + 1.

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

Для прикладу розглянемо уявлення матриці (7.40) в розрідженому строчном форматі:

values ​​= (1, -1, -3, -2, 5, 4, 6, 4, -4, 2, 7, 8, -5);

cols = (1, 2, 4, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5);

pointer = (1, 4, 6, 9, 12, 14).

Очевидно, що обсяг пам'яті, необхідний для зберігання вектора pointer, значно менше, ніж для зберігання вектора rows. Більш того, розріджене рядковий формат забезпечує ефективний доступ до рядків матриці; доступ до стовпців і раніше ускладнений. Тому переважно використовувати цей спосіб зберігання в тих алгоритмах, в яких переважають малі операції.

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

Після розгляду сатиричного формату зберігання очевидним є і розріджене столбцовую формат. В цьому випадку ненульові елементи матриці A перераховуються в порядку їх появи в шпальтах матриці, а не в рядках. Все ненульові елементи зберігаються за стовпцями в масиві values; індекси рядків ненульових елементів - в масиві rows; елементи масиву pointer вказують на позиції, з яких починається опис чергового стовпчика.

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

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

може бути представлена ​​в розрідженому строчном форматі як

values ​​= (1, -1, -3, 5, 4, 6, 4, 7, -5);

cols = (1, 2, 4, 2, 3, 4, 5, 4, 5);

pointer = (1, 4, 5, 8, 9, 10).

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

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

Базові алгоритми обробки розріджених матриць

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

Множення матриці на вектор

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

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

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

також розміщується в одновимірному масиві.

Нехай n - число рядків матриці. Порядок, в якому накопичуються скалярні твори, визначається порядком зберігання елементів матриці. Для кожної її рядки i ми знаходимо за допомогою масиву індексів pointer значення першої pointer [i] і останньої pointer [i + 1] -1 позицій, займаних елементами рядка i в масивах values ​​і cols. Потім, щоб обчислити скалярний добуток рядка i та вектора b, ми просто переглядаємо values ​​і cols на відрізку від pointer [i] до pointer [i + 1] -1; кожне значення, збережене в cols [pointer [j]], є столбцовую індекс і використовується для вилучення з масиву b елемента, який повинен бути помножений на відповідне число з масиву values. Результат кожного множення додається до c [i].

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

Як правило, кількість елементів в одному рядку розрідженій матриці розміру обмежена деякою константою k, . Значить, в процесі множення такої матриці на вектор кількість обчислювальних операцій для отримання скалярного твори приблизно однаково для всіх базових подзадач. При використанні систем зі спільною пам'яттю число потоків p буде менше числа базових подзадач n, і ми можемо об'єднати базові підзадачі таким чином, щоб кожен потік виконував кілька таких завдань, відповідних безперервній послідовності рядків матриці А. У цьому випадку після закінчення обчислень кожна базова подзадача визначає набір елементів результуючого вектора с. Розподіл подзадач між потоками може бути виконано довільним чином.

транспонування матриці

Розглянемо задачу транспонування розрідженій матриці A. Формально матриця може бути визначена як

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

Будемо формувати результуючу матрицю по рядках. Для цього можна брати стовпці вихідної матриці і створювати з них рядки результуючої матриці. Але операція виділення з CRS-матриці стовпця №i є трудомісткою, тому що дані в векторі values ​​зберігаються по рядках і для вибірки даних по стовпчику потрібно переглянути всю матрицю, що призводить до квадратичної (від числа ненульових елементів) трудомісткості алгоритму. Необхідно інше рішення. Детально проблема транспонування розрідженій матриці обговорюється в книзі [10], тут же розглянемо основні ідеї описаного в [10] алгоритму.

1. Сформуємо N одновимірних векторів для зберігання цілих чисел (IntVectors), а також N векторів для зберігання дійсних чисел (RealVectors). N в даному випадку відповідає числу стовпців початкової матриці.
2. У циклі переглянемо всі рядки вихідної матриці, для кожного рядка - всі її елементи. Нехай поточний елемент знаходиться в рядку i, стовпці j, його значення дорівнює v. Тоді додамо числа i і v в j-ті вектора для зберігання цілих і дійсних чисел (відповідно). Тим самим в векторах ми сформуємо рядки транспонованою матриці.
3. Послідовно скопіюємо дані з векторів в CRS структуру транспонованою матриці (сols і values), попутно формуючи масив pointer.

Розглянемо приклад (7.17).

При обході вихідної матриці A формуються вектора IntVectors і RealVectors (число 3 розташоване в рядку 0 і стовпці 1, отже, в IntVectors [1] додається 0, в RealVectors [1] додається 3 і т.д.). Далі вектора послідовно формують структуру : Зверніть увагу на порядок проходження елементів в масиві values ​​матриці і його відповідність порядку елементів в масиві RealVectors (аналогічно cols і IntVectors). Для формування pointer досить підрахувати кількість елементів в кожному з N векторів. pointer [0] завжди дорівнює нулю, pointer [i] = pointer [i-1] + "Кількість елементів у векторі i-1".

Таким чином, алгоритм транспонирует матрицю за лінійний час, що значно краще вихідного тривіального алгоритму. Недоліком же алгоритму в тому вигляді, як він викладений, є використання додаткової пам'яті. У книзі [10] наводиться опис алгоритму, позбавленого цього недоліку. Основна ідея полягає в використанні структур даних матриці для проміжних результатів обчислень.

Мал.7.17.

Транспонування розрідженій матриці

матричне множення

Приступимо до обговорення алгоритмів множення розріджених матриць. Перш за все розглянемо алгоритм множення безпосередньо за визначенням.

Мал.7.18.

множення матриць

Визначення передбачає, що елемент в рядку i і стовпці j матриці C обчислюється як скалярний твір i-го рядка матриці A і j-го стовпця матриці B. Які особливості вносить розріджений уявлення?

По-перше, використовувана структура даних, побудована на основі формату CRS, передбачає зберігання тільки ненульових елементів, що ускладнює програмування обчислення скалярного твори, але одночасно зменшує кількість арифметичних операцій. При обчисленні скалярних творів немає необхідності множити нулі і накопичувати отриманий нуль в часткову суму, що позитивно впливає на скорочення часу рахунку. Нехай, наприклад, в першому і другому векторах знаходиться по 1% ненульових елементів, при цьому тільки десята частина цих елементів розташована на відповідних один одному позиціях. У цьому випадку розрахунок з використанням інформації про структуру векторів може використовувати в 1000 разів менше число множень і додавань. З огляду на, що таких пар векторів , Виходить істотне скорочення обсягу обчислень. На жаль, не все так просто. Облік структури векторів теж вимагає машинного часу. Необхідно виконати зіставлення номерів ненульових елементів з метою виявлення пар значень, які необхідно перемножити і накопичити в часткову суму.

По-друге, необхідно навчитися виділяти вектора в матрицях A і B. Відповідно до визначення, мова йде про рядках матриці A і шпальтах матриці B. Виділити рядок матриці в форматі CRS не становить труднощів: i-й рядок може бути легко знайдена, так як посилання на перший елемент poiner [i] і останній елемент (pointer [i + 1] -1) відомі, що дозволяє отримати доступ до значень елементів і номерами стовпців, що зберігаються в масивах values ​​і cols відповідно. Таким чином, прохід по рядку виконується за час, пропорційне числу ненульових елементів у зазначеному рядку, а прохід по всіх рядках - за час, пропорційне NZ, де NZ - кількість ненульових елементів в матриці.

Проблема виникає з виділенням стовпчика. Щоб знайти елементи стовпця j необхідно переглянути масив cols ( операцій) і виділити всі елементи, у яких у відповідній клітинці масиву cols записано число j. Якщо це потрібно виконати для кожного стовпця, необхідно операцій, що є неефективним.

Можливе, але не єдине вирішення проблеми полягає в транспонировании матриці B: після обчислення з'явиться можливість ефективно працювати зі стовпцями вихідної матриці B, а сам алгоритм транспонування працює досить швидко. Інший варіант - для кожної CRSматріци, яка може знадобитися в столбцовую поданні, додатково зберігати транспонований портрет. Заощадивши час на транспонировании, доведеться змиритися з витратами часу на підтримку додаткового портрета в актуальному стані. Є й інші варіанти вирішення проблеми, ніяк не пов'язані з Транспонированием матриці B (див., Наприклад, ефективний алгоритм Густавсона [11]). Надалі ми будемо використовувати підхід, заснований на транспонировании матриці B.

Як і Третє, та патенти, навчітіся запісуваті пораховані елементи в матриці C. З Огляду на, что C зберігається в форматі CRS, важліво избежать перепаковок. Для цього нужно Забезпечити поповнення матриці C ненульовімі елементами послідовно, по рядках - зліва направо, зверху вниз. Це означає, що часто використовується в обчисленнях на папері метод "візьмемо перший стовпець матриці B, запишемо його над матрицею A і перемножимо на всі рядки ..." не підходить. Потрібно робити навпаки - брати перший рядок матриці A і множити її по черзі на всі стовпці матриці B (рядки матриці ). У цьому випадку забезпечується послідовне поповнення матриці С, що дозволяє дописувати елементи в масиви values ​​і cols, а також формувати масив pointer.

Таким чином, для виконання матричного множення розріджених матриць необхідно зробити наступне:

1. Реалізувати транспонування розрідженій матриці і застосувати його до матриці B.
2. Ініціалізувати структуру даних для матриці C, забезпечити можливість її поповнення елементами.
3. Послідовно перемножити кожен рядок матриці A на кожну з рядків матриці , Записуючи в C отримані результати і формуючи її структуру.

Ще один непростий момент: в процесі обчислення скалярного твори на папері (в точної арифметики) може вийти нуль, причому не тільки в тому випадку, коли при зіставленні векторів відповідних один одному пар не виявилося, але і просто як природний результат. У арифметиці з плаваючою точкою нуль може вийти ще й у зв'язку з обмеженнями на подання чисел і похибкою обчислень (див. Стандарт IEEE-754). Нулі, отримані в процесі обчислень, можна як зберігати в матриці C (у векторі values ​​у відповідній позиції), так і не зберігати; обидва підходи мають право на існування.

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

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

Зауважимо, що кожен множити вектор є рядком матриці і впорядкований відповідно до обраної структурою зберігання матриці. Це означає, що для зіставлення компонент може бути застосований алгоритм, вельми схожий на злиття двох відсортованих масивів в один із збереженням упорядкування. Алгоритм виглядає наступним чином:

1. Встати на початок обох векторів
2. Порівняти поточні елементи . Якщо значення збігаються, накопичити в суму твір A.Value [ks] * B.Value [ls] і збільшити обидва індекси, в іншому випадку - збільшити один з індексів, в залежності від того, яке значення більше (наприклад, ).

Крок 2 виконується до тих пір, поки не закінчаться елементи хоча б в одному з векторів.

Даний алгоритм має лінійну трудомісткість, але він не дуже добре відповідає архітектурі комп'ютера, тому що містить дуже багато розгалужень. Існують більш ефективні схеми: наприклад, в книзі [10] пропонується наступний алгоритм обчислення скалярного твори розріджених векторів.

1. Створимо додатковий цілочисельний масив X довжини N. ініціалізувавши його числом -1. Обнулив речову змінну S.
2. Переглянемо всі ненульові елементи першого вектора . Нехай такий елемент з порядковим номером i розташований в стовпці з номером . В цьому випадку запишемо i в j-ю осередок масиву X.
3. Переглянемо в циклі всі ненульові елементи другого вектора . Нехай елемент з порядковим номером k розташований в стовпці з номером . перевіримо значення . Якщо воно дорівнює -1, в першому векторі немає відповідного елемента, тобто множення виконувати не потрібно. інакше множимо і накопичуємо суму в S.

Даний алгоритм також має лінійну (щодо числа ненульових елементів у векторі) трудомісткість, і не містить надлишкових розгалужень.

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

Метод Холецкого для розріджених матриць

У п. 7.2 було розглянуто метод Холецкого для вирішення системи лінійних рівнянь із симетричною позитивно певної матрицею

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

Як приклад розглянемо систему рівнянь

Використовуючи розрахункові формули методу (7.13) і (7.14), можна обчислити фактор Холецкого для даного завдання

а потім, виконавши зворотний хід алгоритму за формулами (7.15), (7.16), знайти шукане рішення

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

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

Очевидно, що ця перенумерація змінних і переупорядочение рівнянь рівносильні симетричною перестановці рядків і стовпців матриці A, причому та ж перестановка застосовується і до вектора b. Рішення нової системи є переупорядочение вектор x. Вказану перенумерацию легко записати у вигляді твору сволока A на матрицю перестановки P. Нагадаємо, що матриця P називається матрицею перестановки, якщо в кожному рядку і стовпці матриці знаходиться лише один одиничний елемент. У нашому прикладі

а матрицю системи (7.43) можна отримати як

При цьому зв'язок з вихідною постановкою завдання виражається співвідношенням

Нижче наведено фактор Холецкого для нової системи рівнянь (з точністю до )

Виконавши зворотний хід, можна отримати переупорядочение вектор рішення

Важливий момент полягає в тому, що переупорядочение рівнянь і змінних призвело до трикутного множнику L, який розріджене в точності в тій мірі, що і нижній трикутник А.

Завдання знаходження перестановки, що мінімізує заповнення при обчисленні фактора Холецкого, є NPтрудной (тому що взагалі кажучи, мінімум повинен обчислюватися по всіх n! Перестановок). Тому на практиці використовують евристичні алгоритми, які хоча і не гарантують, що знаходять оптимальну перестановку, але, як правило, дають прийнятний результат.

Таким чином, при вирішенні розрідженій системи методом Холецкого можна виділити наступні етапи:

1. Перегрупування - обчислення матриці перестановки P;
2. Символічне розкладання - побудова портрета матриці L і виділення пам'яті під зберігання ненульових елементів;
3. Чисельне розкладання - обчислення значень матриці L і розміщення їх в виділеної пам'яті.
4. Зворотний хід - рішення двох трикутних систем рівнянь.

Етапи 1 і 2 специфічні саме для розріджених матриць, тоді як етапи 3 і 4 виконуються для будь-яких завдань.

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

Метод мінімальному обсязі

Для формулювання методу мінімальному ступені нам будуть потрібні деякі відомості з теорії графів.

Розглянемо неорієнтований граф G. Формально граф G можна розглядати як впорядковану пару двох множин

де - безліч вершин, -безліч зв'язків між вершинами (ребер). Так як розглянутий граф - неорієнтований, то безліч E задовольняє властивості

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

Для будь-якої вершини можна визначити безліч суміжних їй вершин як

потужність безлічі називається ступенем вершини

Граф, кожні дві вершини якого з'єднані ребром, називається повним.

Подграф вихідного графа - граф, що містить якесь підмножина вершин даного графа і якесь підмножина інцидентних їм ребер.

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

Однією з форм завдання графа є матриця суміжності розміру така, що

У нашому випадку матрицю A системи лінійних рівнянь (7.41) можна розглянути як матрицю суміжності відповідного графа G (A), за винятком діагональних елементів, яким будуть відповідати петлі. на Мал. 7.19 наведено граф, відповідний матриці з прикладу (7.42).

Мал.7.19.

Приклад графа матриці

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

Нехай вихідній матриці A з (7.41) відповідає граф G (A). Алгоритм мінімальному ступені будує послідовність графів виключення , Кожен з яких отримано з попереднього видаленням вершини з мінімальним ступенем і створенням кліки між усіма вершинами, які були суміжними з віддаленої. У разі, коли вершин з мінімальним ступенем кілька, вибирається будь-яка. Алгоритм триває до тих пір, поки в черговому графі є вершини. У міру віддалення вершин, їх номер записується в перестановку , По якій згодом будується матриця перестановки P.

Як приклад роботи алгоритму на Мал. 7.20 приведена послідовність графів виключення і відповідна перестановка , Породжувана алгоритмом мінімальному обсязі для завдання (7.42).

Послідовність графів виключення

отримана перестановка = {2,3,4,1,5} відповідає матриці

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

Фактор Холецкого, відповідний цій матриці, буде (з точністю до )

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