„Gauss-elimináció” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló |
aNincs szerkesztési összefoglaló |
||
152. sor:
==Ritka mátrixok==
A [[ritka mátrix]]ok Gauss-eliminációja során fellépő jelenséget, hogy olyan helyeken keletkezik nemzérus elem, ahol eredetileg nulla állt, feltöltődésnek nevezik. Mivel a ritka mátrixokban a nulla elemeket általában helytakarékosan tárolják, ezért a feltöltődésre ügyelni kell: helyet kell szerezni az újonnan keletkezett elemeknek. Ha külön nem foglalkoznak vele, a feltöltődés nagymértékű is lehet; egy eliminációs lépés alatt akár az egész mátrix feltöltődhet.<ref>[http://www.tankonyvtar.hu/hu/tartalom/tkt/numerikus-modszerek-1/ch02s03.html Stoyan Gisbert-Takó Galina: ''Numerikus módszerek I.'']</ref>
A [[minimális feltöltődés]] ''(minimum fill-in)'' elérése kívánatos cél, a szükséges számítási bonyolultságról még kevés tanulmány született;<ref>[https://arxiv.org/abs/1606.08141 Yixin Cao, R. B. Sandeep: Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds]</ref> általában segíthet, ha a problémát okozó sorokat, oszlopokat a Gauss-elimináció végén kezeljük, amit a ''minimális fokszám algoritmus'' (az elimináció k-adik lépésében azt a főátlóbeli elemet választjuk főelemnek, amelynek az i index fokszáma minimális) valósít meg.
| |||