Time complexity of dsyevr

Open discussion regarding features, bugs, issues, vendors, etc.

Time complexity of dsyevr

Postby markusm73 » Fri Dec 15, 2017 6:48 pm

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.
markusm73
 
Posts: 17
Joined: Tue Jun 14, 2005 8:10 pm
Location: New York

Re: Time complexity of dsyevr

Postby Julien Langou » Fri Dec 15, 2017 11:23 pm

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.
Julien Langou
 
Posts: 828
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

Re: Time complexity of dsyevr

Postby markusm73 » Sat Dec 16, 2017 1:01 am

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?
markusm73
 
Posts: 17
Joined: Tue Jun 14, 2005 8:10 pm
Location: New York

Re: Time complexity of dsyevr

Postby Julien Langou » Sat Dec 16, 2017 4:34 pm

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.
Julien Langou
 
Posts: 828
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

Re: Time complexity of dsyevr

Postby markusm73 » Sat Dec 16, 2017 4:46 pm

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
markusm73
 
Posts: 17
Joined: Tue Jun 14, 2005 8:10 pm
Location: New York


Return to User Discussion

Who is online

Users browsing this forum: No registered users and 1 guest

cron