Sparsom matrise - Sparse matrix

Eksempel på sparsom matrise ${\ displaystyle \ left ({\ begin {smallmatrix} 11 & 22 & 0 & 0 & 0 & 0 & 0 \\ 0 & 33 & 44 & 0 & 0 & 0 & 0 \\ 0 & 0 & 55 & 66 & 77 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 88 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 99 \\\ slutten {smallmatrix}}$

Ovenstående sparsomme matrise inneholder bare 9 ikke-null elementer, med 26 null elementer. Sparsiteten er 74%, og densiteten er 26%.

En sparsom matrise oppnådd ved løsning av et begrenset elementproblem i to dimensjoner. Elementene uten null er vist i svart.

I numerisk analyse og vitenskapelig databehandling er en sparsom matrise eller sparsom matrise en matrise der de fleste elementene er null. Det er ingen streng definisjon når det gjelder andelen nullverdielementer for at en matrise skal kvalifiseres som sparsom, men et vanlig kriterium er at antallet ikke-nullelementer omtrent er lik antall rader eller kolonner. Derimot, hvis de fleste elementene er ikke-null, regnes matrisen som tett . Antall nullverdige elementer dividert med det totale antall elementer (f.eks. M × n for en m × n-matrise) blir noen ganger referert til som sparsiteten til matrisen.

Konseptuelt tilsvarer sparsitet systemer med få parvise interaksjoner. Tenk for eksempel på en ballelinje som er forbundet med fjærer fra den ene til den neste: dette er et sparsomt system, da bare tilstøtende kuler er koblet. Derimot, hvis den samme linjen med baller skulle ha fjærer som forbinder hver ball med alle andre baller, ville systemet svare til en tett matrise. Begrepet sparsitet er nyttig i kombinatorikk og applikasjonsområder som nettverksteori og numerisk analyse , som vanligvis har en lav tetthet av betydelige data eller forbindelser. Store sparsomme matriser dukker ofte opp i vitenskapelige eller tekniske applikasjoner når vi løser delvise differensialligninger .

Når du lagrer og manipulerer sparsomme matriser på en datamaskin , er det fordelaktig og ofte nødvendig å bruke spesialiserte algoritmer og datastrukturer som drar fordel av matrisens sparsomme struktur. Spesialiserte datamaskiner er laget for sparsomme matriser, ettersom de er vanlige innen maskinlæringsfeltet. Operasjoner som bruker standard tettmatrisestrukturer og algoritmer er langsomme og ineffektive når de brukes på store, sparsomme matriser ettersom behandling og minne er bortkastet på nullene. Sparsomme data blir av natur lettere komprimert og krever dermed betydelig mindre lagring . Noen svært store sparsomme matriser er umulige å manipulere ved hjelp av standard tette matrisealgoritmer.

Lagre en sparsom matrise

En matrise lagres vanligvis som en todimensjonal matrise. Hver oppføring i matrisen representerer et element a _{i , j} i matrisen og er tilgjengelig for de to indeksene i og j . Konvensjonelt, i er den rad indeksen, nummerert fra topp til bunn, og j er kolonneindeksen, nummerert fra venstre til høyre. For en m × n -matrise er mengden minne som kreves for å lagre matrisen i dette formatet proporsjonal med m × n (ser bort fra at dimensjonene til matrisen også må lagres).

I tilfelle av en sparsom matrise kan betydelige minnebehovsreduksjoner realiseres ved å lagre bare ikke-null oppføringer. Avhengig av antall og fordeling av oppføringene som ikke er null, kan forskjellige datastrukturer brukes og gi store besparelser i minnet sammenlignet med den grunnleggende tilnærmingen. Avveiningen er at tilgang til de enkelte elementene blir mer kompleks og ytterligere strukturer er nødvendig for å kunne gjenopprette den opprinnelige matrisen entydig.

Formater kan deles inn i to grupper:

• De som støtter effektiv modifisering, for eksempel DOK (Dictionary of keys), LIL (List of lists) eller COO (Coordinate list). Disse brukes vanligvis til å konstruere matrisene.
• De som støtter effektiv tilgang og matriseoperasjoner, for eksempel CSR (Compressed Sparse Row) eller CSC (Compressed Sparse Column).

Dictionary of keys (DOK)

DOK består av en ordbok som kartlegger (rad, kolonne) - sammen med verdien av elementene. Elementer som mangler i ordlisten er null. Formatet er bra for trinnvis å konstruere en sparsom matrise i tilfeldig rekkefølge, men dårlig for å iterere over ikke-nullverdier i leksikografisk rekkefølge. Man konstruerer vanligvis en matrise i dette formatet og konverterer deretter til et annet mer effektivt format for behandling.

Liste over lister (LIL)

LIL lagrer en liste per rad, med hver oppføring som inneholder kolonneindeksen og verdien. Vanligvis blir disse oppføringene sortert etter kolonneindeks for raskere oppslag. Dette er et annet format som er bra for inkrementell matrisekonstruksjon.

Koordinateliste (COO)

COO lagrer en liste over (rad, kolonne, verdi) tupler. Ideelt sett blir oppføringene sortert først etter radindeks og deretter etter kolonneindeks, for å forbedre tilfeldige tilgangstider. Dette er et annet format som er bra for inkrementell matrisekonstruksjon.

Komprimert sparsom rad (CSR, CRS eller Yale -format)

Den komprimerte sparsomme raden (CSR) eller komprimert radlagring (CRS) eller Yale-formatet representerer en matrise M med tre (endimensjonale) matriser, som henholdsvis inneholder ikke-nullverdier, rekkevidde av rader og kolonneindekser. Det ligner COO, men komprimerer radindeksene, derav navnet. Dette formatet gir rask radtilgang og matrise-vektormultiplikasjoner ( M x ). CSR-formatet har vært i bruk siden minst midten av 1960-tallet, med den første komplette beskrivelsen som ble vist i 1967.

CSR-formatet lagrer en sparsom m × n matrise M i radform ved hjelp av tre (endimensjonale) matriser (V, COL_INDEX, ROW_INDEX) . Let NNZ betegne antallet ikke-null oppføringer i M . (Vær oppmerksom på at nullbaserte indekser skal brukes her.)

• Rekkene V og COL_INDEX er av lengde NNZ , og inneholder ikke-null-verdier og kolonneindekser av disse verdiene henholdsvis.

• Matrisen ROW_INDEX er av lengde m + 1 og koder for indeksen i V og COL_INDEX der gitt rad starter. Dette tilsvarer at ROW_INDEX [j] koder det totale antallet null -nuller over rad j . Det siste elementet er NNZ , dvs. den fiktive indeksen i V umiddelbart etter den siste gyldige indeksen NNZ - 1 .

For eksempel matrisen

${\ displaystyle {\ begin {pmatrix} 5 & 0 & 0 & 0 \\ 0 & 8 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 6 & 0 & 0 \\\ slutt {pmatrix}}}$

er en 4 × 4 matrise med 4 ikke -null elementer, derfor

   V         = [ 5 8 3 6 ]
   COL_INDEX = [ 0 1 2 1 ]
   ROW_INDEX = [ 0 1 2 3 4 ] 

forutsatt et nullindeksert språk.

For å trekke ut en rad definerer vi først:

   row_start = ROW_INDEX[row]
   row_end   = ROW_INDEX[row + 1]

Deretter tar vi skiver fra V og COL_INDEX som starter med row_start og slutter på row_end.

For å trekke ut rad 1 (andre rad) i denne matrisen setter vi row_start=1og row_end=2. Deretter lager vi skivene V[1:2] = [8]og COL_INDEX[1:2] = [1]. Vi vet nå at i rad 1 har vi ett element i kolonne 1 med verdi 8.

I dette tilfellet inneholder CSR -representasjonen 13 oppføringer, mot 16 i den opprinnelige matrisen. CSR -formatet lagrer bare minne når NNZ <( m ( n - 1) - 1) / 2 . Et annet eksempel, matrisen

${\ displaystyle {\ begin {pmatrix} 10 & 20 & 0 & 0 & 0 & 0 \\ 0 & 30 & 0 & 40 & 0 & 0 \\ 0 & 0 & 50 & 60 & 70 & 0 \\ 0 & 0 & 0 & 0 & 0 & 80 \\\ slutten {pmatrix}}}$

er en 4 × 6 matrise (24 oppføringer) med 8 ikke -nullelementer, så

   V         = [ 10 20 30 40 50 60 70 80 ]
   COL_INDEX = [  0  1  1  3  2  3  4  5 ]   
   ROW_INDEX = [  0  2  4  7  8 ]

Det hele er lagret som 21 oppføringer.

• ROW_INDEX deler matrisen V i rader: (10, 20) (30, 40) (50, 60, 70) (80);
• COL_INDEX justerer verdiene i kolonner: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Vær oppmerksom på at i dette formatet er den første verdien av ROW_INDEX alltid null og den siste er alltid NNZ , så de er på en måte redundante (selv om det i programmeringsspråk hvor matriselengden eksplisitt må lagres, ville NNZ ikke være overflødig). Ikke desto mindre unngår dette behovet for å håndtere et unntakstilfelle når du beregner lengden på hver rad, ettersom det garanterer formelen ROW_INDEX [ i + 1] - ROW_INDEX [ i ] fungerer for enhver rad i . Videre er minnekostnaden for denne redundante lagringen sannsynligvis ubetydelig for en tilstrekkelig stor matrise.

De (gamle og nye) Yale sparsomme matriseformatene er forekomster av CSR -opplegget. Det gamle Yale -formatet fungerer nøyaktig som beskrevet ovenfor, med tre matriser; det nye formatet kombinerer ROW_INDEX og COL_INDEX til en enkelt matrise og håndterer matrisens diagonal separat.

For logiske tilknytningsmatriser kan dataoppsettet utelates, ettersom eksistensen av en oppføring i radmatrisen er tilstrekkelig til å modellere en binær tilknytningsrelasjon.

Det er sannsynligvis kjent som Yale -formatet fordi det ble foreslått i Yale Sparse Matrix Package -rapporten fra 1977 fra Institutt for informatikk ved Yale University.

Komprimert sparsom kolonne (CSC eller CCS)

CSC ligner CSR bortsett fra at verdier leses først etter kolonne, en radindeks lagres for hver verdi og kolonnepekere lagres. For eksempel er CSC (val, row_ind, col_ptr) , hvor val er en matrise med (fra topp til bunn, deretter fra venstre til høyre) ikke-nullverdier i matrisen; row_ind er radindeksene som tilsvarer verdiene; og, col_ptr er listen over val indekser der hver kolonne starter. Navnet er basert på at informasjon om kolonneindeks komprimeres i forhold til COO -formatet. Man bruker vanligvis et annet format (LIL, DOK, COO) for konstruksjon. Dette formatet er effektivt for aritmetiske operasjoner, kolonneskæring og matrise-vektorprodukter. Se scipy.sparse.csc_matrix . Dette er det tradisjonelle formatet for å spesifisere en sparsom matrise i MATLAB (via sparsefunksjonen).

Spesiell struktur

Banded

En viktig spesiell type sparsomme matriser er båndmatrise , definert som følger. Den nedre båndbredden til en matrise A er det minste tallet p slik at oppføringen a _{i , j} forsvinner når i > j + p . På samme måte er den øvre båndbredden det minste tallet p slik at a _{i , j} = 0 når i < j - p ( Golub & Van Loan 1996 , §1.2.1). For eksempel har en tridiagonal matrise lavere båndbredde 1 og øvre båndbredde 1 . Som et annet eksempel har følgende sparsomme matrise lavere og øvre båndbredde begge lik 3. Legg merke til at nuller er representert med prikker for klarhet.

${\ displaystyle \ left ({\ begin {smallmatrix} X & X & X & \ cdot & \ cdot & \ cdot & \ cdot & \\ X & X & \ cdot & X & X & \ cdot & \ cdot & \\ X & \ cdot & X & \ cdot & X & \ cdot & \ cdot & \\\ cdot & X & \ cdot & X & \ cdot & X & \ cdot & \\\ cdot & X & X & \ cdot & X & X & X & \\\ cdot & \ cdot & \ cdot & X & X & \ cdot & \\\ cdot & \ cdot & \ cdot & \ cdot & X & \ cdot & X & \\\ ende {smallmatrix}} \ høyre)}$

Matriser med rimelig liten øvre og nedre båndbredde er kjent som båndmatriser og egner seg ofte til enklere algoritmer enn generelle sparsomme matriser; eller man kan noen ganger bruke tette matrisealgoritmer og oppnå effektivitet ved å sløyfe over et redusert antall indekser.

Ved å omorganisere radene og kolonnene i en matrise A kan det være mulig å oppnå en matrise A ' med lavere båndbredde. En rekke algoritmer er designet for minimering av båndbredde .

Diagonal

En veldig effektiv struktur for et ekstremt tilfelle av båndmatriser , diagonalmatrisen , er å lagre bare oppføringene i hoveddiagonalen som en endimensjonal matrise , så en diagonal n × n matrise krever bare n oppføringer.

Symmetrisk

En symmetrisk sparsom matrise oppstår som adjasensmatrisen til en ikke -styrt graf ; den kan lagres effektivt som en tilstøtende liste .

Blokk diagonal

En blokkdiagonal matrise består av delmatriser langs dens diagonale blokker. En blokkdiagonal matrise A har formen

${\ displaystyle \ mathbf {A} = {\ begin {bmatrix} \ mathbf {A} _ {1} & 0 & \ cdots & 0 \\ 0 & \ mathbf {A} _ {2} & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & \ mathbf {A} _ {n} \ end {bmatrix}},}$

hvor A _k er en firkantmatrise for alle k = 1, ..., n .

Redusere utfylling

Den fill-in av en matrise er disse oppføringene som endres fra en innledende null til en annen verdi enn null under utførelsen av en algoritme. For å redusere minnekravene og antall aritmetiske operasjoner som brukes under en algoritme, er det nyttig å minimere utfyllingen ved å bytte rader og kolonner i matrisen. Den symbolske Cholesky-dekomponeringen kan brukes til å beregne den verste mulige utfyllingen før den faktiske Cholesky-dekomponeringen utføres .

Det er andre metoder enn Cholesky -dekomponeringen i bruk. Ortogonaliseringsmetoder (for eksempel QR -faktorisering) er vanlige, for eksempel når du løser problemer med minst kvadratmetoder. Selv om den teoretiske utfyllingen fortsatt er den samme, kan de "falske ikke-nullene" i praksis være forskjellige for forskjellige metoder. Og symbolske versjoner av disse algoritmene kan brukes på samme måte som den symbolske Cholesky for å beregne fill-in i verste fall.

Løse sparsomme matriksligninger

Både iterative og direkte metoder eksisterer for sparsom matriseløsning.

Iterative metoder, for eksempel konjugatgradientmetode og GMRES, bruker raske beregninger av matrise-vektorprodukter , der matrisen er sparsom. Bruken av forkondisjonatorer kan påskynde konvergensen av slike iterative metoder betydelig. ${\ displaystyle Ax_ {i}}$${\ displaystyle A}$

Programvare

Mange programvarebiblioteker støtter sparsomme matriser, og tilbyr løsere for sparsomme matriksligninger. Følgende er åpen kildekode:

• SuiteSparse , en pakke med sparsomme matrisealgoritmer, rettet mot den direkte løsningen av sparsomme lineære systemer.
• PETSc , et stort C -bibliotek, som inneholder mange forskjellige matriseoppløsere for en rekke matriselagringsformater.
• Trilinos , et stort C ++-bibliotek, med underbiblioteker dedikert til lagring av tette og sparsomme matriser og løsning av tilsvarende lineære systemer.
• Eigen3 er et C ++ - bibliotek som inneholder flere sparsomme matriseløsere. Imidlertid er ingen av dem parallelle .
• MUMPS ( MU ltifrontal M assively P arallel sparse direct S olver), skrevet i Fortran90, er en frontal løsning .
• DUNE , et endelig elementbibliotek som også har et underbibliotek for sparsomme lineære systemer og deres løsning.
• PaStix .
• SuperLU .
• Armadillo gir en brukervennlig C ++ innpakning for BLAS og LAPACK.
• SciPy gir støtte for flere sparsomme matriseformater, lineær algebra og løsere.
• SPArse Matrix (spam) R- og Python -pakke for sparsomme matriser.
• Wolfram Language Tools for håndtering av sparsomme matriser
• ALGLIB er et C ++ og C# bibliotek med sparsom lineær algebra støtte
• ARPACK Fortran 77 bibliotek for sparsom matrisediagonalisering og manipulasjon, ved hjelp av Arnoldi -algoritmen
• SPARSE Referanse (gammel) NIST -pakke for (ekte eller kompleks) sparsom matrisediagonalisering
• SLEPc Library for løsning av store lineære systemer og sparsomme matriser
• Sympiler , en domenespesifikk kodegenerator og bibliotek for å løse lineære systemer og kvadratiske programmeringsproblemer.
• Scikit-learn En Python-pakke for dataanalyse inkludert sparsomme matriser.

Historie

Begrepet sparsom matrise ble muligens laget av Harry Markowitz som startet noe pionerarbeid, men deretter forlot feltet.

Se også

Merknader

Referanser

• Golub, Gene H .; Van Loan, Charles F. (1996). Matrix Computations (3. utg.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Stoer, Josef; Bulirsch, Roland (2002). Introduksjon til numerisk analyse (3. utg.). Berlin, New York: Springer-Verlag . ISBN 978-0-387-95452-3.
• Tewarson, Reginald P. (mai 1973). Sparse Matrices (Del av serien Mathematics in Science & Engineering) . Academic Press Inc. (Denne boken, av en professor ved State University of New York i Stony Book, var den første boken eksklusivt dedikert til sparsomme matriser. Gradueringskurs som brukte dette som lærebok ble tilbudt ved det universitetet på begynnelsen av 1980 -tallet).
• Bank, Randolph E .; Douglas, Craig C. "Sparse Matrix Multiplication Package" (PDF) .
• Pissanetzky, Sergio (1984). Sparse Matrix Technology . Academic Press.
• Snay, Richard A. (1976). "Redusere profilen til sparsomme symmetriske matriser". Bulletin Géodésique . 50 (4): 341–352. Bibcode : 1976BGeod..50..341S . doi : 10.1007/BF02521587 . hdl : 2027/uc1.31210024848523 . S2CID  123079384 . Også NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.

Videre lesning

• Gibbs, Norman E .; Poole, William G .; Stockmeyer, Paul K. (1976). "En sammenligning av flere båndbredde og profilreduserende algoritmer" . ACM -transaksjoner på matematisk programvare . 2 (4): 322–330. doi : 10.1145/355705.355707 . S2CID  14494429 .
• Gilbert, John R .; Moler, Cleve; Schreiber, Robert (1992). "Sparsomme matriser i MATLAB: Design og implementering" . SIAM Journal on Matrix Analysis and Applications . 13 (1): 333–356. CiteSeerX  10.1.1.470.1054 . doi : 10.1137/0613024 .
• Sparse Matrix Algorithms Research ved Texas A&M University.
• SuiteSparse Matrix Collection
• LITT prosjekt Et EU-finansiert prosjekt om sparsomme modeller, algoritmer og ordlæringslæring for store data.