[eigen] Blocked QR with column pivoting.

[Rasmus Larsen]

It would be great to have an implementation of the LAPACK algorithm in
xGEQP3 in Eigen. In the table here:

http://eigen.tuxfamily.org/dox/group__TopicLinearAlgebraDecompositions.html

there is a "teaser" saying that ColPivHouseholderQR will soon be blocked.
Is somebody actually working on this, and is so, what's the timeline?

Rasmus

[Gael Guennebaud]

This is a very long time wanted feature. Sadly, nobody started to work on
it yet. Retrospectively, this "soon" was really optimistic. A tile-based
implementation would be even better (better multi-threading), and
completing this class with complete orthogonalization for minimal norm
solving would be a nice bonus too.

Any volunteer? or sponsorship?

gael

Post by Rasmus Larsen
It would be great to have an implementation of the LAPACK algorithm in
http://eigen.tuxfamily.org/dox/group__TopicLinearAlgebraDecompositions.html
there is a "teaser" saying that ColPivHouseholderQR will soon be blocked.
Is somebody actually working on this, and is so, what's the timeline?
Rasmus

[Mark Sauder]

​Hello Eigen,

On the heels of the last comment, I wanted to (cautiously) offer a
thought... if there were a "Donate" button on the Eigen home page I would
click it today.

Donations could be used to sponsor a traveling university fellowship or
student stipend for dedicating work on Eigen bugs and features. This might
help make the 'sponsorship​' comment very easy for the individual as well
as organizations to contribute toward. Managed by the core development
team/administrators, a sponsored position could accelerate/focus work as
administrators see best. For individuals like myself who use Eigen heavily
but have not made meaningful contributions to the code base, this could be
an avenue we could help support.

I sincerely apologize if suggesting this is in any manner poor taste; it is
not my intention to offend. I can appreciate the downsides to proposing
any kind of financial aspect to the Eigen ecosystem.

​Respectfully,
​
​Mark

Post by Gael Guennebaud
This is a very long time wanted feature. Sadly, nobody started to work on
it yet. Retrospectively, this "soon" was really optimistic. A tile-based
implementation would be even better (better multi-threading), and
completing this class with complete orthogonalization for minimal norm
solving would be a nice bonus too.
Any volunteer? or sponsorship?
gael

Post by Rasmus Larsen
It would be great to have an implementation of the LAPACK algorithm in
http://eigen.tuxfamily.org/dox/group__TopicLinearAlgebraDecompositions.html
there is a "teaser" saying that ColPivHouseholderQR will soon be blocked.
Is somebody actually working on this, and is so, what's the timeline?
Rasmus

[Christian Keck]

In my software I have Eigen dense and sparse matrices and vectors that
are temporarily invalid. How can I signal that these matrix and vectors
are invalid without using extra variables?

Is it possible to set the size of a matrix oder vector to zero? How can
the elements of a vector set to a NaN? My compiler (Microsoft Visual C++
2013) does not yet support assignments with signalling NaNs.

Thank you, Christian
--
Dipl.-Ing. Christian Keck
Institut für Produktionsmesstechnik
Technische Universität Braunschweig
Schleinitzstraße 20
D-38106 Braunschweig
Telefon: [phone]
Telefax: [phone]

Mail: mailto://***@tu-braunschweig.de
Internet: http://www.iprom.tu-braunschweig.de

[Christoph Hertzberg]

Post by Christian Keck
Is it possible to set the size of a matrix oder vector to zero? How can
the elements of a vector set to a NaN? My compiler (Microsoft Visual C++
2013) does not yet support assignments with signalling NaNs.

You can resize matrices/vectors to 0 using the resize method:
vector.resize(0);
matrix.resize(0,0);
However, this does not work for fixed-sized matrices/vectors, i.e.,
Matrix2d, Vector3f, etc.
You can also set a matrix/vector to NaN, e.g. by:
matrix.setConstant(0.0/0.0);
and check using
bool invalid = matrix.hasNaN();

Christoph
--
Dipl. Inf., Dipl. Math. Christoph Hertzberg

Universität Bremen
FB 3 - Mathematik und Informatik
AG Robotik
Robert-Hooke-Straße 1
28359 Bremen, Germany

Zentrale: [phone]

Besuchsadresse der Nebengeschäftsstelle:
Robert-Hooke-Straße 5
28359 Bremen, Germany

Tel.: [phone]
Empfang: [phone]
Fax: [phone]
E-Mail: ***@informatik.uni-bremen.de

Weitere Informationen: http://www.informatik.uni-bremen.de/robotik

[Rasmus Larsen]

Attached is a patch to the existing ColPivHouseholderQR that updates it to
use the numerically stable norm downdate formula due to Drmac and Bujanovic
(see http://www.netlib.org/lapack/lawnspdf/lawn176.pdf), which avoids the
need to directly re-compute the norm of the pivot column every time. This
makes pivoting & rank determination stable for graded matrices, and the
patch contains new and stricter unit tests. The change comes with a modest
slowdown for small matrices (e.g. ~18% slower for 64x64). I think it is
worth it, but perhaps you have ideas for how to improve my implementation?
I tried vectorizing the norm downdate step, but it required multiple extra
scratch vectors and didn't improve speed much.

Best,
Rasmus

Post by Gael Guennebaud
This is a very long time wanted feature. Sadly, nobody started to work on
it yet. Retrospectively, this "soon" was really optimistic. A tile-based
implementation would be even better (better multi-threading), and
completing this class with complete orthogonalization for minimal norm
solving would be a nice bonus too.
Any volunteer? or sponsorship?
gael

Post by Rasmus Larsen
It would be great to have an implementation of the LAPACK algorithm in
http://eigen.tuxfamily.org/dox/group__TopicLinearAlgebraDecompositions.html
there is a "teaser" saying that ColPivHouseholderQR will soon be blocked.
Is somebody actually working on this, and is so, what's the timeline?
Rasmus