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.7 (R2008b)

Other Files

blendenpik/blendenpik.m,
blendenpik/blendenpik_over.m,
blendenpik/blendenpik_under.m,
blendenpik/blendenpik_under_alternative.m,
blendenpik/build_fftw_wisdom.c,
blendenpik/coherence.m,
blendenpik/configure_blenenpik.m,
blendenpik/dense_full_overdetermined_lsqr.c,
blendenpik/dense_full_overdetermined_lsqr.m,
blendenpik/dense_overdetermined_lsqr.c,
blendenpik/dense_overdetermined_lsqr.m,
blendenpik/dense_underdetermined_lsqr.c,
blendenpik/dense_underdetermined_lsqr.m,
blendenpik/fast_unitary_transform.c,
blendenpik/fast_unitary_transform.m,
blendenpik/fftw_r2r.c,
blendenpik/fftw_r2r.h,
blendenpik/install_blendenpik.m,
blendenpik/lapack_solve_ls.c,
blendenpik/lapack_solve_ls.m,
blendenpik/mex_dgeqrf.c,
blendenpik/mex_dgeqrf.m,
blendenpik/mex_dlange.c,
blendenpik/mex_dormqr.c,
blendenpik/mex_dtrcon.c,
blendenpik/mex_dtrsm.c,
blendenpik/mex_fftw_r2r.c,
blendenpik/random_sample_precond.m,
blendenpik/README.txt,
blendenpik/wtime.c,
blendenpik/wtime.m,
license.txt

[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