Conference paperPOLOK Lukáš and 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, pp. 112. ISBN 9781510838222. Available from: https://doi.org/10.22360/SpringSim.2017.HPC.049  Publication language:  english 

Original title:  Pivoting Strategy for Fast LU decomposition of Sparse Block Matrices 

Title (cs):  Pivoting Strategy foř Fast LU decomposition of Spařse Block Matrices 

Pages:  112 

Proceedings:  Proceedings of the 25th High Performance Computing Symposium 

Conference:  25th High Performance Computing Symposium 

Place:  Virginia Beach, VA, US 

Year:  2017 

URL:  https://doi.org/10.22360/SpringSim.2017.HPC.049 

ISBN:  9781510838222 

DOI:  10.22360/SpringSim.2017.HPC.049 

Publisher:  Association for Computing Machinery 

Files:  

 Keywords 

LU decomposition, sparse matrix, block matrix, register blocking, direct methods. 
Annotation 

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 abovementioned problems is their block structure. It is given by the variables existing in a multidimensional 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 fillin and produces decompositions of comparable and often better precision than the conventional methods. 
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 = {112},
booktitle = {Proceedings of the 25th High Performance Computing Symposium},
year = {2017},
location = {Virginia Beach, VA, US},
publisher = {Association for Computing Machinery},
ISBN = {9781510838222},
doi = {10.22360/SpringSim.2017.HPC.049},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=11334}
} 
