CWYAlpha

Just another WordPress.com site

Thought this was cool: OpenCV vs. Armadillo vs. Eigen vs. more! Round 3: pseudoinverse test

Okay, the title of this post is getting longer and sillier, but this is the 3rd continuation of my last two post on comparing different libraries for everyday matrix operations. The last two posts compared basic operations such as multiplication, transposition, inversion etc. etc. in isolation, which is probably not a good reflection of real life usage. So I decided to come up with a new test that would combine different matrix operations together. I chose the pseudoinverse because it is something I use every now and then and it combines multiplication, transposition and inversion, which seems like a good test.

For benchmarking I’m going to be solving the following over determined linear system:

$AX = B$

and solve for X using

$X = \left(A^TA\right)^{-1}A^{T}B$

A is a NxM matrix, where N is much larger than M. I’ll be using N=1,000,000 data points and M (dimensions of the data) varying from 2 to 16.

B is a Nx1 matrix.

The matrix values will be randomly generated from 0 to 1 with uniform noise of [-1,1] added to B. They values are kept to a small range to avoid any significant numerical problems that can come about doing the pseudoinverse this way, not that I care too much for this benchmark. Each test is performed for 10 iterations, but not averaged out since I’m not interested in absolute time but relative to the other libraries.

Just to make the benchmark more interesting I’ve added GSL and OpenBLAS to the test, since they were just an apt-get away on Ubuntu.

Results

The following libraries were used

• OpenCV 2.4.3 (compiled from source)
• Eigen 3.1.2 (C++ headers from website)
• Armadillo 3.4.4 (compiled from source)
• GSL 1.15 (Ubuntu 12.10 package)
• OpenBLAS 1.13 (Ubuntu 12.10 package)
• Atlas 3.8.4 (Ubuntu 12.10 package)

My laptop has an Intel i7 1.60GHz with 6GB of RAM.

All values reported are in milliseconds. Each psuedoinverse test is performed 10 times but NOT averaged out. Lower is better.

 library/data dimensions 2 3 4 5 6 7 8 9 OpenCV 275.954 503.168 524.701 978.336 1385.46 1885.44 1883.16 2531.94 Eigen 368.439 648.308 789.151 1089.96 1254.04 1513.19 1761.05 1993.96 Armadillo + Atlas 98.243 166.575 246.166 358.861 546.694 635.13 851.304 1102.35 Armadillo + OpenBLAS 76.147 117.065 130.439 269.368 322.245 434.151 376.652 421.379 GSL 594.091 980.898 1520.06 2146.78 2757.59 3231.15 4135.9 5256.05
 10 11 12 13 14 15 16 OpenCV 3191.09 4064.59 4402.34 5085.36 5810.52 6576.29 6641.42 Eigen 2332.62 2664.57 2563.89 3223.94 3299.76 4035.65 4066.95 Armadillo + Atlas 1197.52 1463.56 1569.91 1827.96 1181.59 1420.41 1661.6 Armadillo + OpenBLAS 469.763 492.199 561.044 610.661 629.2 741.123 729.042 GSL 6643 7288.27 8432.9 9336.24 9980.36 11822.6 13114

Ranking from best to worse

3. Eigen
4. OpenCV
5. GSL

All I can say is, holly smokes Batman! Armadillo + OpenBLAS wins out for every single dimension! And the difference is quite significant. The second runner up is Armadillo with Atlas. Third/fourth place is interesting because OpenCV is only slightly faster for smaller dimensions compared to Eigen, after which Eigen constantly remains faster. Last is GSL, okay no surprise there for me. It never boasted being the fastest car on the track.

OpenBLAS is based on GotoBLAS and is actually a ‘made in China’ product, except this time I don’t get to make any jokes about the quality. It is very fast. In this test it’s around 2x faster than Atlas.

I’m rather sad OpenCV is not that fast since I use it heavily for computer vision tasks. My compiled version actually uses Eigen, but that doesn’t explain why it’s slower than Eigen! Back in the old days OpenCV used to use BLAS/LAPACK, something they might need to consider bringing back.

Code

test_matrix_pseudoinverse.cpp (right click save as)

Edit the code to #define in the libraries you want to test. Make sure you don’t turn on Armadillo + GSL, because they have conflicting enums. Instructions for compiling is at the top of the cpp file, but here it is again for reference.

To compile using ATLAS:

g++ test_matrix_pseudoinverse.cpp -o test_matrix_pseudoinverse -L/usr/lib/atlas-base -L/usr/lib/openblas-base -lopencv_core -larmadillo -lgomp -fopenmp -lcblas -llapack_atlas -lgsl -lgslcblas -march=native -O3 -DARMA_NO_DEBUG -DNDEBUG -DHAVE_INLINE -DGSL_RANGE_CHECK_OFF

To compile with OpenBLAS:

g++ test_matrix_pseudoinverse.cpp -o test_matrix_pseudoinverse -L/usr/lib/atlas-base -L/usr/lib/openblas-base -lopencv_core -larmadillo -lgomp -fopenmp -lopenblas -llapack_atlas -lgsl -lgslcblas -march=native -O3 -DARMA_NO_DEBUG -DNDEBUG -DHAVE_INLINE -DGSL_RANGE_CHECK_OFF

from Nghia Ho: http://nghiaho.com/?p=1726