U. A. Khan and J. M. F. Moura, "Distributed Iterate-Collapse Inversion (DICI) algorithm for L-banded matrices," in 33rd IEEE International Conference on Acoustics, Speech, and Signal Processing, Las Vegas, NV, Mar.-Apr. 2008, pp. 2529-2532.


In this paper, we present a distributed algorithm to invert $L-$banded matrices that are symmetric positive definite (SPD), when the submatrices in the band are distributed among several processing nodes. We provide a distributed iterate-collapse inversion (DICI) algorithm that converges, at each node, to the corresponding submatrices in the inverse of the $L-$banded matrix. The computational complexity of the DICI algorithm to invert an SPD $L-$banded $n\times n$ matrix can be shown at each node to be independent of the size, $n$, of the matrix. Local information exchange is carried out after each iteration to guarantee convergence. We apply this algorithm to invert the information matrices in a computationally efficient distributed implementation of the Kalman filter and show its application towards inverting arbitrary sparse SPD matrices.

Back to Publications