hrvatski

Ubrzanje jednostranog Jacobijevog algoritma za nalaženje svojstvenih vrijednosti matrica korištenjem sortiranja

Brzo i efikasno nalaženje svojstvenih vrijednosti i svojstvenih vektora matrica danas predstavlja jedan od najinteresantnijih i najkorisnijih problema, kako za znanstvenu zajednicu, tako i za komercijalnu upotrebu. Među brojnim metodama koje nalaze svojstvene vrijednosti matrica, svakako je najpoznatiji QR algoritam, ali važno mjesto zauzima upravo Jacobijeva metoda. Jacobijeva metoda dugo je bila zapostavljena, jer je obzirom na QR metodu bila sporija, no danas je ponovno porastao interes za nju zbog jednostavne paralelizacije. Sama metoda se bazira na implicitnoj singularnoj dekompoziciji matrica (SVD). Primjene SVD-a su jako velike. Neke od najvažnijih su u teorijske svrhe gdje se koristi za dokazivanje činjenica, u matričnim algoritmima gdje se često koristi kao dio drugih algoritama, u znanstvenim proračunima, u stvarnim problemima kao što su računarska grafika, procesiranje signala, statistika, algoritmi za pretraživanje web-a, analiza podataka (tzv. data mining), rjeˇavanje linearnih sustava te u mnogim drugim problemima. Početkom devedesetih godina prošlog stoljeća, dokazano je da Jacobijeva metoda ima bolju relativnu točnost no što je imaju QR algoritam, podijeli i vladaj (engl. divide and conquer) algoritam, tradicionalna bisekcija ili bilo koji drugi algoritam koji prvo radi tridijagonalizaciju početne matrice. Odlika ovih algoritama je brzina, ali se bidiagonalizacijom dosta gubi na točnosti. Jacobijeva je metoda generalno sporija od QR metode, ali zato daje mnogo točnije rezultate, što joj je i glavna prednost. U zadnje vrijeme dosta se radi na optimizaciji i ubrzanju Jacobijeve metode, pa su postignuti znatni uspjesi u ubrzanju ove metode koji su je učinili ne samo točnijom, nego čak i bržom od QR metode. Ubrzanje Jacobijeve metode postignuto je u dva koraka. Prvi korak je da su napravljena neka pretprocesiranja, koja su početnu matricu svela na neki ”ljepši” oblik koji brže konvergira k rješenju. Razlikujemo dvije Jacobijeve metode za nalaženje svojstvenih vrijednosti, jednostrani i dvostrani Jacobijev algoritam. U praksi se pokazalo da je jednostrani Jacobijev algoritam mnogo točniji i brži nego je to dvostrani algoritam, pa ćemo više pažnje posvetiti jednostranom Jacobijevom algoritmu. Neke od prednosti jednostranog Jacobijevog algoritam su da je jednostavan za paralelizaciju, zahtijeva manje memorije nego njemu konkurentski algoritmi, može se koristiti bilo koja pivotna strategija, pogodan je za rad s blok stupcima, te u potpunosti može iskoristiti vektorizaciju. Neke od mana jednostranog algoritma su da nakon pretprocesiranja uništava skoru dijagonalnost početne matrice. Na kraju, svaka provjera točnosti, odnosno metoda zaustavljanja algoritma je skupa i traje reda veličine n * 3/2 operacija. Jednostrani Jacobijev algoritam provodi se u dva koraka. Kao prvi korak napravi se faktorizacija Choleskog odnosno simetrična indefinitna faktorizacija već prema tome je li matrica pozitivno definitna ili ne. Zatim se stupci faktora ortogonaliziraju, tj. radi se SVD, odnosno hiperbolički SVD faktora matrice. Ubrzavanje drugog koraka algoritma vrši se korištenjem nekih specijalnih strategija pivotiranja/rotiranja elemenata. U zadnje vrijeme dosta se radi na paralelizaciji Jacobijeve metode zbog relativno laganog načina paralelizacije samog algoritma.

Jacobijeva metoda; svojstvene vrijednosti; SVD

nije evidentirano