Signficant slow down of SVD in OpenCV 2.3 (Bug #1498)

While the problem can not be fixed completely, since we moved to our own SVD implementation, which is much faster on small matrices and generally more accurate on large matrices (at the expense of speed), there is possible workaround -

Since the covariation matrix is symmetrical, you can use cvEigenVV to decompose it to V*E*V' (where V is an orthogonal matrix of eigenvectors and E is a diagonal matrix of eigenvalues) and then pass the matrix V twice to cvSVBkSb (since U=V).

In the latest trunk version (r7098 and higher) you can simply call cvInvert() and pass CV_SVD_SYM flag there.

is it possible to supply the matrix on which the current SVD is 6 times slower? according to my experiments, new SVD is only a bit slower than Lapack on matrices of size <100x100. The specification of OS, compiler and flags you use is also appreciated. Until we have valid proof if the problem, which can not be solved easily, it's not a productive argument. I reopen the ticket for now.

Yes of course. I have attached the data file and two versions (2.2 and 2.4) of binary. By just clicking RunTest.bat, you can get the run time used for different versions of opencv.

I run this in more than 10 computers of my friends, and version 2.4 is about 6 times slower. We all use windows 7 and visual studio 2010. Specifically, my computer is ThinkPad T410 with i5 CPU. Here is the source code of this exe:

/***  Test speed of linear algebra functions in OpenCV ***/

#include <opencv/cv.h>
#include <cstdio>
#include <cstdarg>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cmath>
#include <cassert>
#include <ctime>

#ifdef _DEBUG
#pragma comment(lib, "opencv_core220d.lib")
#pragma comment(lib, "opencv_highgui220d.lib")
#else
#pragma comment(lib, "opencv_core220.lib")
#endif // _DEBUG

using namespace cv;
using namespace std;
void CovarMatrix (CvMat* CovMat, CvMat* FeatureVecs);

int main(int argc, char *argv[])
{
    bool debug = false;
    int FVLength = 64;    

    CvMat* avg = cvCreateMat(FVLength, 1, CV_64FC1);
    CvMat* FeatVec = cvCreateMat(FVLength, 1, CV_64FC1);
    CvMat* Anomaly = cvCreateMat(FVLength, 1, CV_64FC1);
    CvMat* Ki = cvCreateMat(FVLength, FVLength, CV_64FC1);
    CvMat* CovMat = cvCreateMat(FVLength, FVLength, CV_64FC1);
    cvSetZero(CovMat);
    CvMat* TotVecs = cvCreateMat(2,FVLength, CV_64FC1);

    // Initialize the FeatVec and avg to be random

    CvRNG rng_state = cvRNG(0xffffffff);
    cvRandArr(&rng_state, FeatVec, CV_RAND_NORMAL, cvRealScalar(100), cvRealScalar(30));
    cvRandArr(&rng_state, avg, CV_RAND_NORMAL, cvRealScalar(60), cvRealScalar(25));

    // Start time
    clock_t start = ::clock();
    unsigned int it = 2000;
    for (int p = 0; p < it; p++)  {
        cvSub(FeatVec, avg, Anomaly);            // Find anomaly vector (feature-average)
        for (int k=0; k < FVLength; k++) //Ki is now going to be inverse covariance matrix
        {
            cvmSet(TotVecs,0,k,cvmGet(FeatVec,k,0));
            cvmSet(TotVecs,1,k,cvmGet(avg,k,0));
        }

        // Next, find the covariance matrix of this.
        CovarMatrix(CovMat, TotVecs);
        cvInvert(CovMat, Ki, CV_SVD);  

        if (p == 0){
            CvFileStorage *fs = cvOpenFileStorage("data.xml", NULL, CV_STORAGE_WRITE);
            cvWrite(fs, "CovMat", CovMat);
        }
    }

    clock_t endT = clock();
    cout<<"Time elapsed : "<< (double(endT - start))/CLOCKS_PER_SEC <<endl;

    return 0;
}

void CovarMatrix (CvMat* CovMat, CvMat* Vecs)
{
    int nums = Vecs->cols;        
    int Len = Vecs->rows;        
    int n       = Vecs->cols;        // step size     
    double *data = Vecs->data.db;    // pointer to float with all values in input
    double sum;    

    for (int j = 0; j < nums ; j++) {
        sum = 0;
        for (int i = 0; i < Len; i ++)
            sum += data[i * n + j];
        sum = sum/Len;

        for (int i =0; i < Len; i++)
            data[i * n + j] -= sum;
    }

    CvMat* VecsT = cvCreateMat(nums, Len, CV_64FC1);        // covariance matrix
    cvTranspose( Vecs,VecsT );        
    cvMulTransposed( VecsT, CovMat, 0);            
    //  scale CovMat by m-1
    double *CovDat = CovMat->data.db;            // pointer to float with all values in input
    for (int i = 0; i < CovMat->rows; i++)        // for each feature vector, find the mean, and subtract it 
        for (int j = 0; j < CovMat->cols; j ++)
            CovDat[i * (CovMat->cols) + j] = CovDat[i * (CovMat->cols) + j] / (Len-1);
    cvReleaseMat(&VecsT);
}

Vadim Pisarevsky wrote:

is it possible to supply the matrix on which the current SVD is 6 times slower? according to my experiments, new SVD is only a bit slower than Lapack on matrices of size <100x100. The specification of OS, compiler and flags you use is also appreciated. Until we have valid proof if the problem, which can not be solved easily, it's not a productive argument. I reopen the ticket for now.

ok; the problem has been reproduced; we will try to solve it soon

Dear community, could somebody work take this issue? Core OpenCV devs are busy with release preparations, so if we want to see this issue fixed, we need a volunteer!