Detail publikace

Pivoting Strategy for Fast LU decomposition of Sparse Block Matrices

POLOK Lukáš a SMRŽ Pavel. Pivoting Strategy for Fast LU decomposition of Sparse Block Matrices. In: Proceedings of the 25th High Performance Computing Symposium. Virginia Beach, VA: Association for Computing Machinery, 2017, s. 1-12. ISBN 978-1-5108-3822-2. Dostupné z: https://doi.org/10.22360/SpringSim.2017.HPC.049
Název česky
Pivoting Strategy foř Fast LU decomposition of Spařse Block Matrices
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Polok Lukáš, Ing. (UPGM FIT VUT)
Smrž Pavel, doc. RNDr., Ph.D. (UPGM FIT VUT)
URL
Abstrakt

Řešení velkých lineárních systémů je základní úloha při řešení mnoha zajímavých problémů, včetne metod konečných prvků (FEM), (ne-)lineárních nejmenších čtverců (NLS) a jiných. Problémy na něž se zaměřujeme jsou navíc řídké: ne všechny vrcholy v modelu grafické inference jsou propojeny pozorováními, jako například v problémech typu simultaneous localization and mapping (SLAM) v robotice nebo bundle adjustment (BA) v počítačovém vidění. Dvě místa kde se při řešení takovýchto problémů tráví nejvíc času jsou přitom sestavení řídké matice a řešení linearizovaného systému.

Zajímavou vlastností těchto metod je jejich bloková struktura. Ta je dána počtem dimenzí proměnných, které jsou často 2D, 3D nebo např. se(3) a tudíž jejich derivace jsou husté bloky příslušné velikosti. V naší předchozí práci jsme ukázali výhody explicitní reprezentace bloků v řídkých maticích, tedy zvýšenou propustnost aritmetických operací a rychlejší sestavení matice. V tomto článku navrhujeme novou implementaci řídké blokové LU dekompozice a demonstrujeme její výhody na standardních datasetech. Ačkoliv samotný algoritmus není složitý, klíčová část je strategie výběru pivotních prvků, jež udržuje metodu numericky stabilní. Navrhovaný algoritmus je průměrně třikrát rychlejší (v nejlepším případě více než 50x), produkuje řidší faktory a dosahuje stejné a často i lepší přesnosti než konkurenční metody.

Rok
2017
Strany
1-12
Sborník
Proceedings of the 25th High Performance Computing Symposium
Konference
25th High Performance Computing Symposium, Virginia Beach, VA, US
ISBN
978-1-5108-3822-2
Vydavatel
Association for Computing Machinery
Místo
Virginia Beach, VA, US
DOI
10.22360/SpringSim.2017.HPC.049
EID Scopus
2-s2.0-85020644896
BibTeX 
@INPROCEEDINGS{FITPUB11334,
   author = "Luk\'{a}\v{s} Polok and Pavel Smr\v{z}",
   title = "Pivoting Strategy for Fast LU decomposition of Sparse Block Matrices",
   pages = "1--12",
   booktitle = "Proceedings of the 25th High Performance Computing Symposium",
   year = 2017,
   location = "Virginia Beach, VA, US",
   publisher = "Association for Computing Machinery",
   ISBN = "978-1-5108-3822-2",
   doi = "10.22360/SpringSim.2017.HPC.049",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11334"
}
Soubory
Nahoru