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