Yousef saad (tradus de engleza de dyachenko t

Metode iterative pentru sistemele rare de ecuații liniare: Scheme de stocare, Operații de bază pe matrice rare

Straturile de stocare cu matrice redusă

Scopul principal este de a stoca numai elemente non-zero printr-o matrice și capacitatea de a efectua operații simple de matrice peste ea.

Fie Nz numărul de elemente non-zero ale lui A. Luați în considerare cele mai comune scheme de stocare, pentru mai multe detalii, consultați [4].

Schema cea mai simplă pentru stocarea matricelor rare este formatul așa-numit "coordonate". Structura matricei originale este mapată la trei tablouri unidimensionale: (1) - o matrice care conține valorile elementelor non-zero ale matricei A în ordine arbitrară; (2) o matrice integer care conține indicii lor de șir; și (3) o matrice întregă care conține indicii lor de coloană. Toți cei trei vectori au lungimea Nz.

Exemplul 1. Matricea

Poate fi reprezentat ca:

În exemplul de mai sus, elementele sunt listate în ordine aleatorie, dar ele sunt de obicei listate după rânduri sau coloane. Dacă elementele sunt enumerate în rânduri, vectorul JC, care conține informații redundante, poate fi înlocuit cu un șir de indicii de la începutul fiecărei linii. Acest lucru va da economii remarcabile în stocare. Noua structură de date va avea trei rețele care vor efectua următoarele funcții:

- matricea AA conține valori non-zero aij, stocate pe linie, de la rândul 1 la n. Lungimea matricei AA este Nz.

- matricea JA cuprinde indicii de coloane ale elementelor aij în matricea A. Lungimea matricei JA este Nz.

Astfel, matricea A de mai sus poate fi stocată ca:

Un astfel de format este cel mai popular pentru stocarea unor matrice rare de un tip general. Se numește formatul de linie redusă sau Rândul redus comprimat (CSR). Acest sistem este mai preferabilă decât o coordonată, așa cum este adesea mai convenabil pentru mai multe ope¬ratsy importante de matrici rare: plus, multiplicare, permutări de coloane și rânduri, transpunere, soluții de sisteme liniare cu matrici rare coeficient atât metode directe si iterative. Pe de altă parte, diagrama unui simplu ca format, lucid și flexibil, este folosit de multe ori „de intrare“ pentru bibliotecile de calcul destinate să lucreze cu matrici rare de coordonate.

Există mai multe modificări la această schemă de stocare, cea mai evidentă fiind reprezentată de schema de coloane necorespunzătoare sau de coloana compresivă (CSC).

O altă schemă comună ia în considerare faptul că elementele diagonale ale celor mai multe matrici sunt nenuloase și / sau sunt folosite mai des decât altele. Modificat Sparse Row (MSR) utilizează doar două matrici: o matrice de AA și o matrice JA întreg. În primele n poziții, AA conține în ordine elementele diagonale ale matricei originale. Elementul AA (n + 1) nu este completat (sau conține informații suplimentare despre matrice). Pornind de la poziția n + 2, elementele non-zero ale matricei originale sunt scrise în rânduri, cu excepția diagonalelor. Pentru fiecare element AA (k), elementul JA (k) arată indicele coloanei din matricea originală. La pozițiile n + 1 ale matricei JA, se plasează indicatorii de intrare pentru fiecare rând din matricea AA și JA.

Prin urmare, pentru matricea din exemplul de mai sus, aceste două matrice vor avea forma:

Un asterisc indică un element neutilizat. Rețineți că JA (n) = JA (n + 1) = 14, indicând faptul că ultima linie este zero, deoarece elementul diagonal este deja descris mai devreme.

Matricile structurate diagonal sunt matrice ale căror elemente nonzero sunt situate de-a lungul unui număr mic de diagonale. Aceste diagonale pot fi stocate într-o matrice dreptunghiulară DIAG (1: n, 1: Nd), unde Nd este numărul de diagonale. Deplasarea fiecărei diagonale este calculată în raport cu diagonala principală, care trebuie cunoscută. Compensările sunt stocate în matricea IOFF (1: Nd). Astfel, elementul ai, i + ioff (j) al matricei originale va fi stocat în poziția (i, j) în matricea DIAG. Ordinea în care sunt stocate diagonală, în general, nu este important, mai ales în cazul în care majoritatea operațiilor concentrate în jurul diagonalei principale, are sens pentru a stoca în prima coloană. De asemenea, trebuie remarcat faptul că toate diagonalele, cu excepția diagonalei principale, au mai puțin de n elemente, astfel încât nu vor fi utilizate toate elementele matricei DIAG.

Exemplul 2. O matrice tridiagonală

pot fi stocate în două rețele în conformitate cu schema de mai sus:
DIAG =

O schemă mai generală, populară pentru mașinile vectoriale, este așa-numitul format. Această schemă presupune că numărul de diagonale Nd este mic. Două matrice rectangulare de mărime n * Nd sunt necesare pentru stocare.

În primul rând, coef, astfel DIAG, stocate elemente nenule ale matricei A. Elementele nenule ale fiecărui rând pot fi stocate într-un rând al coef matrice (1: n, 1: Nd), completând linia de zero, dacă este necesar. Împreună cu COEF, matricea JCOEF întreagă (1: n, 1: Nd) trebuie să stocheze indicele de coloană al fiecărui element COEF.

Pentru matricea A a exemplului 2, schema de stocare Ellpack-Itpack ia forma:
COEF =

Operații de bază pentru matrici rare

Multiplicarea unei matrici de către un vector este o operație importantă care este necesară în majoritatea algoritmilor iterativi pentru rezolvarea unor sisteme lineare rare. Această secțiune arată cum poate fi implementată pentru schemele de stocare listate mai devreme.

Următorul exempl de cod de pe Fortran 90 prezintă ciclul principal de multiplicare a vectorilor matrici pentru matrici stocați într-un format de coloană redusă:

Rețineți că fiecare repetare a buclăi calculează diferitele componente ale vectorului rezultat. Acest lucru este avantajos, deoarece fiecare dintre aceste componente poate fi calculat independent. Evident, dacă matricea este stocată în coloane, trebuie folosit următorul cod:

În fiecare iterație a buclei, produsul din coloana jth este adăugat la rezultat, care se presupune că este inițial zero. Rețineți, de asemenea, că bucla exterioară nu mai este potrivită pentru paralelizare. Ca paralelizare alternativă, puteți încerca să împărțiți operația vectorului în bucla interioară. Bucla internă are doar câteva operații, deci este puțin probabil ca aceasta să aibă o îmbunătățire semnificativă a performanței. Această comparație arată că pot fi necesare modificări ale structurilor de date pentru a îmbunătăți performanța atunci când lucrați cu calculatoare puternice. Să analizăm acum matricile matrice-vectori pentru matricile stocate într-un format diagonal.

Aici, fiecare diagonală este înmulțită cu vectorul x. iar rezultatul este adăugat la vectorul y. Din nou, se presupune că vectorul y este umplut cu zerouri la începutul ciclului. Din punctul de vedere al paralelizării și / sau vectorizării, este mai bine să utilizați codul de mai sus, probabil. Pe de altă parte, nu este destul de generală.

Soluția sistemului triunghiular inferior sau superior este un alt "nucleu" important în calculul matricelor rare. Următorul fragment de cod prezintă blocul convențional pentru rezolvarea sistemului triunghiular inferior Lx = y pentru formatul de stocare CSR.

În fiecare etapă, rezultatul multiplicării actuale a lui x de rândul i este calculat și scăzut din y (i). Aceasta dă valoarea lui x (i). Funcția Dotproduct calculează produsul scalar al a doi vectori arbitrari U (k1: k2) și V (k1: k2). Vector AL (k1: k2) este rândul i-lea al matricei L într-un format rar, și X (JAL (k1: k2)) este un vector X component colectat într-un vector scurt, ceea ce corespunde indicilor de coloane ale elementelor în linie AL (k1: k2).

Articole similare

• Traduceri de traducere din engleză în rusă, traducere engleză în rusă

• Drugstore traducere din rusă în engleză, traducere rusă în engleză

• Veniți traducerea în engleză, exemple, transcriere, pronunție

Trimiteți-le prietenilor: