Detail publikace
Accelerated Sparse Matrix Operations in Nonlinear Least Squares Solvers
Nelineární metoda nejmenších čtverců; numerické metody; řídké blokové matice; obecné výpočty na jednotkách grafických akcelerátorů.
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í.