Matrice Rare

Matricele rare îşi găsesc aplicabilitatea în modelarea unor procese de natură industrială, economică, tehnică, socială, etc.

Modelele matematice ale proceselor reale implică un număr foarte mare de variabile şi restricţii care prezintă fenomenul de raritate (sparsity), adică de slabă interconectare a elementelor sale. Luarea în consideraţie a fenomenului de raritate furnizează un nou mod de abordare foarte eficient, ce implică în dezvoltarea aplicaţiilor informatice folosirea unor structuri de date speciale, care să conducă la reducerea resurselor de memorie şi a timpului de calcul.

În general, o matrice - dimensională este rară dacă conţine un număr mic de elemente nenule , adică . Cantitativ, matricele rare sunt caracterizate de ponderea numărului de elemente nenule în totalul de elemente, pondere ce defineşte gradul de umplere al matricei. În aplicaţiile curente se întâlnesc matrice rare cu grade de umplere între 0,15% şi 3%.

O matrice este considerata rara atunci cand folosind o alta modalitate de memorare a elementelor se obtine un grad de utilizare superior memorarii element cu element.

Matricea:

este o matrice rara pentru ca:

- daca este memorata element cu element, fiecare element ocupa K baiti;

- daca are M linii si N coloane, lungimea zonei de memorie LM necesara este LM=K*M*N baiti.

Pentru cazul dat: K=2, M=8, N=10, LM=2*8*10=160 baiti.

Se defineşte gradul de umplere (densitatea) unei matrice prin raportul dintre numărul elementelor nenule şi numărul total al elementelor sale:

unde: p – numărul de elemente nenule;

n – numărul de linii;

m – numărul de coloane.

Se acceptă, în general, că o matrice este rară dacă densitatea sa este de cel mult 3%.

Se observa ca matricea contine multe elemente nule. Se pune problema memorarii numai a elementelor nenule.

Se definesc 3 vectori:

lin[] - pentru memorarea pozitiilor liniilor unde se afla elementele nenule;

col[] - pentru memorarea pozitiilor coloanelor unde se afla elementele nenule;

val[] - pentru memorarea valorilor elementelor nenule.

Adunarea matricelor rare presupune parcurgerea câtorva paşi:

- determinarea numărului de elemente nenule ale matricei sumă;

- alocarea memoriei corespunzătoare acestui număr;

- determinarea acelor elemente din prima matrice care nu au corespondent în cea de-a doua şi adăugarea lor la matricea sumă;

- determinarea elementelor din cea de-a doua matrice care nu au corespondent în prima şi adăugarea lor la matricea sumă;

- determinarea elementelor comune celor două matrice, însumarea lor şi adăugarea la matricea sumă.

Prin “elemente comune” au fost desemnate acele elemente caracterizate prin indicii de linie şi de coloană care sunt nenule în ambele matrice.

Pentru înmulţirea matricei rare A, (m, 1) – dimensională, cu matricea rară B, (l, n) – dimensională, se utilizează o modificare a procedurii standard, considerând influenţa liniilor matricei A asupra matricei produs C, (m,n) – dimensională, prin coloanele matricei B. Procedura standard de înmulţire se modifică astfel încât în bucla internă să se execute toate operaţiile corespunzătoare unui element al matricei A. Întrucât elementul aik al matricei A poate contribui la formarea tuturor elementelor liniei i a matricei C, se determină mai întâi această contribuţie după care se continuă cu următorul element al liniei i a matricei A, până la determinarea completă a liniei i a matricei C.

1. Reprezentare prin vectori

Se definesc trei vectori:

- un vector care memoreaza liniile pe care se afla elementele nenule;

- un vector care memoreaza coloanele pe care se afla elementele nenule;

- un vector care memoreaza valoarea elementelor nenule.

Procedura care initializeaza de la tastatura o matrice rara contine:

- secventa de initializare;

- secventa de citire a liniei pe care se afla elementul nenul;

- secventa de citire a coloanei pe care se afla elementul nenul;

- secventa de introducere a elemntului nenul - mecanismul de incheiere a procesului de introducere elemente nenule;

- procedura returneaza numarul elementelor nenule din matrice;

- se presupune ca dimensiunea matricei este cunoscuta si nu are legatura cu aceasta procedura.

Cei trei vectori au un grad de incarcare dat de faptul ca intre K si numarul maxim de elemente nenule care se memoreaza efectiv exista diferente.