The High Relative Accuracy of Computations with Laplacian Matrices

Abstract

This paper provides an efficient method to compute an LDU decomposition of the Laplacian matrix of a connected graph with high relative accuracy. Several applications of this method are presented. In particular, it can be applied to efficiently compute the eigenvalues of the mentioned Laplacian matrix. Moreover, the method can be extended to graphs with weighted edges.

Keywords

• high relative accuracy
• Laplacian matrix
• eigenvalues