Methods and apparatuses for solving graph Laplacians

摘要

Methods and apparatuses for solving a system on a symmetric diagonally dominant matrix. The method includes constructing an equivalent symmetric diagonally dominant linear system Ax=b from the system on a symmetric diagonally dominant matrix, wherein the matrix A of the equivalent linear system Ax=b has negative off-diagonal entries and zero row sums; constructing a graph of the matrix A of the equivalent linear system; constructing a decomposition of the graph; constructing a two-level process using the decomposition of the graph, wherein the two-level process includes reducing the equivalent linear system Ax=b to a linear system By=c; and extending the two-level process to a multi-level process having more than two levels.