Blendenpik

A fast solver of dense rectangular dense linear equations . (least squares or underdetermined).

Description

This library implements a randomized algorithm for solving the least-squares equation x = arg min norm(A * x - b, 2) or the underdetermined system min(norm(x, 2)) s.t. Ax=b. With high probability the running this o(mn^2) for an m-by-n matrix.

For details of the solver see the paper at:
Blendenpik: Supercharging LAPACK's least-squares solver.
Authors: Haim Avron, Petar Maymounkov, and Sivan Toledo.

To build FFTW and/or SPIRAL WHT is needed. Extract the files and write install_blendenpik.

• MATLAB release: MATLAB 7.9 (2009b)

[Ben Petschel]

Can you post the results of benchmarking against "\" please?

[Ben Petschel]

This is potentially a novel and useful algorithm but I couldn't get it to install because it seems to require a separate installation of FFTW C libraries, even though FFTW already comes with MATLAB and is used by the built-in version of FFT.

Also there is no mention of how the results compare in accuracy and speed against the built-in solves least-squares "\", so why go to the trouble of getting it to work?

[Haim Avron]

For benchmarking results take a look at:
http://www.cs.tau.ac.il/~haima/blendenpik-v0.pdf
This paper has extensive benchmarking vs. LAPACK (which MATLAB uses). For some quick figures, on a random 20000x1000 matrix MATLAB's \ takes 27 sec, calling LAPACK directly (in compiled function lapack_solve_ls) takes 12.2, and blendenpik takes 7.8 secs. For some matrices blendenpik is 4 times faster than LAPACK.

As for the use of FFTW: Blendenpik uses DHT and DCT, not FFT. FFTW supports DHT and DCT but MATLAB's implementation of DCT doesn't use FFTW.

[Ben Petschel]

Nice work

[Susan]

I built this library using Matlab r2009a and tried running it on a 64-bit linux computer with 32 Gb of RAM. I have fftw v3.2.2 installed. The 'Install_blendenpik" script ran and completed with any errors. However when I run the example:
>> A = rand(40000, 1000);
>> b = rand(40000, 1);
>> x = blendenpik(A, b);

I get the following errors:
x=blendenpik(A,B);
Random unit diagonal + unitary transformation time: 0.17 sec
Random sampling time: 0.00 sec
??? Error using ==> mex_dgeqrf
Out of memory. Type HELP MEMORY for your options.

Error in ==> random_sample_precond at 88
    R = mex_dgeqrf(R);

Error in ==> blendenpik_over at 79
[R, flag, timing.precond_timing] = random_sample_precond(A, params);

Error in ==> blendenpik at 40
    x = blendenpik_over(A, b, params);
 
And in my terminal window I get the following error:
 MKL ERROR : Parameter 7 was incorrect on entry to DGEQRF

I also tried running the same commands with smaller matrices but still get the out of memory errors. Am I using the right versions of matlab and fftw? Do you have any idea why I am getting this error?

[Haim Avron]

It looks like there is a problem when you use it with MKL.
Let me check that out.

[Haim Avron]

I have fixed a problem with 64-bit MATLAB 2009b and uploaded a new version.

[Xiangrui Meng]

I have 64-bit MATLAB 2009b and fftw3 installed. It seems that install_blendenpik will use the fftw3 library that comes with MATLAB but not the libfftw3.a inside /usr/lib, which gives segmentation fault in my case.