Content deleted Content added
→Costs: extended to cover the case of dense adjacency matrices |
→Computing eigenvectors: minor |
||
Line 69:
===Computing eigenvectors===
The cost of computing the <math>n</math>-by-<math>k</math> (with <math>k<<n</math>) matrix of selected eigenvectors of the graph Laplacian is normally proportional to the cost of multiplication of the <math>n</math>-by-<math>n</math> graph Laplacian matrix by a vector, which varies greatly whether the graph Laplacian matrix is dense or sparse. For the dense case the cost thus is <math>O(n^2)</math>. The very commonly cited in the literature cost <math>O(n^3)</math> comes from choosing <math>k=n</math> and is clearly misleading, since, e.g., in a hierarchical spectral clustering <math>k=1</math> as determined by the [[Fiedler vector]].
==Software==
|