Re: [eigen] Fast tall QR for least squares |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen <eigen@xxxxxxxxxxxxxxxxxxx>*Subject*: Re: [eigen] Fast tall QR for least squares*From*: Sameer Agarwal <sameeragarwal@xxxxxxxxxx>*Date*: Sun, 24 Feb 2013 10:16:50 -0800*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:x-received:in-reply-to:references:date:message-id :subject:from:to:content-type; bh=ObX9zP4IQneoZT17XBxrRc1a0C4GRnliCv2FabTcjxo=; b=QYeUq6aqYEV8ojuD1aW9nlbzSPATO1FM7tTsi1FfJn8QYP4998VlNBJ1cqqlSIUXug rvbYAcMTUOFeViHQ3E70sW9jITEBlkh7Aw16wg6K1mIfhn6AK6Bz/x14/Nli+hjlEuxN A9P4hF59v66vxfGdd8VsQxSC3UMHl64qX3xPvHAVIIFUwnnnpS7L1/J7z8fH2wT3Re1c XO1a0JNVeNxZu63EHV5zMlpoQnxJ5LhB8IVEfmwmzUvvQN8K/2tjljnMzR4gfD7mruJM l1mvijjoZsHuHDMmR6xjrhilfWLwUOrIaAPbKEd4IlBWPdUomZoGrW1tJmYojdm32rPt pW1A==

This seems to be aimed at shared memory computations, our matrices are not that large.

Sameer

On Sun, Feb 24, 2013 at 9:40 AM, Désiré NUENTSA WAKAM <desire.nuentsa_wakam@xxxxxxxx> wrote:

Hi,

A good candidate is the TSQR (tall-skinny QR) by Demmel et al. : http://digitalassets.lib.berkeley.edu/techreports/ucb/text/EECS-2008-74.pdf

An implementation for shared-memory with Intel TBB is available in Trilinos : https://cfwebprod.sandia.gov/cfdocs/CCIM/docs/tsqr.pdf

Désiré

Le 24/02/2013 15:39, Gael Guennebaud a écrit :

Hi,

the best would be to "blockify" ColPivHouseholderQR on our side....

In the meantime, one option might be to start with HouseholderQR

(which should be an order of magnitude faster) and fallback to column

pivoting only when needed, i.e., when two columns are (nearly)

linearly dependent. I think that this situation can be detected from

the diagonal entries of the resulting R factor, namely:

if(qr.matrixQR().diagonal().maxCoeff() *

NumTraits<Scalar>::dummy_precision() >

qr.matrixQR().diagonal().minCoeff())

{

// fallback to ColPivHouseholderQR

}

cheers,

Gael.

On Sun, Feb 24, 2013 at 12:03 AM, Keir Mierle <mierle@xxxxxxxxx> wrote:

Currently Ceres runs a QR decomposition for dense nonlinear solving in the

heart of the Levenberg-Marquardt loop is as follows:

VectorRef(x, num_cols) = A->matrix().colPivHouseholderQr().solve(rhs_);

This is the performance limiting step in Ceres for dense problems. The A

matrix tends to be very tall and not especially wide; in other words, it is

an overdetermined system. You might ask why not use Cholesky, and the answer

is that forming the A'A matrix is sufficiently expensive to make running

Cholesky slower than QR.

Any ideas on how to make this solve faster than it is currently?

Thanks!

Keir

**References**:**[eigen] Fast tall QR for least squares***From:*Keir Mierle

**Re: [eigen] Fast tall QR for least squares***From:*Gael Guennebaud

**Re: [eigen] Fast tall QR for least squares***From:*Désiré NUENTSA WAKAM

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Fast tall QR for least squares** - Next by Date:
**Re: [eigen] Eigen 3.2-beta1 ??** - Previous by thread:
**Re: [eigen] Fast tall QR for least squares** - Next by thread:
**[eigen] problem computing kernel in eigen**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |