why is cv::invert so incredibly slow?
hi,
why is cv::invert so incredibly slow? inverting a 465x465 matrix using svd takes 2minutes. without svd it still takes ~2sec
octave is much faster
i try to invert a 48984x465 matrix (SVD) and it takes a lot of time (it does not even completed yet) to invert. using octaves pinv finishes in <20sec;
calculating inv(R'*R)*R' in octave takes <10sec
in opencv (without SVD) it also took much more time than my patience allowed me to wait.
I use 2.4.1
has anyone a hint?
edit: the second test (inv(R'R)R') was done in debug. obviously it should finish in same time as the first one)
Edit2:
i did some tests with the 2.4.8 ocv version:
inverting 465 x 465 matrix without SVD took 0.5s
inverting 465 x 465 matrix with SVD took 5s
inverting 48984 x 465 matrix with SVD took 10min
inverting 48984 x 465 matrix without SVD (inv(R'R)R') took 18s (only measured the inv(R'*R) part)
indeed there is a speed up in later opencv versions.
octave timings:
tic; inv(rand(465,465)); toc -> Elapsed time is 0.0780001 seconds.
tic; pinv(rand(465,465)); toc -> Elapsed time is 1.232 seconds.
tic; pinv(rand(48984,465)); toc -> Elapsed time is 15.023 seconds.
R = rand(48984,465); tic;inv(R'*R);toc --> Elapsed time is 0.889 seconds.
In comparistion to octave that afaik also uses SVD to calculate pseudoinverses opencv implementation seems to be very slow. But also the normal inversion does not compare very well.
Lets start by moving on to 2.4.8 first. Maybe it was a bug and it is already fixed ... Then head back if problem persists.
And since you are using debug, please report correct speeds in release mode. The overhead for debug is gigantic, I never deploy or measure anything in debug mode ...
the first timings are release only the inv(R'R)R' calculation was done in debug. obviously the inv(R'R) should have the same timing as the fist one since it also has a 465x465 matrix to invert. only the timing of the matrix multiplication is added to the time. i added new timings from newer ocv version. i previously used the old one since it is the one we use in the current project so i did not wanted to become incompatible (also we used ocv with the IPP lib - dont know if this would have any influence). the new timings are with a new out of the box opencv
I know that this question is very old, but I arrived here when searching for a solution to a similar problem. In my case I wanted to invert an SPD matrix, and Cholesky factorization was good enough. I read the source code of Cholesky factorization in the library, and found that the main cause of the bad performances is reading memory locations in such a pattern that most of the reads are not cached. When solving this issue I got a performance boost of factor of almost 100 times faster. I use OpenCV version 2.4.13. I will be glad to provide more details if someone is interested.
@destructor If you want to share details you can post an issue or make a PR