Efficient Cholesky Factor Recovery for Column Reordering in Simultaneous Localisation and Mapping

Description
Title: Efficient Cholesky Factor Recovery for Column Reordering in Simultaneous Localisation and Mapping
Authors: Touchette, Sebastien
Gueaieb, Wail
Lanteigne, Eric
Date: Apr-2016
Abstract: Simultaneous Localisation And Mapping problems are inherently dynamic and the structure of the graph representing them changes significantly over time. To obtain the least square solution of such systems efficiently, it is desired to maintain a good column ordering such that fill-ins are reduced. This comes at a cost since general ordering changes require the complete re-computation of the Cholesky factor. While some methods have obtained good results with reordering at loop closing, the changes are not guaranteed to be limited to the scope of the loop, leading to suboptimal performance. In this article, it is shown that the Cholesky factorisation of an updated matrix can be efficiently recovered from the previous factorisation if the permutations are localised. This is experimentally demonstrated on 2D SLAM datasets. A method is then provided to identify when such recovery is advantageous over the complete re-computation of the Cholesky factor. Furthermore, a hybrid algorithm combining factorisation recovery and re-computation of the Cholesky factor is proposed for dynamically evolving problems and tested on SLAM datasets. Steps where reordering occurs can be executed up to 67 % faster with the proposed method.
URL: http://dx.doi.org/10.1007/s10846-016-0367-7
http://hdl.handle.net/10393/34543
DOI: 10.1007/s10846-016-0367-7
CollectionScience informatique et génie électrique // Electrical Engineering and Computer Science
Files
camera-ready.pdfThe article2.33 MBAdobe PDFOpen