Distributed asynchronous Cholesky decomposition

Abstract

The Cholesky decomposition represents a fundamental building block in order to solve several matrix-related problems, ranging from matrix inversion to determinant calculation, and it finds application in several contexts, e.g., in Unscented Kalman Filters or other least-square estimation problems. In this paper we develop a distributed algorithm for performing the Cholesky decomposition of a sparse matrix. We model a network of n agents as a connected undirected graph, and we consider a symmetric positive definite n × n matrix M with the same structure as the graph (i.e., except for the diagonal entries, nonzero coefficients mij are allowed only if there is a link between the i-th and the j-th agent). We develop an asynchronous and distributed algorithm to let each agent i calculate the nonzero coefficients in the i-th column of the Cholesky decomposition of M. With respect to the state of the art, the proposed algorithm does not require orchestrators and finds application in sparse networks with limited bandwidth and memory requirements at each node. © 2016 IEEE.