Pivoting Strategy for Fast LU decomposition of Sparse Block Matrices

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F17%3APU123021" target="_blank" >RIV/00216305:26230/17:PU123021 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.22360/SpringSim.2017.HPC.049" target="_blank" >https://doi.org/10.22360/SpringSim.2017.HPC.049</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.22360/SpringSim.2017.HPC.049" target="_blank" >10.22360/SpringSim.2017.HPC.049</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Pivoting Strategy for Fast LU decomposition of Sparse Block Matrices

Popis výsledku v původním jazyce

Solving large linear systems is a fundamental task in many interesting problems, including finite element methods (FEM) or (non-)linear least squares (NLS), among others. Furthermore, the problems of interest here are sparse: not all the vertices in a typical FEM mesh are connected, or similarly not all vertices in a graphical inference model are linked by observations, as is the case in e.g. simultaneous localization and mapping (SLAM) in robotics or bundle adjustment (BA) in computer vision. The two places where most of the time is spent in solving such problems are usually the sparse matrix assembly and solving the underlying linearized system. An interesting property of the above-mentioned problems is their block structure. It is given by the variables existing in a multi-dimensional space such as 2D, 3D or even se(3) and hence their respective derivatives being dense blocks of the corresponding dimension. In our previous work, we demonstrated the benefits of explicitly representing those blocks in the sparse matrix, namely reduced assembly time and increased efficiency of arithmetic operations. In this paper, we propose a novel implementation of sparse block LU decomposition and demonstrate its benefits on standard datasets. While not difficult to implement, the enabling feature is the pivoting strategy that makes the method numerically stable. The proposed algorithm is on average three times faster (over 50x faster in the best case), causes less fill-in and produces decompositions of comparable and often better precision than the conventional methods.

Název v anglickém jazyce

Pivoting Strategy for Fast LU decomposition of Sparse Block Matrices

Popis výsledku anglicky

Solving large linear systems is a fundamental task in many interesting problems, including finite element methods (FEM) or (non-)linear least squares (NLS), among others. Furthermore, the problems of interest here are sparse: not all the vertices in a typical FEM mesh are connected, or similarly not all vertices in a graphical inference model are linked by observations, as is the case in e.g. simultaneous localization and mapping (SLAM) in robotics or bundle adjustment (BA) in computer vision. The two places where most of the time is spent in solving such problems are usually the sparse matrix assembly and solving the underlying linearized system. An interesting property of the above-mentioned problems is their block structure. It is given by the variables existing in a multi-dimensional space such as 2D, 3D or even se(3) and hence their respective derivatives being dense blocks of the corresponding dimension. In our previous work, we demonstrated the benefits of explicitly representing those blocks in the sparse matrix, namely reduced assembly time and increased efficiency of arithmetic operations. In this paper, we propose a novel implementation of sparse block LU decomposition and demonstrate its benefits on standard datasets. While not difficult to implement, the enabling feature is the pivoting strategy that makes the method numerically stable. The proposed algorithm is on average three times faster (over 50x faster in the best case), causes less fill-in and produces decompositions of comparable and often better precision than the conventional methods.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/LQ1602" target="_blank" >LQ1602: IT4Innovations excellence in science</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 25th High Performance Computing Symposium

ISBN

978-1-5108-3822-2

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

1-12

Název nakladatele

Association for Computing Machinery

Místo vydání

Virginia Beach, VA

Místo konání akce

Virginia Beach, VA

Datum konání akce

23. 4. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—