Exploiting Locality by Nested Dissection For Square Root Smoothing and Mapping, Peter Krauthausen, Frank Dellaert, and Alexander Kipp, Robotics: Science and Systems, 2006

The computational complexity of SLAM is dominated by the cost of factorizing a matrix derived from the measurements into a square root form, which has cubic complexity in the worst case. However, the matrices associated with the full SLAM problem are typically very sparse, as opposed to the dense problems one obtains in a filtering context. Hence much faster, sparse factorization algorithms can be used. Furthermore, the cost can be further reduced by choosing a good order in which to eliminate variables during the factorization process, leading to more or less fill-in. In particular, in this paper we investigate how a nested dissection ordering method can provably improve the performance of the full SLAM algorithm. We show that the computational complexity for the factorization of a large class of measurement matrices occurring in the SLAM problem can be tightly bound under reasonable assumptions.