Transpusa matricei rare

Matricea rară este reprezentată prin 3 vectori ce conțin informații doar despre elementele sale nenule. A calcula transpusa unei matrice rare înseamnă a interschimba conținutul vectorilor pentru linii cu cel pentru coloane. Subprogramul este:

          SUBROUTINE TRARAR(LIN,ICOL,K, IK)

          INTEGER AUX

          IK=0

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

          K1=0

          DO 10  I=1,K

          AUX=ICOL(I)

          ICOL(I)=LIN(I)

          LIN(I)= AUX                   

          LIN1(K1)=LIN(I)

          ICOL(K1)=ICOL(I)

          VAL1(K1)=VAL1(I)

10      CONTINUE

          IK=1

20      CONTINUE

          RETURN

          END

Variabila AUX de tip întreg ajută la efectuarea interschimbului. Aici nu este necesar apelul subprogramului de efectuare a interschimbului elementelor unui vector pentru că s-ar efectua un apel inutil de subprogram, ori așa, am încorporat secvența pur și simplu că nu este  lungă și este simplă.

(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)

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)

Verificarea simetriei unei matrice

Subprogramul care verică dacă matricea A cu N linii și N coloane este simetrică are forma:

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

         DO 10 J=1,N

         IF(A(I,J).NE.A(I,J)) 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)

Coeficienții ecuației de regresie simplă

Modelul de regresie simplă

pentru calculul coeficienților a și b se folosesc formulele 

subprogramele de calcul pentru coeficienții a și b sunt următoarele:

SUMVEC - sumă elemente ale unui vector S=X(1)+X(2)+....+X(N);

PATRAT - ridicare la pătrat a elementelor unui vector Z(I)=X(I)*X(I);

PRODEL - calcul produse elemente ale unui vector Z(I)=X(I)*Y(I);

COEF - calculează coeficineții A și B după formulele de mai sus.

         SUBROUTINE SUMVEC(X,N,S)

         S=0.

         DO   10  I=1,N

         S=S+X(I)

10     CONTINUE

         RETURN

         END

         SUBROUTINE PATRAT(X,N,S2)

         S2=0.

         DO   10  I=1,N

         S2=S2+X(I)*X(I)

10     CONTINUE

         RETURN

         END

         SUBROUTINE PRODEL(X,Y,Z,N)

         DO   10  I=1,N

         Z(I)=X(I)*Y(I)

10     CONTINUE

         RETURN

         END

         SUBROUTINE COEF(X,Y,N,A,B,IK)

         IK=0

         IF(N.LE.0) GO TO 10

         AN=N

         IK=1

         CALL PRODEL(X,Y,XY,N)

         CALL  SUMVEC(X,N,SX)

         CALL  SUMVEC(XY,N,SXY)

         CALL  SUMVEC(Y,N,SY)

         CALL  PATRAT(X,XN,SXX)

         A=(AN*SXY-SX*SY)/(AN*SXX-SX*SX)

         B=(SY-A*SX)/AN

10     CONTINUE

         RETURN

         END

Variabila IK este 0 dacă nu se calculează coeficienții că seriile de date sunt vide și IK=1 dacă acești coeficienți se calculează. Subprogramul COEF() se optimizează și dacă se elimină puzderia de apeluri de subprograme, dar devine mai mărișor și cu instrucțiuni ceva mai regrupate după cum urmează:

         SUBROUTINE COEF(X,Y,N,A,B,IK)

         IK=0

         IF(N.LE.0) GO TO 20

         AN=N

         IK=1

         SX=0.

         SY=0.

         SXX=0.

         SXY=0.

         DO   10  I=1,N

         SX=SX+X(I)

         SY=SY+Y(I)

         SXX=SXX+X(I)*X(I)

         SXY=SXY+X(I)*Y(I)

10     CONTINUE

         A=(AN*SXY-SX*SY)/(AN*SXX-SX*SX)

         B=(SY-A*SX)/AN

20     CONTINUE

         RETURN

         END

Dacă subprogramul ar fi scris în limbajul C++ cu siguranță că inițializările s-ar fi scris SX=SY=SXX=SXY=0.; ceea ce ar fi fost cu mult mai drăguț. Coeficienții ecuației de regresie simplă se calculează fie apelând tot felul de alte subprograme simple, fie scriind un subprogram ce include toate calculele. Trebuie ales un echilibru între a apela subprograme și a avea redundanță în program prin nereutilizare de componente de bibliotecă. Programatorul e suveran în programul pe care-l scrie și el alege dacă vrea să fie genial sau penibil, riscuș fiind în ambele cazuri 50% și 50%.

(29 decembrie 2017)

Alegerea identificatorilor

În limbajul FORTRAN IV căci cu el se scriau programe până în 1977 numele de variabile care se construiau trebuiau să respecte următoarele reguuli:

- lungimea numelui de variabilă era maxim de 6 caractere;

- caracterele utilizate sunt literele mari A-Z, cifrele 0-9 și semnul $;

- primul caracter al numelui de variabilă este obligatoriu o literă.

Astfel, construcțiile:

VALOARE

COST

PROFIT

CERC

G981

$VAR

SUMA3

sunt nume de variabile corecte.

Construcțiile:

1RAZA   nu este corectă că are prim caracter altceva decât o literă;

RAZA+  nu este corectă că are simbolul + care nu este nici literă și nici cifră;

PR_PL    nu este corectă pentru că are în interior caracterul underscore cod HTML &#95;;

A1234567B nu este corectă pentru că are mai mult de 6 caractere în componență.

Chiar dacă erau restricții așa de severe, programatorii de talent știau să aleagă astfel de denumiri ale variabilelor astfel încât să asigure un nivel de ortogonalitate pentru a nu le confunda unele cu altele. Se făceau o serie de convenții precum:

- variabila I era folosită pentru traversarea elementelor unui șir sau a liniilor matricei;

- variabila J era folosită pentru traversarea elementelor de pe coloanele unei matrice;

- variabila TEMP era folosită pentru rezultate temporare, ca și variabila AUX;

- variabilele M și N erau utilizate pentru a stabili număr de elemente sau de linii sau coloane;

- variabila XMED era folosită pentru media aritmetică;

- variabila DISP era folosită pentru dispersie;

- postfixul SORT era folosit pentru a marca faptul că rezultatul este sortat XSORT, YSORT;

- prefixul STOC era folosit pentru stocuri STOCPL, STOCRE, STOCEF;

- postfixul PL era utilizat pentru planificat, RE pentru realizat și EF pentru efectiv.

Fiecare programator își construia propriile reguli de a defini nume de variabile, dar ideia era ca programul să fie cât mai lizibil și el ca programator să nu depună eforturi inutile nici la depanare și nici la mentenanță, ci să meargă la sigur, având reguli pe care și le-a definit și le-a și respectat. 

Programatorii care au lucrat foarte ermtic, definind nume de variabile după niște reguli foarte codificate au avut mari probleme în a depana programele, căci este foarte dificil să se umble într-o secvență care pleacă de la o relație matematică de forma:

să fie recunoscută cu lejeritate în construcția:

S234=S65*S987*S987

în loc de a scrie:

SCERC=PI*R*R

Este rezonabil mai ales când se construiesc subprograme să se utilizeze modalități omogene de definire a numelor de variabile EPS pentru acel epsilon care controlează precizia, ITER pentru numărul de iterații și pentru variabila de stare IK sau ISTARE sau pentru codul de eroare IERR și toți programatorii vor folosi fără retitență bibliotecile de subprograme, altfel le vor evita că sunt greoaie. Alegerea identificatorilor intră în arta programatorilor și adevărații programatori au și reguli de a construi nume de variabile care săă facă programele livibile și ușor de manevrat, fără ca expresiile să fie groaznic de sofusticate. În FORTRAN IV nu există cuvinte cheie și programatorii ar avea la dispoziție să folosească DO, IF, READ, GO TO RETURN ca nume de variabile. M-am jucat și eu cândva cu acestă facilitate și noroc că a fost doar o joacă pentru că un program cu astfel de variabile este o calamitate la depanare, căci există riscul de a distruge din prea mult zel chiar instrucțiuni corect scrise.

(28 decembrie 2017)

Activarea și dezactivarea de termeni

În informatică nu este rezonabil să fie șterse nivi articole din fișiere și nici termeni ai seriilor de date. Ceea ce ar trebui șters, trebuie dezactivat. În acest sens se asociază fiecărui element din șir un alt element care are valoarea 0 dacă este considerat neactiv sau șters din punct de vedere logic și nu fizic. La fișiere în articol se definește un câmp de un byte care este 0 dacă articolul este neactiv sau șters logic și 1 dacă este activ. Prin testarea acelui câmp, dacă are valoarea 1 se for face prelucrări, iar sacă este zero nu va fi utilizat nici articolul și nici elementul din șir.

Subprogramul care însumează elementele active ale șirului X de N componente va avea un subprogram care mai primește ca parametru un vector LL tot de N componente și LL(I) =0 ceea  ce înseamnă că elementul nu este activ, este șters logic și nu intră în calcule, iar dacă LL(I)=1 elementul X(I) este activ și se folosește în prelucrări.

             SUBROUTINE SUMVEC (X,LL,N,SUM)

             SUM=0.

             DO  10 I=1,N

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

             SUM=SUM+X(I)

10         CONTINUE

             RETURN

             END

Activând și dezactivând termeni se construiesc tot felul de eșantioane și se verifică tot felul de ipoteze. Prin operații simple se procedează la reconstituirea de toturi de date fără a fi nevoie să se refacă nici seriile de date și nici fișiere. Acum în prelucrările moderne se lucrează în mod curent cu vectori sau câmpuri de stare fără a mai se proceda șa ștergeri de elemente sau la ștergeri de articole.

(28 decembrie 2017)

Suma elementelor unei matrice

Dacă se dă o matrice A cu m linii și n coloane, pentru adunarea elementelor sale se folosește schema logică:

Programul scris în limbajul FORTRAN IV pentru a calcula această sumă este:

         SUBROUTINE ADMAT (A,M,N,SUMAT)
         SUMAT=0.
         DO 10 I=1,M

         DO 10 J=1,N
10     SUM=SUM+A(I,J)

         RETURN
         END

Limbajul FORTRAN a fost agreat de programatori pentru simplitatea și concizia lui. Numai limbajul C++ îl depășește și acest lucru se datorează extensisi listei de operanzi și a mecanismelor cu care se definește o mare varietate de tipuri de referire și de evaluare a operanzilor.

(23 decembrie 2017)

Vectorizarea masivelor multidimensionale

Vectorizarea matricelorm este o terminologie cam vrutală prin care s=a căutat o mai bună utilizare a memoriei interne a unui calculator în vremurile de demult când memoria atât internă, cât și memoria externă era o mare problemă. Un calculator IBM 360 considerat de top  prin  august 1969 avea memorie de 4096 Kb și de aici trebuie pornită orice discuție legată de dimensiunea oricărei probleme de rezolvat cu calculatorul. Un sistem de ecuații de maximum 30variabile  și  30 ecuații însemna definirea unei matrice  

DIMENSION A(30,30) 

în FORTRAN ocupa 30 * 30 * 4 bytes adică 3,515 Kb. La un program de adunare a două matrice, fiecare având 100 linii și 100 de coloane se vor defini în programul FORTRAN 

DOUBLE PRECISION A(100,100), B9100, 100), C(100,100)

necesarul de memorie va fi de 234,375 adică aproximativ 235 Kb, adică 23% din disponibilul de memorie al calculatorului. Calculele se fac riguros și destul de exact, dar tot în acea memorie de 1024 Kb trebuie să încapă pe lângă date și programul rezultat după editarea de legături în forma executabilă. Deci în niciun caz nu va fi vorba de dezmățul de memorie care este acum când un calculator modest are memorie RAM de 4 Gb echivalentul a 16.384 de calculatoare IBM 360 din 1969. 

Această situație a impus vectorizarea, adică un procedeu de a face economie de memorie.

În vremurile de dinainte de 1980 despre alocarea de memorie se știa clar că este numai statică. Limbajul ALGOL 67 amintea ceva de blocuri, de alocare și de dealocare dar nu am avut cunoștință de implementări complete ale limbajului acesta. 

În condițiile implementării limbajelor FORTRAN și COBOL era mare deosebire între conceptele de:

- memorie alocată, adică modul cum au fost definite variabilele în program;

- memorie utilizată, adică tot ce se inițializa și se folosea sub controlul instrucțiunilor executabile.

Într-un program FORTRAN se definea un masiv tridimensional

DIMENSION X(20,10,30) 

și se inițializau constantele N cu 10, M cu 15 și H cu 7.

În secvența:

     DO 30 I=1, N

     DO 30 J=1, M

     DO 30 I=K, 7

30 X(I,J,K) = I + K * J

este inițializată numai o parte din masivul tridimensional, ceea ce înseamnă că restul de memorie este nefolosit. Se falculează  gradul de ocupare G = N*M*K / (20*10*30) În cazul concret G = 0,175 adică nu nivel foarte mic.

Dacă se lucrează cu masi.ve având mai multe dimensiuni pentru a calcula exact poziția unui element în masiv formulele arată că trebuie date niște constante. La masivul bidimensional este necesar să se știe cât a fost alocat numărul de coloane ca valoare numerică. Dacă se lucrează cu masive unidimensionale această restricție dispare și lumea preferă să lucreze cu masive unidimensionale. Vectorizarea, acest termen care nu prea există în limba română și preluat brutal din engleză, înseamnă a pune în corespondentă elementele unui masiv bidimensional cu elementele unui masiv unidimensional și a lucra cu masivul unidimensional efectuând tot felul de operații ca și cum s-ar lucra cu masivul bidimensional.

Dacă se consideră un masiv bidimensional

DIMENSION A(10,10)

se inițializează N=5, M=5, se inițializează cumva numai primele 5 linii și primele 5 coloane pentru a calcula suma elementelor de pe diagonala principală se scrie secvența:

     S=0     

     DO 30 I=1, N*M

30 S = S + X(I + (M-1))

Avem bgijă ca să scriem o secvență de vectorizare de forma:

DIMENSION A(10,10), X(100)

...............

      K=1

      DO 30 I=1, N

      DO 30 J=1, M

      X(K) = A(I,J)

30  K=K+1

Discuțiile legate de avantajele vectorizării sunt lungi și avantajele din acele vremuri făceau diferența la apelul de subprograme unde parametrii formali arătau cu mult mai bine decât în cazul în care se scriau masive multidimensionale însoțite de niște constante care dădeau amri bătăi de cap programatorilor care doreau să facă metenanță atunci când cu lucrau cu constante simbolice definite undeva la începutul programului principal în blocuri COMMON sau de folosirea lui EQUIVALENCE.

DIMENSION X(100), B(10,10)

EQUIVALENCE (B(1),X(1))

Pune în corespondență X(10 cu B(1,1), X(2) cu B(2,1)....X(100) cu B(10,10). Se ține seama de regula după care se face linearizarea. Sunt limbaje unde linearizarea se face coloană de coloană, iar altele linearizarea se face linie de linie. Aici am presupus linearizarea coloană după coloană.

Rste o vectorizare la nivel de zone de memorie alocate static, lucru diferit de vectorizarea aceea care ține seama numai de ceea ce s-a inițialozat.

(25 noiembrie 2017)