Článek ve sborníku konference

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
Jazyk publikace:angličtina
Název publikace:Pivoting Strategy for Fast LU decomposition of Sparse Block Matrices
Název (cs):Pivoting Strategy foř Fast LU decomposition of Spařse Block Matrices
Strany:1-12
Sborník:Proceedings of the 25th High Performance Computing Symposium
Konference:25th High Performance Computing Symposium
Místo vydání:Virginia Beach, VA, US
Rok:2017
URL:https://doi.org/10.22360/SpringSim.2017.HPC.049
ISBN:978-1-5108-3822-2
DOI:10.22360/SpringSim.2017.HPC.049
Vydavatel:Association for Computing Machinery
Soubory: 
+Typ Jméno +Název Vel. Poslední změna
iconscs17paper.pdf521 KB2017-02-15 14:10:13
^ Vybrat vše
S vybranými:
Klíčová slova
LU decomposition, sparse matrix, block matrix, register blocking, direct methods.
Anotace
Ř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.
BibTeX:
@INPROCEEDINGS{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=11334}
}

Vaše IPv4 adresa: 54.145.45.143