Matricea rară

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
O matrice rară obținută prin aproximarea unei funcții în două dimensiuni cu metoda elementului finit . Valorile diferite de zero sunt reprezentate în negru.

În matematică , în special în analiza numerică , o matrice rară este o matrice ale cărei valori sunt aproape toate egale cu zero.

Conceptual, raritatea se referă la sistemele cuplate. Luați în considerare o serie de bile în care fiecare dintre ele este conectată la următoarea prin intermediul arcurilor; acesta este un sistem împrăștiat. În schimb, dacă aceleași bile ar fi fost conectate între ele, sistemul ar fi fost reprezentat de o matrice densă . Conceptul de raritate este util în combinatorică și în acele domenii de aplicare, cum ar fi teoria rețelelor , unde există o densitate redusă de date sau relații semnificative.

Matricele rare de o anumită complexitate apar adesea în unele discipline științifice sau inginerești atunci când este necesar să se rezolve ecuații diferențiale parțiale .

Atunci când matricele rare sunt stocate și gestionate pe un computer , este profitabil și adesea o necesitate să se utilizeze algoritmi specializați și structuri de date care să ia în considerare natura rară a matricei. Efectuarea operațiilor folosind structurile și algoritmii obișnuiți ai matricei este o operațiune foarte lentă și, de asemenea, duce la pierderi mari de memorie, dacă matricea care trebuie gestionată este rară. Datele rare sunt, prin însăși natura sa, ușor de comprimat , iar comprimarea are ca rezultat aproape întotdeauna o utilizare semnificativ mai mică a memoriei . Cu toate acestea, este adevărat că unele matrici rare foarte mari sunt imposibil de gestionat cu algoritmi standard.

Depozitarea unei matrici rare

Structura clasică de date a unui tablou este cea a unui tablou bidimensional. Fiecare element al tabloului reprezintă elementul generic a i , j , care poate fi accesat prin intermediul celor doi indici i și j . Pentru o matrice m × n , trebuie să fie disponibilă cel puțin cantitatea minimă de memorie necesară pentru a stoca valorile ( m × n ) ale matricei.

Multe, dacă nu toate, valorile unei matrici rare sunt zero. Principiul de bază care este urmat pentru stocarea unei matrici rare este salvarea, în locul tuturor valorilor, numai a celor altele decât zero. În funcție de numărul și distribuția valorilor diferite de zero, pot fi utilizate diferite structuri de date și pot fi realizate economii considerabile de memorie care sunt imposibile cu abordarea obișnuită.

Un exemplu de format pentru stocarea matricelor rare este formatul (vechi) Yale Sparse Matrix Format, care stochează o matrice rară m × n , M , într-un rând folosind trei matrice unidimensionale. Fie NNZ numărul de valori diferite de zero ale lui M. Prima matrice este A , cu lungimea NNZ , și stochează toate valorile diferite de zero ale lui M , sortate de la stânga la dreapta și de sus în jos. A doua matrice este IA , care are o lungime de m + 1 (adică o valoare pe rând, plus una). IA(i) conține indicele primului element diferit de zero din A din al i rând. Lungimea liniei i este determinată de IA(i+1) - IA(i) , din acest motiv IA trebuie să fie de lungime . A treia matrice, JA , conține indexul coloanei fiecărui element al lui A, deci JA este lung NNZ .

De exemplu, matricea

 [1 2 0 0]
[0 3 9 0]
[0 1 4 0]

este o matrice de trei pe patru cu șase elemente diferite de zero, deci

 A = [1 2 3 9 1 4]
IA = [1 3 5 7]
JA = [1 2 2 3 2 3]

O altă posibilitate este de a utiliza quadrees .

Exemplu

O imagine bitmap în două tonuri, în care una dintre cele două culori este predominantă (gândiți-vă la un fișier care stochează o semnătură scrisă de mână) poate fi codificată ca o matrice rară care conține doar numerele de rânduri și coloane ale pixelilor cu culoarea nu dominantă.

Matrici diagonale

O foarte eficientă matrice diagonală structură implică stocarea doar valorile diagonalei principale ca unidimensional matrice, astfel încât o n × n matrice diagonală necesită doar n valori.

Grup

Banda inferioară a unei matrice A este cel mai mic număr p astfel încât valoarea a ij este neglijabilă atunci când i > j + p. În mod similar, banda superioară este cea mai mică p astfel încât a ij = 0 când i < j - p (Golu, Van Loan, 1996 §1.2.1). De exemplu, o matrice tridiagonală are o bandă inferioară și o bandă superioară egală cu 1.

Tablourile cu o bandă mică inferioară și superioară sunt cunoscute sub numele de matrici de bandă și se pretează adesea la algoritmi mai simpli decât cei aplicabili matricelor rare în general; uneori este posibil să se aplice algoritmi pentru matrici dense și să se repete utilizarea acestora pe un număr mic de indici.

Reducerea lățimii de bandă

Algoritmul Cuthill-McKee poate fi utilizat pentru a reduce lățimea de bandă a unei matrice simetrice rare. Există totuși matrici pentru care algoritmul invers Cuthill-McKee are o performanță mai bună.

US National Geodetic Survey (NGS) folosește așa-numitul algoritm „bancar” al lui Richard Snay, deoarece operează mai rapid pe matrici rare, realiste, utilizate în Geodezie. Pot fi utilizate și alte metode.

Reduceți completarea

Completarea unui tablou constă din acele valori care de la zero devin diferite de zero în timpul executării unui algoritm. Pentru a reduce cerințele de memorie și numărul de operații aritmetice utilizate într-un algoritm, este util să minimizați completarea prin schimbarea rândurilor și coloanelor matricei. Descompunerea simbolică Cholesky poate fi utilizată pentru a calcula cea mai proastă completare posibilă înainte de a efectua descompunerea Cholesky propriu-zisă.

Pot fi utilizate și alte metode decât descompunerea Cholesky . Metodele de ortogonalizare (cum ar fi factorizarea QR) sunt comune, de exemplu, în rezolvarea problemelor cu metoda celor mai mici pătrate . Deși completarea este, în teorie, aceeași, în termeni practici „valorile false diferite de zero” pot fi diferite dacă metodele se schimbă. Versiunile simbolice ale acestor algoritmi pot fi utilizate într-un mod similar cu simbolic Cholesky pentru a calcula cel mai rău caz de completare.

Rezolvarea sistemelor de ecuații asociate matricelor rare

Există atât metode iterative, cât și metode directe pentru rezolvarea sistemelor asociate matricelor rare. O metodă iterativă foarte comună este cea a gradientului conjugat .

Bibliografie

Surse

  • ( EN ) Tewarson, Reginald P , Sparse Matrices (parte a seriei Matematică în științe și inginerie), Academic Press Inc., mai 1973. (Această carte, scrisă de un profesor al Universității de Stat din New York la Stony Book, este prima carte dedicată în întregime matricilor împrăștiate.Cursurile de licență care au folosit-o ca manual s-au ținut la începutul anilor 1980 ).
  • ( EN ) Pachet de multiplicare a matricei rare, Randolph E. Bank, Craig C. Douglas [1]
  • ( EN ) Pissanetzky, Sergio 1984, „Sparse Matrix Technology”, Academic Press
  • ( EN ) RA Snay. Reducerea profilului matricilor simetrice rare. Bulletin Géodésique, 50: 341–352, 1976. De asemenea, Memorandumul tehnic NOAA NOS NGS-4, National Geodetic Survey, Rockville, MD.

Perspective

Elemente conexe

Alte proiecte

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică