Redka matrika

matrika, v kateri je večina elementov enaka nič

Redka matrika (tudi raztresena matrika) je matrika, ki ima elemente, večinoma enake 0 (ima zelo malo elementov, ki so različni od 0).

Redka matrika se dobi pri iskanju približnih rešitev parcialnih diferencialnih enačb in integralskih enačb z metodo končnih elementov v dveh razsežnostih. Neničelni elementi so prikazani s črno barvo.

Izraz je skoval ameriški ekonomist Harry Max Markowitz (rojen 1927).

Redke matrike v glavnem pripadajo šibko povezanim sistemom. Najpogosteje se uporabljajo v znanosti pri reševanju parcialnih diferencialnih enačb. Redke matrike so zelo velike. Poseben problem je računalniško shranjevanje velikih matrik, ki v glavnem vsebujejo same ničle. To se lahko doseže na ta način, da se zapišejo samo lege od nič različnih elementov.

Pasovna matrika

uredi
Glavni članek: pasovna matrika.

Posebni primer redke matrike je pasovna matrika. Pri redki pasovni matriki se lahko definira spodnjo in zgornjo širino pasu. Spodnja širina pasu je najmanjše število   tako, da elementi   postanejo enaki 0, ko je  . Podobno je definirana tudi zgornja pasovna širina. Zgled: tridiagonalna matrika ima zgornjo in spodnjo pasovno širino enako 1.

Zgled redke matrike z zgornjo in s spodnjo pasovno širino 3.

 

Ničle so prikazane s pikami.

S preureditvijo vrstic in stolpcev se lahko dobi matrika z manjšo spodnjo pasovno širino. Znanih je več postopkov iskanja najmanjše pasovne širine. Postopek (algoritem) se imenuje minimizacija pasovne širine.

Glej tudi

uredi

Zunanje povezave

uredi
  • Weisstein, Eric Wolfgang. »Sparse Matrix«. MathWorld.
  • Množenje redkih matrik (angleško)
  • Načini računalniškega shranjevanja redkih matrik (angleško)