Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$?

Are there any families of Laplacians for which it takes almost linear time?

  • 5
    $\begingroup$ does linear time mean $O(n^2)$ or $O(m)$ ($m$ being the number of edges in the graph) ? $\endgroup$ Oct 30, 2011 at 21:45
  • 1
    $\begingroup$ I think $O(m)$ is more appropriate since -to the best of my understanding- $O(n^2)$ is the cost of a principal eigenvector for a "generic" $n\times n$ matrix. If we assumed O(n^2) to be linear I think that it would imply the answer "all Laplacians" to the second question. I am not sure though. $\endgroup$
    – Dimitris
    Oct 30, 2011 at 22:57
  • $\begingroup$ Are you interested in exact or approximate solutions? Btw, what is the reference for the O(n^2) solution you mention? For approximate solutions, there are the Lanczos/power methods that run in near-linear time (I think). $\endgroup$ Nov 4, 2011 at 19:27
  • $\begingroup$ Either exact or approximate within $\epsilon$ is fine. I think that the power method is $O(n^2)$ modulo the approximation error: ${\bf L}^i{\bf x}$ costs O(n^2) per iteration, and the number of iterations to approach the optimal solution within $\epsilon$ is a function of the two largest eigenvalues. I might be missing something. Do you have a references for the near-linear time? $\endgroup$
    – Dimitris
    Nov 4, 2011 at 23:28
  • $\begingroup$ A standard reference seems to be: "J. Kuczynski and H. Wozniakowski. Estimating the largest eigenvalues by the power and Lanczos algorithms with a random start. SIAM Journal on Matrix Analysis and Applications, 13:1094–1122, 1992." It obtains $1+\epsilon$ approximation in $O(1/\epsilon\cdot m\cdot \log n)$ time (essentially, note that an iteration of the power method runs in $O(m)$ time). The approximation means to find a vector $x$ s.t. $x^tLx\ge (1-\epsilon)\lambda_1\|x\|^2$. If the eigenvalues drop sufficiently rapidly, then one can get even better estimates. $\endgroup$ Nov 5, 2011 at 18:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.