Speed of Matrix-Multiplication (in Matlab, C, other PCs)

I'm working on an object detection algorithm ( HOG ). Their (paper-guys) tool is written in C and needs "less than a second [for] 4000 detection windows".

I use Matlab. After optimizing my code for speed, the biggest 'time sink' (80% cpu time) is a matrix-multiplication (it is the linear kernel of a SVM classification). I striped it down to:

nF = 3780; % number of features
nV = 3120; % number of support vectors
V = rand(nV,nF); % support vectors

N = 5000;
S = rand(N,nF);

tic
K =  V * S'; % Elapsed time is ~2 seconds.
toc

The matrix-multiplication takes 2sec (where the paperguys do it in 1sec). I tried mex'ing it, but that takes 35% longer. I tried parallel computing with splitting S, but also took much longer.

Now my questions are about explanation and understanding this: How much faster is a matrix multiplication like this in C? How much influence has the PC spec? I guess it is impossible to speedup a matrix multiplication in Matlab?

Answer 1

[James Tursa]

MATLAB uses a very fast and highly optimized BLAS library to do matrix multiplication. You are unlikely to find anything faster than simply doing V * S' as you currently are because this calls the BLAS library routine in the background (the parser will pass the transpose info to the BLAS routine without actually forming S' explicitly first). And part of the optimization is multi-threading, so you are already getting that benefit simply by using the * operator. The fastest way to do matrix multiplication in C for the sizes you are using is to call this BLAS library (same thing MATLAB is already doing).

What do you mean "the paperguys do it in 1sec"? You have a program that is doing the same size matrix multiply in 1 sec on the exact same computer? Are you sure they are doing the same matrix multiply? What computer are you using? Don't use the first MATLAB timing you do because that time includes the time to load the function. Do a couple more tests and then see what you get for timing.

[James Tursa]

I am including C-solutions in my "unlikely to find anything" statement. It is extremely unlikely you will be able to find any C code or write any C code that you can compile that will beat the BLAS library routine for speed (for the sizes you are using). The only thing that might beat it is another BLAS library written by a different company that has better optimizations in it than the one that MATLAB uses (MATLAB uses a 3rd party BLAS library ... they don't write this code themselves).

[James Tursa]

I am also assuming that there are no subscripting issues involved. I.e., you wrote this:

K =  V * S'

But if you are really doing something like this in a loop:

K(:,:,i) =  V(:,:,i) * S(:,:,i)'

Then the answer can be different, because the subscripting causes data copies that can chew up time, and these data copies can sometimes be avoided in a mex routine.

[yosey]

Thank you very much! Your answers really help me, because I can exclude alot of explanations.

All I've is their quote from the paper: "Although our current linear SVM detector is reasonably efficient – processing a 320×240 scale-space image (4000 detection windows) in less than a second ..."

This means N=4000 in my code (takes me 1.6 sec). The 1sec is with their programm (I dont ve it), on their PC. I use my laptop, so they might ve a much better PC.

-> Do you think you accelerate from 1.6sec to 1sec with a faster PC?

Are you sure they are doing the same matrix multiply? 98% yes

[yosey]

no subscripting issues involved

[Steven Lord]

Double precision or single precision?

[yosey]

"Double precision or single precision?" - This is a great hint, thank you. So far I'm doing everything in double, while using single makes it nearly twice as fast.

I think thats it. Particularly its so basic, I should not have missed it ... but im still happy, thank you sir.