Metode de Programare cu Matrice Rare

Introducere

Lucrarea cuprinde metode tradiţionale de calcul matriceal care sunt utilizate frecvent în practică, metode reanalizate şi revăzute prin optica matricelor rare în vederea adaptării lor la rezolvarea problemelor de mari dimensiuni.

Sunt prezentate metodele şi caracteristicile esenţiale ale celor mai utilizate tehnici de calcul cu matrice rare privind memorarea, efectuarea calculelor numai cu elemente nenule, reducerea numărului de operaţii, creşterea preciziei de calcul şi a stabilităţii numerice, menţinerea structurii de matrice rară, precum şi eficienţa utilizării acestora din punct de vedere al cerinţelor de memorie şi timp de calcul. De asemenea, sunt prezentate şi aplicaţii ale tehnicilor de calcul cu matrice rare în rezolvarea optimală a sistemelor complexe.

Lucrarea este structurată în cinci capitole, în fiecare dintre acestea fiind prezentate cele mai bune metode de calcul cu matrice rare şi comparaţii ale rezultatelor cu rezultatele metodelor de calcul cu matrice dense.

În capitolul I „Metode de programare cu matrice rare” sunt prezentate noţiuni introductive despre matricele rare si metode de memorare a acestora în formă compactă. Metodele de memorare a matricelor rare sunt utilizate frecvent deoarece matricele rare de mari dimensiuni pot fi memorate şi manevrate doar astfel în memoria centrală a calculatorului si se micşorează timpul de calcul prin evitarea efectuării operaţiilor cu elemente nenule. Sunt prezentate metode care memorează numai elementele nenule şi poziţiile pe care se află acestea în matrice, salvând astfel memorie şi timp.

În capitolul II „Factorizarea matricelor rare” sunt expuse cele mai eficiente metode de factorizare a unei matrice rare, de exprimare a acesteia sub formă de factori matriceali, în vederea calculului matricei inverse. Acestea includ factorizarea LU, bifactorizarea unei matrice şi o comparaţie între acestea. Metoda de factorizare în calculul inversei unei matrice rare necesită un număr de n3/3 operaţii elementare faţă de n3 în cadrul metodelor directe.

În capitolul III „Rezolvarea sistemelor de ecuaţii algebrice liniare cu matricea coeficienţilor rară”, sunt prezentate metode directe şi indirecte de rezolvare a sistemelor de dimensiuni mari, strategii de pivotare şi scalare în vederea menţinerii structurii de matrice rară şi a stabilităţii numerice, precum şi comparaţii între aceste metode.

În capitolul IV „Programarea liniară utilizând metode de calcul cu matrice rare”, sunt prezentate câteva din cele mai eficiente metode de rezolvare a problemelor de programare liniară cu scopul de a arăta cum tehnicile de calcul cu matrice rare pot fi incluse în rezolvarea lor.

În capitolul V „Sisteme fizice şi matrice rare” evidentiaza prezenţa matricelor rare în modelele matematice ale sistemelor fizice complexe de mari dimensiuni. Prezenţa matricelor rare în modelele matematice ale sistemelor fizice este remarcată în analiza reţelelor electrice a sistemelor de distribuţie a puterii şi în analiza reţelelor fluidice.

Anexa cuprinde programele C asociate acestor metode de calcul cu matrice rare.

CAPITOLUL I

METODE DE PROGRAMARE CU MATRICE RARE

1.1 Noţiuni fundamentale despre matrice rare

În general, o matrice n × n este rară dacă conţine un număr mic de elemente nenule, τ, adică τ << n2. O matrice este rară (engl. ″sparse″) în sensul că raportul dintre numărul de elemente nenule şi cel de elemente nule este foarte mic. Cantitativ matricele rare sunt caracterizate de raportul dintre numărul elementelor nenule şi al celor nule, d = τ / (n2 – τ), numit densitatea matricei.

Definiţia 1. O matrice pătrată n × n este rară dacă odată cu creşterea lui n creşterea numărului de elemente nenule τ este inferioară uneia pătratice, adică τ < n1+k, 0 ≤ k <1.

Elementele nule ale unei matrice rare sunt calasificate în zerouri numerice şi zerouri topologice. Toate zerourile topologice sunt şi zerouri numerice. Unele zerouri numerice sunt tratate ca elemente nenule, acestea fiind considerate topologic nenule.

O matrice nesingulară A se poate exprima sub formă de produs de factori matriceali L şi U, unde L este inferior triunghiulară, iar U este superior triunghiulară, cu elementele diagonalei principale egale cu unitatea.

Definiţia 2. O matrice nesingulară A este matrice de eliminare perfectă dacă tuturor elementelor nule din A le corespund elemente nule în factorii matriceali L şi U.

Modelele matematice ale sistemelor fizice complexe de mari dimensiuni adeseori conţin matrice rare. Sistemele de ecuaţii care descriu comportarea acestora pot fi rezolvate în mod direct, prin inversarea explicită a matricei coeficienţilor. Deşi aceste metode sunt uşor de programat, totuşi ele nu exploatează structura rară a matricelor şi pentru probleme de mari dimensiumi sunt total ineficiente. În consecinţă, aceste metode sunt potrivite pentru probleme de dimensiuni relativ mici (n < 100) şi a căror matrice a coeficienţilor este densă.

Metodele directe de inversare a matricelor bazate pe tehnici de factorizare pot lua în consideraţie structura de matrice rară prin utilizarea unor metode de ordonare în vederea minimizării numărului de elemente nenule nou create în procesul de factorizare, deci a menţinerii structurii de matrice rară şi memorarea şi manevrarea numai a elementelor nenule. Deoarece numai elementele nenule ale matricei originale şi ale factorilor matriceali sunt memoraţi, este evident că trebuie să se dispună de metode speciale privind memorarea matricelor rare în formă compactă. Memorarea în formă compactă este convenabilă deoarece:

- matricele rare de mari dimensiuni pot fi memorate şi manevrate în memoria centralăa calculatorului,

- chiar dacă în formă compactă cerinţa de memorie depăşeşte capacitatea memoriei centrale, utilizarea memoriei externe este încă eficientă prin minimizarea tipurilor de acces,

- se micşorează timpul de calcul prin evitarea efectuării de operaţii cu elemente nule, aceasta realizându-se prin factorizarea simbolică care generează numai operaţiile netrivialre,

- matricea A-1 memorată ca produs de matrice elementare de obicei necesită mai puţină memorie decât reprezentarea compactă a lui A-1 explicită.

1.2 Memorarea unui vector

Înainte de a trata tehnicile de memorare a elementelor nenule ale unei matrice rare în formă compactă, se vor discuta aspecte generale implicate în memorarea şi identificarea unui vector în formă compactă, precum şi probleme privind modificarea acestei memorări când noi elemente vor fi adăugate pentru memorare. Această problemă necesită definirea unei zone în care se memorează elementele nenule ale vectorului, zona primară, şi altei zone cu informaţii necesare regăsirii rapide a acestora, zona secundară.

Tehnicile de memorare a unui vector sunt ilustrate pe vectorul (31,6; 52,9; 25,4; 47,3). Acest vector este memorat într-o zonă denumită VAL, în aceiaşi ordine ca mai sus:

Locaţia 1 2 3 4 …

VAL 31,6 52,9 25,4 47,3 …

Deseori în descrierea algoritmilor în care sunt implicaţi vectori este necesară adăugarea sau ştergerea unor elemente. Dacă operaţia de adăugare sau şteregere are loc numai la sfârşitul vectorului, atunci vectorul este numit stivă. În vederea manipulării stivei este necesară numai o variabilă, IVÂRF, care indică vârful stivei. O altă formă specială de vector este coada, aceasta fiind un vector unde elementele se pot adăuga numai la sfârşit şi înlăturarea de la început. Pentru a putea lucra cu o coadă sunt necesare numai două indicatoare, IFAŢA şi ISPATE