Matricele rare

Și în vremurile de demult se lucra cu probleme de mari dimensiuni, concretizate prin matrice cu grad de umplere redus, adică, matrice rare. Gradul de umplere al matricei A, G(A), este dat de formula:

G(A) = (K * 100) / (M*N)

unde:

K - numărul elementelor nenule din matricea A;

M - numărul de linii ale matricei A;

N - numărul de coloane ale matricei A.

O matrice A se zice că este rară dacă și numai dacă G(A) < 0,33%. Și în vremurile de demult lucrul cu matrice rare presupunea existența unei biblioteci de subprograme ce conținea subprograme privind:

- inițializarea matricei rare cu date provenind din cartele perforate;

- transformarea matricei definite full în matrice rară;

NORAR() - normalizarea de matrice rare;

- adunarea cu normalizare de matrice rare;

- scăderea cu normalizare de matrice rare;

- înmulțirea cu normalizare de matrice rare;

- inversarea cu normalizare a matricei rare;

- calcului transpusei unei matrice rare;

- comoararea de matrice rare.

Algoritmii care se implementau în acele vremuri țineau seama dacă se lucra sau nu cu matrice rare pentru că disponibilul de memorie internă era o mare problemă atunci. Se făceau calcule la sânge cum s-ar zice cu operanzii ca să se obțină rezolvări de probleme cu dimensiuni cât mai mari.

O matrice rară se memorează folosind 3 vectori, fiecare având câte NM componente și anume:

LIN(NM) -  memorează liniile elementelor nenule;

ICOL(NM) - memorează coloanele elementelor nenule;

VAL(NM) - memorează valorile nenule din matricea A.

Se consideră că acest mod de memorare a unei matrice rare este eficient pentru o matrice A de tip double cu M linii și N coloane dacă și numai dacă 8 * M * N < 4 * 2 * K + 8 * K, unde K este numărul elementelor nenule din matricea A. Vectorii LIN() și ICOL() sunt definiți de tip INTEGER și fiecare componentă a lor are 4 bytes, iar vectorul VAL() are componente de câte 8 bytes fiecare pentru faptul că matricea A este definită ca având tipul DOUBLE.

(05 ianuarie 2018)