Institute of Information Science, Academia Sinica

We present a generalized subgraph preconditioning (GSP) technique to solve large-scale bundle adjustment problems efficiently. In contrast with previous work which uses either direct or iterative methods alone, GSP combines their advantages and is significantly faster on large datasets. The main idea is to identify a sub-problem (subgraph) that can be solved efficiently by sparse factorization methods and use its solution to build a preconditioner for the conjugate gradient method. In addition, GSP is more general and leads to more effective preconditioners. When applying the proposed method to the ``bal'' datasets, we observe that GSP shows promising performance.