Fakulta informačních technologií VUT v Brně

Detail publikace

Accelerated Sparse Matrix Operations in Nonlinear Least Squares Solvers

POLOK Lukáš. Accelerated Sparse Matrix Operations in Nonlinear Least Squares Solvers. Brno: Ústav počítačové grafiky a multimédií FIT VUT v Brně, 2017.
Název česky
Akcelerace operací nad řídkými maticemi v nelineární metodě nejmenších čtverců
Typ
obecné
Jazyk
angličtina
Autoři
Polok Lukáš, Ing. (UPGM FIT VUT)
Klíčová slova
Nelineární metoda nejmenších čtverců; numerické metody; řídké blokové matice; obecné výpočty na jednotkách grafických akcelerátorů.
Abstrakt

Tato práce se zaměřuje na datové struktury pro reprezentaci řídkých blokových matic a s nimi spojených výpočetních algoritmů, jež jsem navrhl. Řídké blokové matice se vyskytují při řešení mnoha dílčích problémů jako například při řešení metody nejmenších čtverců. Nelineární metoda nejmenších čtverců (NLS) je často aplikována v robotice pro řešení problému lokalizace robota (SLAM) nebo v příbuzných úlohách 3D rekonstrukce v počítačovém vidění (BA), (SfM). Problémy konečných elementů (FEM) a parciálních diferenciálních rovnic (PDE) v oboru fyzikálních simulací můžou také mít blokovou strukturu.

Většina existujících implementací řídké lineární algebry používají řídké matice s granularitou jednotlivých elementů a jen několik málo podporuje řídké blokové matice. To může být způsobeno složitostí blokových formátů, jež snižuje rychlost výpočtů, pokud bloky nejsou dost velké. Některé ze specializovaných NLS optimalizátorů v robotice a počítačovém vidění používají blokové matice jako interní reprezentaci, aby snížily cenu sestavování řídkých matic, ale nakonec tuto reprezentaci převedou na elementovou řídkou matici pro implementaci k řešení systémů rovnic.

Existující implementace pro řídké blokové matice se většinou soustředí na jedinou operaci, často násobení matice vektorem. Řešení navržené v této disertaci pokrývá širší spektrum funkcí: implementovány jsou funkce pro efektivní sestavení řídké blokové matice, násobení matice vektorem nebo jinou maticí a nechybí ani řešení trojúhelníkových systémů nebo Choleského faktorizace. Tyto funkce mohou být snadno použity ke řešení systémů lineárních rovnic pomocí analytických nebo iterativních metod nebo k výpočtu vlastních čísel. Jsou zde popsány rychlé algoritmy pro hlavní procesor (CPU) i pro grafické akcelerátory (GPU).

Navrhované algoritmy jsou integrovány v knihovně SLAM++, jež řeší problém nelineárních nejmenších čtverců se zaměřením na problémy v robotice a počítačovém vidění. Je provedeno vyhodnocení na standardních datasetech kde navrhované metody dosahují výrazně lepších výsledků než dosavadní metody popsané v literatuře -- a to bez kompromisů v přesnosti či obecnosti řešení.

Rok
2017
Strany
1-241
Vydavatel
Ústav počítačové grafiky a multimédií FIT VUT v Brně
Místo
Brno, CZ
Soubory
Nahoru