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?
11
$\begingroup$
$\endgroup$
-
5$\begingroup$ does linear time mean $O(n^2)$ or $O(m)$ ($m$ being the number of edges in the graph) ? $\endgroup$ – Suresh Venkat Oct 30 '11 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 '11 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$ – Alex Andoni Nov 4 '11 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 '11 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$ – Alex Andoni Nov 5 '11 at 18:32
