Naslov Ubrzanje QR faktorizacije s pivotiranjem Autor Ivan Čeh Mentor Sanja Singer (mentor)Član povjerenstva Sanja Singer (predsjednik povjerenstva)Član povjerenstva Maja Starčević (član povjerenstva)Član povjerenstva Tomislav Berić (član povjerenstva)Član povjerenstva Goranka Nogo (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2018-11-27, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Sažetak U ovom radu predstavljeni su neki algoritmi za ubrzanje QR faktorizacije matrice sa stupčanim pivotiranjem (QRCP faktorizacije). QR faktorizacija se izvršava vrlo brzo na modernim računalima s memorijskom hijerarhijom i većim brojem procesorskih jezgara korištenjem blokovskog algoritma. Koristi se WY reprezentacija produkta Householderovih reflektora. Taj algoritam je implementiran u LAPACK-ovoj rutini dgeqrf. QRCP faktorizacija je po broju potrebnih aritmetičkih operacija neznatno zahtjevnija od QR faktorizacije, no kod nje je teško postići takvo ubrzanje blokovskim algoritmom, jer ne možemo unaprijed donijeti odluku o sljedećih \(b\) pivotnih stupaca. Djelomično rješenje je blokovska QRCP faktorizacija koja je implementirana u LAPACK-ovoj rutini dgeqp3, no ona ne daje višestruko ubrzanje zbog potrebe za ažuriranjem jednog retka u svakom koraku. Naveli smo neke primjene QRCP faktorizacije i opisali primjenu za nalaženje aproksimacija matrice nižeg ranga gdje QRCP faktorizacija često daje rezultate usporedive s optimalnom, ali računski zahtjevnijom, singularnom dekompozicijom. Predstavili smo tri druga pristupa QRCP faktorizaciji, koja su vremenski znatno efikasnija od klasične QRCP faktorizacije, te neke njihove varijacije. Veću brzinu im najčešće daje činjenica da ne zahtijevaju uvijek odabir stupca s najvećom normom. Prvi je algoritam s kontroliranim lokalnim pivotiranjem kod kojeg je unaprijed određena najgora dopustiva uvjetovanost matrice. Tražimo najbolje pivotne kandidate u trenutnom bloku, a u slučaju da svi preostali kandidati daju lošu uvjetovanost, blok proširujemo novim stupcima. Drugi je algoritam s izbjegavanjem komunikacije, koji dijeli matricu na blokove stupaca. Na blokovima paralelno provodi QRCP faktoriazciju i redukcijom dolazi do najboljih \(b\) kandidata za sljedeće pivotne stupce. Treći je algoritam randomizirane QRCP faktorizacije koja koristi množenje slijeva slučajnom matricom \(\Omega\) male visine, kako bi se smanjio broj redaka. Na takvoj se matrici provodi klasična QRCP faktorizacija te se njome izabire redoslijed pivotnih stupaca prvotne matrice \(A\). Ako matrica \(A\) nije dovoljno uska, generiranje slučajnog uzorka treba ponavljati, što se može učiniti traženjem novih slučajnih brojeva ili korištenjem postojećeg slučajnog uzorka. Implementirane su dvije verzije randomizirane QRCP faktorizacije, a njihovim testiranjem potvrđeno je očekivanje da daju rezultate kvalitetom usporedive s klasičnom QRCP faktorizacijom, uz višestruko vremensko ubrzanje.
Sažetak (engleski) In this paper we presented some algorithms for fast QR matrix factorization with column pivoting (QRCP factorization). The QR factorization runs very fast on modern computers due to memory hierarchy and parallel execution on multiple CPU cores by using blocked algorithm. WY representation of the product of Householder reflectors is used for this purpose. The algorithm is implemented in LAPACK routine dgeqrf. The QRCP factorization is not much more complex than the QR factorization, compared by the number of arithmetic operations needed, but it is hard to preform into a blocked algorithm because we cannot immediately decide about the next \(b\) pivot columns. Partial solution is the blocked QRCP factorization which is implemented in LAPACK routine dgeqp3. It does not provide multiple speed-up because it updates only one row in each step. We showed some applications of the QRCP factorization, and described the application in finding lower rank approximations where the QRCP factorization often gives results comparable to optimal, but computationally more complex, singular value decomposition. We presented three other approaches to the QRCP factorization, that are much more time efficient than the classical QRCP factorization, and some variations of them. What makes them fast is the fact they do not require the column with the biggest norm in each step. The first algorithm is the QR factorization with controlled local pivoting, each uses predetermined worst allowed matrix condition number. We search for the best pivot candidates in a current block, until each of them causes low condition number. Then the current block is expanded by the new columns. The second one is communication avoiding algorithm, which divides matrix to column blocks on which the QRCP factorization will be done in parallel, and it finds the best choice for \(b\) pivot columns. The third algorithm is the randomized QRCP factorization which multiplies matrix A from the left by \(\Omega\), to decrease the number of rows. On that matrix we perform the classical QRCP factorization, which is used to detemine order of pivot columns in the initial matrix \(A\). If \(A\) is not thin enough, randomized sampling must be repeated which can be done by repeated random number generation, or by using, already existing, random sample. Two versions of the randomized QRCP factorization are implemented. We tested them and confirmed the expectation that their results will be comparable to the classical QRCP factorization by quality with significant speedup.
Ključne riječi
QR faktorizacija
QRCP faktorizacija
algoritam s kontroliranim lokalnim pivotiranjem
algoritam s izbjegavanjem komunikacije
algoritam randomizirane QRCP faktorizacije
Ključne riječi (engleski)
QR factorization
QRCP factorization
QR factorization with controlled local pivoting
communication avoiding algorithm
randomized QRCP factorization
Jezik hrvatski URN:NBN urn:nbn:hr:217:570941 Studijski program Naziv: Računarstvo i matematika Vrsta resursa Tekst Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2019-03-27 15:05:24
