Maldensa matrico

El Vikipedio, la libera enciklopedio
Jump to navigation Jump to search
Ekzemplo
La supera matrico havas nur 9 nenulajn elementojn. La maldenso estas 74%, alivorte la denso estas 26%.
Maldensa matrico donita kiam oni solvis fini-elementan problemon du-dimensie. La nigraj punktoj estas nenulaj.

En cifereca analizo, maldensa matrico estas matrico kies plejmulto da elementoj estas nulo. Alie, ĝi estas densa. La nombro de nulaj elementoj dividita de la tuta nombro de elementoj (ekz, m × n por m × n-matrico) nomiĝas la maldenso de la matrico. Ĝia komplemento estas la denso.

Granda maldensa matrico ofte aperas en scienca kaj inĝeniera aplikado, kiam oni solvas partan diferencialan ekvacion.

Memori maldensan matricon[redakti | redakti fonton]

Tipe matrico memoriĝas kiel du-dimensia tabelo, kiun oni vizitas per indeksoj i kaj j. Konvencie, i estas la horizonta indekso kaj  j estas la vertikala. La memorkosto tiel por m × n matrico estas funkcio de m × n.

Por maldensa matrico, oni povas grande malmultigi la memorkoston per memori nur la nenulaĵojn. Variaj datumstrukturoj utiliĝus kondiĉe je la preciza denso kaj distribuo de la nenulaĵoj. La dilemo estas ke viziti elementojn en tiaj datumstrukturoj estos pli multekosta, kaj necesus kroma strukturo se oni volus rekonstrui la originan matricon precize.

Estas du klasoj de datumstrukturoj por memori maldensan matricon:

  • Tiaj, kiuj subtenas rapidan ŝanĝon: DOK (Vortaro de klavoj), LoL (Listo da listoj), aŭ COO (Kunorda listo). Ili utilas por rekonstrui la originan matricon rapide.
  • Tiaj, kiuj subtenas rapidan vizitadon kaj matrican operacion: CSR (Presita Maldensa Horizontalo) aŭ CSC (Presita Maldensa Vertikalo).