Методи упаковування розріджених матриць і векторів

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

(4.192)

подається за допомогою векторів , де - вектори адрес компонентів вектора НЕ відповідно по рядкам і стовпцям матриці. Упакований запис матриці за допомогою векторів називають списковою формою запису, а самі вектори – списками.

При наведеному кодуванні кількість компонентів запису матриці , де - кількість НЕ матриці. Для запису топологічні матриць, що є бінарними матрицями (містять НЕ у вигляді бінарні цифр +1 чи -1), у прямому кодуванні , оскільки можна вказати знаки бінарних цифр при компонентах одного з векторів адреси. Наприклад, коли в (4.192) НЕ бінарні, задані вектором то, вказуючи знаки його компонентів (монад) при адресах, припустімо, рядка, вичерпну інформацію про таку матрицю можна подати за допомогою двох векторів

У методі прямого кодування пошук НЕ за його адресами вимагає значних витрат часу, оскільки тут у загальному випадку треба оглянути всі компоненти векторів та . Це й є основним недоліком методу

Найкомпактнішим методом кодування вимірної матриці є метод нумерації, в якому кожному НЕ за певним законом присвоюється номер, наприклад, порядковий номер по рядках

(4.193)

де номер рядка матриці; номер її стовпця.

Матриця кодується двома векторами: вимірним вектором компонентами якого є наскрізні порядкові номери НЕ по рядках матриці, і вектором значень НЕ . Для матриці (4.192)

Адреси НЕ (номери їхніх рядків і стовпців) визначаються як

(4.194)

Отже, тут кількість компонентів запису

Для бінарної матриці НЕ записуються одним вектором , при компонентах якого вказуються знаки від'ємних ненульових монад. Наприклад, для бінарної матриці зі структурою (4.192) при вона записується вектором

Метод нумерації такий же трудомісткий за пошуком інформації, як і метод прямого кодування. Тут для пошуку НЕ необхідно переглянути всі компоненти вектора починаючи від його початку і до місця розташування шуканого НЕ.

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

Для матриці (4.192) маємо

У випадку бінарної матриці вона може бути подана тільки векторами та із записом від'ємних знаків бінарних НЕ при компонентах вектора . Наприклад, для бінарної матриці, структура якої збігається з (4.192) при упакована інформація подається векторами

Кількість НЕ в му рядку матриці тут визначається як

(4.195)

де відповідно й і й компонент вектора . Кількість компонентів запису НЕ в матриці становить для бінарних матриць

Метод кодування зі зміщенням економічний і відзначається високою швидкістю пошуку НЕ. Його недолік - значна трудомісткість зміни структури матриці (наприклад, її транспонування), що пов'язане з необхідністю кодування строго по рядках і стовпцях. Зрештою, цей недолік характерний практично для всіх методів кодування.

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

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

Розглянемо застосування викладеного алгоритму для наведеного вище прикладу. У лічильник записуємо одиницю У перший елемент вектора переписуємо значення лічильника Переглядаємо по рядках вектор та ведемо пошук елементів першого стовпця. У першому рядку знаходимо . В запишемо (номер рядка зі знаком знайденого елемента). Значення лічильника збільшуємо на одиницю У другому рядку знаходимо . В запишемо (номер рядка). Значення лічильника збільшуємо на одиницю Формування першого рядка закінчили. В запишемо значення лічильника Ведемо пошук елементів другого стовпця. У другому рядку знаходимо . В запишемо (номер рядка зі знаком знайденого елемента). Значення лічильника збільшуємо на одиницю У третьому рядку знаходимо . В запишемо (номер рядка зі знаком знайденого елемента). Значення лічильника знову збільшуємо на одиницю Формування другого стовпця закінчено. В запишемо значення лічильника

Аналогічно формуємо елементи третього і четвертого стовпців. Нарешті, в записуємо значення лічильника В результаті отримуємо вектори

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

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

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

Припустимо, що матриця

(4.196)

кодується векторами

Далі припустимо, що в матриці (4.196) у процесі її перетворення з'явилися ННЕ і які необхідно записати у наведеній списковій формі. Алгоритм перетворення можна реалізувати таким чином, що ННЕ будуть з'являтися поступово у рядках. Всі ННЕ будемо записувати в продовження вектора а відповідний номер стовпця в продовження вектора . Перше вільне місце вказує останній елемент вектора Введемо допоміжний вектор Значення останнього елемента перепишемо в перший елемент вектора Оскільки в першому рядку матриці ННЕ ніколи не будуть появлятися, то в другий елемент вектора , можна також записати це значення. При появі ННЕ його значення запишемо в 11-й елемент вектора , а в 11-й елемент вектора запишемо 4 (номер стовпця ННЕ). У третій і четвертий елементи вектора запишемо число 12 (номери вільного місця у векторах і При появі ННЕ його значення запишемо в 12-й елемент вектора а номер стовпця (2) - у 12-й елемент вектора .У п'ятий елемент вектора запишемо число 13.

Таким чином, перекодована матриця (4.196) у зв'язку з появою двох ННЕ та подається тепер за допомогою таких значень векторів:

Упакування матриці доцільне тільки тоді, коли кількість компонентів запису , менша від загальної кількості елементів (у тому числі нульових) матриці, тобто коли Для оцінки ефективності упакування користуються коефіцієнтом економії пам'яті ЦОМ

(4.197)

Подані вище методи запису розріджених бінарних матриць можна з успіхом застосувати для упаковування топологічних матриць, зокрема матриць інциденцій. Для цієї ж мети дуже зручним є використання понять топологічні множини, викладені у другому розділі. Наприклад, запис матриці сполучень найекономічніший у вигляді множини суміжностей (2.83), який подається -вимірним (по числу віток кола) вектором. Це означає, що такий вектор має всього компонентів (запис матриці ). Однак цей запис значно ускладнює алгоритми, що працюють с такими векторами. Найдоцільніше використовувати вершинні множини (2.81), які хоч і задаються -вимірним вектором, але забезпечують економні алгоритми його обробки. Подібним чином може бути задана друга матриця інциденцій у вигляді контурних множин (2.84). Легко переконатися, що таке упакування фактично відповідає кодуванню бінарних матриць зі зміщенням чи з нумерацією.

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

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

Наприклад, матриця сполучень (скорочена).

може бути подана таблицею (спискова матриця )

або векторами та Порядок номерів ребер відповідає порядкові їх запису в матриці (тут - натуральний).

Як видно, наведений спосіб упакування матриці фактично відповідає прямому кодуванню.

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

маємо). Список, що відповідає векторові звичайно називають списком розділювачів.

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

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

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

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

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

Рис. 4.13

ребра 1 до ребра 2). Наступні обходи дають хорди 5 і 6. Очевидно, для наведеного графа можна побудувати різні дерева залежно від базової вершини та шляхів обходу графа.

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

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

Легко зміркувати, що у першому випадку цей мінімум дуже слабо виражений і задовольняється фактично будь-яким деревом з такою базовою вершиною, в якій збігається найбільша кількість ребер. Наприклад, для графа рис. 4.13, а оптимальне будь-яке дерево з базовою вершиною 1, 2 чи 3. Неважко також дійти висновку, що оптимальним з погляду методу контурних струмів деревом є дерево, яке забезпечує систему незалежних контурів, що охоплюють мінімальну кількість ребер. З цього погляду дерево, вибране на рис. 4.13, а, не оптимальне - один із незалежних контурів, наприклад 7, 2, З, 4, має надмірну кількість ребер. Оптимальним є дерево на рис. 4.13, б.

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

Рис. 4.14

графа рис. 4.14, а в сукупності з хордою (3, 7) такими є ребра (11, 8), (10, 9), (2, 1), (5, 4), (5, 6). Це добре видно з відповідних складових векторів з фіксованими хордою 4 і з вершинами 3 та 7 по тому, які номери вершин виступають лише раз. Це вершини (11, 10, 6, 4, 2). Отже, на першому етапі вилучаються ребра дерева (1, 8, 2, 7, 13). після чого одержуємо зредукований граф рис. 4.14, б. Аналогічно на другому етапі формуємо граф, показаний на рис. 4.14, в, на третьому - уже сам контур (рис. 4.14, г).

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

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

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

Date: 2015-09-25; view: 579; Нарушение авторских прав