Duality and nonlinear graph Laplacians

Specifically, we present an iterative algorithm for solving a class of nonlinear system of equations arising from a nonlinear generalization of the graph Laplacian in O˜(k2mlog⁡(kn/ϵ)) iterations, where k is a measure of nonlinearity, n is the number of variables, m is the number of nonzero entries in the generalized graph Laplacian L, ϵ is the solution accuracy and O˜() neglects (non-leading) logarithmic terms. This algorithm is a natural nonlinear extension of the one in Kelner et al. (2013), which solves a linear Laplacian system of equations in nearly linear time. Unlike the linear case, in the nonlinear case each iteration takes O˜(n) time so the total running time is O˜(k2mnlog⁡(kn/ϵ)). For sparse graphs with m=O(n) and fixed k this nonlinear algorithm is O˜(n2log⁡(n/ϵ)) which is slightly faster than standard methods for solving linear equations, which require approximately O(n2.38) time.