Time complexity of dsyevr

[markusm73]

The developer documentation for the Intel math kernel library quite helpfully provides information on the approximate operation count for various LAPACK functions, which is apparently not available in the standard LAPACK documentation. E.g. for ?geqrf:

https://software.intel.com/en-us/mkl-developer-reference-fortran-geqrf

Unfortunately, it doesn't provide any time complexity estimates for ?syevr.

Does anybody have any details on, in particular, dsyevr? If available, I would also greatly appreciate a breakdown of the complexity for getting only a subrange of eigenpairs and/or the extra effort required for computing eigenvectors in addition to eigenvalues.

[Julien Langou]

For GEQRF, please check http://www.netlib.org/lapack/lawnspdf/lawn41.pdf appendix C.

For SYEVR, Cost is 4/3N^3 due to tridiagonalization step (SYTRF). Then this is O(N^2) per sought eigenvectors. But I do not know the constant in front of the O(N^2). I can ask around. Does it kind of go towards the type of answers you would seek? Is it worth that I ask around? (Once you are done with the tridiagbonalization step, eigenvalues are pretty much ``free``. This is O(N).)

Cheers,
Julien.

[markusm73]

I'm mostly just interested in the relative big-O cost associated with various modes of operation. To recap: the always required tridiagonalization step is O(N^3). The cost per eigenvalue is only O(N) so if I request K eigenvalues, it's O(K*N) (O(N^2) if all eigenvalues are requested). Constants aside, requesting eigenvectors is a lot more expensive than just getting the eigenvalues, with cost O(N^2) per eigenvector (O(N^3) if all are requested).

I guess the cost specific to the eigenvalue step is negligible for most problems. My only remaining question is: what range of cost ratios can be expected between the constants for tridiagonalization and computing all eigenvectors?

In a quick test, if I feed dsyevr a large identity matrix, eigenvector computation seems to be in roughly the same ballpark as tridiagonalization (maybe even cheaper). But if I pass it e.g. a Wilkinson matrix, which I've read may be problematic with MRRR, the eigenvector step takes maybe 2x longer than tridiagonalization. This only affects eigenvector computation btw., there doesn't seem to be any appreciable difference for eigenvalues (at least for identity vs Wilkinson).

Is a cost ratio of 2 for the "all eigenvectors" vs. tridiagonalization step about right as an upper bound?

[Julien Langou]

About right. Sure.

Well the computation of the eigenvectors and eigenvalues is trickier than the tridiagonalization. Tridiagonalization you perform 4/3N^3 Flops and you are done. You know what you will be doing before starting. Computing eigenvalues is an iterative process. So well, the algorithm converges quite well, but you never know. And then for the eigenvectors, you might need some re-orthogonalziation steps, and these are killing you. So this is really matrix dependent. (As you noted with your use of a Wilkinson matrix.)

The factor 2x as an upper bound depends on the matrix (cluster of eigenvalues, etc.), but also the size of the matrix. Some FLOPS are cheaper than others. When N increases the tridiagonalization might get more efficient, but reorthogonalization requires pass over matrices so that'll be bandwidth limited.

Well, all in all, I do not know. Factor 2x as an upper bound sounds about right indeed.

Cheers,
Julien.

[markusm73]

Thanks, that's all I wanted to know. I needed the information for implicit parallelism, whether a problem would be expensive enough to warrant running it in dedicated threads. Obviously, one cannot always know beforehand how well-behaved a matrix is, but at least I now have a rough idea how expensive the function might be given the problem parameters.

Cheers,
Markus