Vikipedio:Projekto matematiko/Maldensa tabelo

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Maldensa tabelo
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En la matematika subkorpo de cifereca analitiko maldensa tabelo estas matrico _populated_ unuavice kun nuloj.

_Sparsity_ estas koncepto, utila en kombinatoriko kaj apliko (areoj, areas) kiel reta teorio, de malalta denseco de gravaj datumoj aŭ ligoj. Ĉi tiu koncepto estas _amenable_ al kvanteca (racianta, rezonanta, kaŭzanta). Ĝi estas ankaŭ _noticeable_ en ĉiutaga vivo.

Giganta _sparse_ matricoj ofte aperi en scienco aŭ inĝenierado kiam solvanta (problemoj, problemas) por linearaj modeloj.

Kiam (butikanta, etaĝanta) kaj manipulanta _sparse_ matricoj sur la komputilo, ĝi estas ofte necesa al (modifi, aliigi) la normo (algoritmoj, algoritmas) kaj preni avantaĝo de la _sparse_ strukturo de la matrico. _Sparse_ datumoj estas per ĝia naturo facile kompresis, kiu povas liveri enormaj ŝparadoj en memora uzado. Kaj pli grave, manipulanta giganta _sparse_ matricoj kun la normo (algoritmoj, algoritmas) (majo, povas) esti neebla pro al ilia kruta amplekso. La difino de giganta dependas sur la aparataro kaj la komputilaj programoj havebla al manipuli la matrico.

Enhavo

1 (Difinoj, Difinas)
2 Ekzemplo
3 (Butikanta, Etaĝanta) maldensa tabelo
- 3.1 Diagonala matrico
4 Reduktanta la (elektra bendlarĝo, bendlarĝo)
5 Reduktanta la enspaci-en
6 Vidi ankaŭ
7 Referencoj
8 Ekstera (ligoj, ligas)

[redaktu] (Difinoj, Difinas)

Donita _sparse_ N×M matrico A la (linio, vico) (elektra bendlarĝo, bendlarĝo) por la nOno (linio, vico) estas difinita kiel

$b_n(\mathbf{A}) := \mathrm{min}_{1 \le m \le M} \lbrace m \mid a_{n, m} \neq 0 \rbrace$

La (elektra bendlarĝo, bendlarĝo) por la matrico estas difinita kiel

$B(\mathbf{A}) := \mathrm{max}_{1 \le n \le N} b_n(\mathbf{A})$

[redaktu] Ekzemplo

Bitmatrica bildo havanta nur 2 (koloroj, koloras, kolorigas), kun unu de ilin domina (diri (fajli, kolono, dosiero, paperujo, fajlilo) (tiu, ke, kiu) (butikoj, butikas) _handwritten_ signumo) povas esti kodita kiel maldensa tabelo (tiu, ke, kiu) enhavas nur (linio, vico) kaj kolumnaj nombroj por (rastrumeroj, rastrumeras) kun la ne-domina koloro.

[redaktu] (Butikanta, Etaĝanta) maldensa tabelo

La naiva datumstrukturo por matrico estas du dimensia tabelo. Ĉiu (termo, koeficiento, elemento) en la tabelo prezentas ero a_mi,j de la matrico kaj povas esti atingita per la du indeksoj mi kaj j. Por n×m matrico ni (bezoni, bezono, necesa) almenaŭ (n*m) / 8 (bitokoj, bitokas, bajtoj, bajtas) al prezenti la matrico kiam alprenanta 1 malmulto por ĉiu (termo, koeficiento, elemento).

Maldensa tabelo enhavas multaj (ofte plejparte) nulaj elementoj. La baza ideo kiam (butikanta, etaĝanta) _sparse_ matricoj estas al nur butiko la ne-nulaj elementoj kiel kontraŭ (butikanta, etaĝanta) ĉiuj elementoj. Dependanta sur la nombro kaj distribuo de la ne-nulaj elementoj, malsamaj datumstrukturoj povas esti uzita kaj liveri gigantaj ŝparadoj en memoro kiam (komparita, komparis) al naiva (maniero, proksimiĝi, proksimiĝo).

Unu ekzemplo de tia maldensa tabela aranĝo estas la (malnova) _Yale_ _Sparse_ Matrica Aranĝo [1]. Ĝi (butikoj, butikas) komenca _sparse_ N×N matrico M en (linio, vico) (formo, formi) uzanta tri (tabeloj, tabelas), A, Ia, Ja. _NZ_ signifas la nombro de nenulaj elementoj en matrico M. La tabelo A tiam estas de longo _NZ_ kaj tenas ĉiuj nenulaj elementoj de M. La tabelo Ia (butikoj, butikas) je Ia(mi) la pozicio de la unua ero de (linio, vico) mi en la _sparse_ tabelo A. La longo de (linio, vico) mi estas difinita per Ia(mi+1) - Ia(mi). Pro tio Ia (bezonas, bezonoj) al esti de longo N + 1. En tabelo Ja, la kolumna indekso de la ero A(j) estas butikita. Ja estas de longo _NZ_.

[redaktu] Diagonala matrico

Tre kompetenta strukturo por diagonala matrico estas al butiko (justa, ĵus) la elementoj en la ĉefa diagonalo kiel unu dimensia tabelo. Por n×n matrico ni (bezoni, bezono, necesa) nur n / 8 (bitokoj, bitokas, bajtoj, bajtas) kiam alprenanta 1 malmulto por ĉiu (termo, koeficiento, elemento).

[redaktu] Reduktanta la (elektra bendlarĝo, bendlarĝo)

La _Cuthill_-_McKee_ algoritmo povas kutimi redukti la (elektra bendlarĝo, bendlarĝo) de _sparse_ simetria matrico. Estas tamen matricoj por kiu la Dorsflanko _Cuthill_-_McKee_ algoritmo plenumas pli bona.

La Nacia _Geodetic_ Katastro (_NGS_) uzas D-ro _Richard_ _Snay_'s "(Bankestra, Bankista, Bankiera)" algoritmo ĉar sur realisma _sparse_ matricoj uzita en Geodezia labora ĝi havas pli bona (seanco, rendimento).

Estas multaj aliaj manieroj en uzi.

[redaktu] Reduktanta la enspaci-en

La enspaci-en de matrico estas tiuj elementoj kiu ŝanĝi de komenca nulo al ne-nula valoro dum la ekzekuto de algoritmo. Al redukti la memoro (postuloj, bezonoj, bezonas) kaj la nombro de aritmetikaj operacioj uzita dum algoritma ĝi estas utila al minimumigi la enspaci-en per (verganta, reŝaltanta) (linioj, vicoj, linias, vicas) kaj kolumnoj en la matrico. La signa _Cholesky_ malkomponaĵo povas kutimi kalkuli la plej malbona ebla enspaci-en antaŭ farante la reala _Cholesky_ malkomponaĵo.

Estas aliaj manieroj ol la _Cholesky_ malkomponaĵo en uzi. _Orthogonalization_ manieroj (kiel _QR_ faktorigo) estas komuna, ekzemple, kiam solvanta (problemoj, problemas) per plej malgranda (kvadratoj, placoj, kvadratigas) manieroj. Dum la teoria enspaci-en estas ankoraŭ la sama, en praktika (termoj, kondiĉoj, terminoj, termas, terminas) la "malveraj ne-nuloj" povas diferenci por malsamaj manieroj. Kaj signa (versioj, versias) de tiuj (algoritmoj, algoritmas) povas esti uzita en la sama maniero kiel la signa _Cholesky_ al komputi plej malbona (kesto, okazo) enspaci-en.