Abstract
In this paper, we provide nearly linear time algorithms for several problems closely associated with the classic Perron-Frobenius theorem, including computing Perron vectors—entrywise non-negative eigenvectors of non-negative matrices—and solving linear systems in asymmetric M-matrices, a generalization of Laplacian systems. The running times of our algorithms depend nearly linearly on the input size and polylogarithmically on the desired accuracy and problem condition number. Leveraging these results, we also provide improved running times for a broader range of problems, including computing random walk-based graph kernels, computing Katz centrality, and more. Our methods improve upon previously known results which either depended polynomially on the condition number, required quadratic time, or only applied to special cases. We achieve this by providing new iterative methods for reducing these problems to solving linear systems in Row-Column Diagonally Dominant (RCDD) matrices.
Introduction
The Perron-Frobenius theorem is a pillar of linear algebra, stating that any non-negative square matrix has a unique largest real eigenvalue with a corresponding eigenvector whose entries are all positive. This "Perron vector" is essential for understanding Markov chains, ranking web pages (e.g., PageRank), and analyzing social networks. Despite its importance, computing this vector or solving linear systems for related "M-matrices" (a generalization of graph Laplacians) has historically been computationally expensive. Previous algorithms typically required quadratic time ($O(n^2)$) or had runtimes that scaled poorly with the "condition number"—a measure of numerical instability. This research bridges that gap, providing algorithms that run in time nearly proportional to the number of non-zero entries in the matrix ($m$), with only a logarithmic dependence on accuracy and stability.
The Computational Challenge
The primary difficulty in solving M-matrix systems or finding Perron vectors lies in their potential asymmetry and numerical instability. While symmetric systems (like undirected graph Laplacians) have seen significant algorithmic breakthroughs in recent years, asymmetric systems have remained more elusive. The authors identify a "chicken and egg" problem: to solve an M-matrix system efficiently, one ideally needs the Perron vector to scale the matrix into a Row-Column Diagonally Dominant (RCDD) form; however, to find the Perron vector, one often needs to solve M-matrix systems.
Algorithmic Framework: Reduction to RCDD
The core of the proposed solution is a reduction to RCDD systems. RCDD matrices are a class of matrices that can already be solved in nearly linear time. To break the circular dependency between scaling and solving, the authors introduce a novel iterative framework:
- Shift-and-Invert Preconditioning: The algorithm considers a "shifted" version of the matrix ($M + \alpha I$). When the shift $\alpha$ is very large, the matrix is easily solvable.
- The Scaling Loop: Starting with a large $\alpha$, the algorithm finds a scaling. It then repeatedly halves $\alpha$, using the solution from the previous step as a "preconditioner" to solve the next, more difficult step.
- MMatrix-Decide: A decision procedure is developed that can either certify a matrix is an M-matrix by finding its scaling or provide a proof that it is not.
- Doubling Scheme: Since the condition number is often unknown, the algorithm uses a doubling strategy—starting with a small guess for the difficulty and doubling it until the algorithm succeeds.
Key Insights
- Scaling as a Primitive: The core insight is that every invertible M-matrix is essentially an RCDD matrix in disguise. Finding the right diagonal scaling (using the left and right Perron vectors) makes the problem tractable.
- Multiplicative Closeness: The authors prove that if an M-matrix is shifted by two different values of $\alpha$ that are close to each other, the inverse of one serves as an excellent approximation (preconditioner) for the other. This justifies the iterative halving approach.
- Approximation Sufficiency: By showing that only approximate Perron vectors are required to achieve RCDD-ness, the algorithm can converge without needing the exact answer upfront.
Applications and Results
This theoretical breakthrough leads to several improved runtimes across various domains:
- Perron Vector Computation: The first algorithm to compute the top eigenvector of a non-negative irreducible matrix in $\tilde{O}(m)$ time.
- M-Matrix Solver: A nearly linear time solver for systems of the form $(sI - A)x = b$, where $A$ is non-negative.
- Katz Centrality: Improved runtime for computing this social network influence measure, which was previously difficult to scale for large graphs.
- Graph Kernels: Faster computation of "random walk kernels," used to measure similarity between graphs in bioinformatics and natural language processing.
- Leontief Economies: A faster method for checking the "Hawkins-Simons condition," determining if an economic model can meet demand.
Conclusion
While the "nearly linear" complexity is a major theoretical milestone, the authors note that the polylogarithmic factors and hidden constants may be large, suggesting a need for further optimization for practical implementation. However, by extending tools developed for symmetric graph Laplacians to the broader world of asymmetric M-matrices, this work provides new linear algebraic primitives that could revolutionize combinatorial problems on directed graphs.
Summary updated