Normalizarea de matricei rare

Normalizarea de matrice rare este un subprogram extrem de inportant care musai trebuie apelat înainte de a ieșii din orice subprogram care lucrează cu două matrice rare sau inversează o matrice rară. După efectuarea unor astfel de calcule este posibil ca în matricea rezultat să apară valori nule acolo în vectorul VAL(N). Se va elimina din tripletele de vectori linia și coloana unde VAL(J) este cu valoarea zero. Vor rezulta alți trei vectori LIN(N), ICOL(N) și VAL(N) cu un număr K1 de componente K1 < K unde K este numărul de componente ale matricei rare freprezentată prin 3 vectori înainte de normalizare și K1 reprezintă numărul de componente după ce s-a făcut normalizarea.

Se consideră matricele rare A și B definite prin:

Matricele A și B au fiecare câte 10 linii și 8 coloane. Se construiesc tripletele următoare pentru matricea A:

(1, 2, 1), (1, 7,4), (2,4, 4), (2, 8,7), (3, 5, -1), (4, 1, 9), (5, 1, 3), (5,2,2), (5, 8,5), (7, 2, 8), (7, 4, 6),    (7, 5, 7), (9, 6,12), (10,2,31), (10,8,87).

Se construiesc tripletele următoare pentru matricea A:

(1, 2, 1), (1, 7,4), (2,4, 4), (2, 8,7), (3, 5, -1), (4, 1, 9), (5, 1, -3), (5,2,2), (5, 8,5), (7, 2, 8), (7, 4, 6),    (7, 5, 7), (9, 6,-12), (10,2,31), (10,8,-87).

Dacă se adună cele două matrice rare se obțin tripletele matricei rezultat următoare:

(1, 2, 1), (1, 7,4), (2,4, 4), (2, 8,7), (3, 5, 0), (4, 1, 9), (5, 1, -3), (5,2,2), (5, 8,5), (7, 2, 8), (7, 4, 6),   

(7, 5, 7), (9, 6,0), (10,2,31), (10,8, 0).

Prin normalizare tripletele bolduite vor dispărea căci ele conțin valori zero ale elementelor matricei rezultat. Lista de triplete LIN1, ICOL1, VAL1 devine:

(1, 2, 1), (1, 7,4), (2,4, 4), (2, 8,7), (4, 1, 9), (5, 1, -3), (5,2,2), (5, 8,5), (7, 2, 8), (7, 4, 6),    (7, 5, 7), (10,2,31).

Subprogramul pentru normalizarea matricei rare este:

          SUBROUTINE NORAR(LIN,ICOL,N,K, LIN1,ICOL1,K1,IK)

          IK=0

          IF((K.LE.0).OR.(K.GT.N)) GO TO 20

          K1=0

          DO 10  I=1,K

          IF(VAL(I).EQ.0.) GO TO 10

          K1=K1+1

          LIN1(K1)=LIN(I)

          ICOL(K1)=ICOL(I)

          VAL1(K1)=VAL1(I)

10      CONTINUE

          IK=1

20      CONTINUE

          RETURN

          END

Variabila IK este zero dacă sunt erori în datele inițiale. Ea este 1 dacă rezultatul este corect, inclusiv dacă rezultă o matrice rară cu toate elementele nule.

   

(05 ianuarie 2018)

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)

Gemerarea unui termen din șirul FIBONACCI

Gemerarea unui termen din șirul FIBONACCI presupune scrierea unui subprogram care calculează totți termenii care preced termenul ce tyrebuie căutat și returnează valoarea termenului cerut. Formula de calcul a termenului Fn din șirul FIBONACCI este Fn =  Fn-1 + Fn-2. Subprogramul este:

         SUBROUTINE ELEFIB(N,ISIRK,IK)

         IK=0

         IF((N.GT.46).OR.(N.LE.2)) GO TO 20

         ISIRI1=0

         ISIRI2=1

         DO  10 I=3,N

         ISIRK=ISIRI1 + ISIRI2

         ISIRI1=ISIRK

         ISIRI2=ISIRI1

10     CONTINUE

         IK=1

         RETURN

         END

Subprogramul returnează IK egal cu zero dacă termenul cerut este eronat, respectiv IK=1 dacă rezultatul returnat este corect. Variabila ISIRK va arăta care este valoarea termenul din șirul FIBONACCI care a fost cerut să fie generat.

(04 ianuarie 2018)

Generarea elementelor șirului FIBONACCI

Generarea elementelor șirului FIBONACCI se realizează după formulele:
F0 = 0
F1 = 1
F2 = F0 + F1
...
Fn = Fn-1 +Fn-2

 A genera n+1  termen ai șirului FIBONACCI înseamnă a calcula termenii 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,... , Fn-1 +Fn-2.
Știind că F46= 1.836.311.903  și cel mai mare număr întreg memorat pe 4 bytes este 2.147.483.647 iar F47 = 2.971.215.073 vectorul cu termeni generați nu trebuie să depășească 47 de termeni, subprogramul generează cel mult  termenii F0,  F1,  F2,  F3,  ....F46,  din șirul FIBONACCI, pentru N mai mare decât 2 și mai mic decât 47..
Subprogramul este:

         SUBROUTINE FIBON(N,ISIR,IK)

         IK=0

         IF((N.GT.46).OR.(N.LE.2)) GO TO 20

         ISIR(1)=0

         ISIR(2)=1

         DO  10 I=3,N

         ISIR(I)=ISIR(I-1) + ISIR(I-2)

10     CONTINUE

         IK=1

         RETURN

         END

Subprogramul returneză șirul de termeni generat și variabila de stare IK egală cu 1 dacă șirul a fost generat, respectiv, IK egal cu zero dacă numărul de termeni este incorect.

(04 ianuarie 2018)

Interschimb de variabile

Interschimbul de variabile este echivalentul cu interschimbul conținutului a două borcane A și B, borcanul A care conține ulei și celălalt, borcanul B, care conține apă. În final trebuie ca borcanul B să conțină ulei și borcanul A să conțină apă. Evident este nevoie de un al treilea vas temporar, TEMP care va prelua conținutul borcanului A. O dată golit borcanul A, în el va fi vîrsat borcanul B. Vasul temporar va fi vărsat în borcanul B golit deja de apă.

         SUBROUTINE SCHIMB(A,B)

         TEMP=A

         A=B

         B=TEMP

         RETURN

         END

Aceeași operație se realizează și pentru vectorii X și Y de câte N componente, obținând subprogramul:

         SUBROUTINE SCHVEC(X,Y,N)

         DO  10 I=1,N

         TEMP=A(I)

         A(I)=B(I)

         B(I)=TEMP

10     CONTINUE

         RETURN

         END

Pentru interschimbul elementelor din două matrice A și B fiecare având N linii și M coloane se va scrie subprogramul:

         SUBROUTINE SCHMAT(A,B,M,N)

         MAXAIJ=A(1,1)

         DO  10 I=1,N

         DO  10 J=1,N

         TEMP=A(I,J)

         A(I,J)=B(I,J)

         B(I,J)=TEMP

10     CONTINUE

         RETURN

         END

Aici se vede cum se obține generalizarea de la interschimb de elemente, la interschimb de vectori și apoi la interschimb de matrice, continuarea fiind aceeași pentru masivele multidimensionale.

(04 ianuarie 2017)

Ridicarea la putere a matricei

A ridica o matrice pătrată A cu N linii și N coloane la puterea K înseamnă a o înmulți cu ea însăși de K-1 ori. Rezultatul se află în matricea REZ. Este nevoie de:
- un subprogram CPYMAT de copiere de matrice;
- un subprogram PROMAT de înmulțire de matrice;
- subprogramul PUTERE de ridicare la putere matrice.

         SUBROUTINE PROMAT (A,B,C,M,N,K)
         DO 20 I=1,M

         DO 20 J=1,K

         CIJ=0.

         DO 10 L=1,N
10     CIJ=CIJ+A(I,L)*B(L,J)

         C(I,J)=CIJ

20     CONTINUE

         RETURN
         END

         SUBROUTINE CPYMAT(A,B,M,N)

         MAXAIJ=A(1,1)

         DO  10 I=1,M

         DO  10 J=1,N

         B(I,J)=A(I,J)

10     CONTINUE

         RETURN

         END

         SUBROUTINE PUTERE(A,N,REZ)

         DIMENSION TEMP(N,N) 

         CALL  CPYMAT(A,TEMP,N,N)

         DO  10 J=1,N-1

         CALL  PROMAT (A,TEMP,REZ,N,N,N)

         CALL  CPYMAT(TEMP,REZ,N,N)

10     CONTINUE

         RETURN

         END

Subprogramul PUTERE(....) are în el așa cum este scris niște asperități, dintre carea cea mai supărătoare este copierea de matrice de la ultima iterație care este nenecesară, dar care se gestionează cu o instrucțiune IF(...) dar a cărei execuție nu aduce un profit așa de mare decât numai dacă volumul de operații generat de dimensiunea matricei A este cu mult mai mare, lucru care se stabilește cu exactitate, dar care nu mi se pare a fi esențial pentru ceea ce mă interesează pe mine ca exemplificare.

(04 ianuarie 2018)

Verificarea matricelor pozitiv definite

O matrice este pozitiv definită dacă toate elementele sale sunt mai mari strict decât zero. Subprogramul care verifică dacă matricea A cu M linii și N coloane este pozitiv definită este:

         SUBROUTINE POZIT (A,N,N, IK)
         IK=0
         DO 10 I=1,M

         DO 10 J=1,N

         IF(A(I,J).LE.0) GO TO 20
10     CONTINUE

         IK=1

20     CONTINUE

         RETURN
         END

Variabila IK are valoarea zero dacă matricea nu este simetrică și are valoarea 1 dacă matricea este simetrică.

(04 ianuarie 2018)