  In this paper we provide nearly linear time algorithms for several problems
closely associated with the classic Perron-Frobenius theorem, including
computing Perron vectors, i.e. 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. The running times of our algorithms
improve upon previously known results which either depended polynomially on the
condition number of the problem, required quadratic time, or only applied to
special cases.
  We obtain these results by providing new iterative methods for reducing these
problems to solving linear systems in Row-Column Diagonally Dominant (RCDD)
matrices. Our methods are related to the classic shift-and-invert
preconditioning technique for eigenvector computation and constitute the first
alternative to the result in Cohen et al. (2016) for reducing stationary
distribution computation and solving directed Laplacian systems to solving RCDD
systems.
