[eigen] question on numerical stability of non-pivoting householder algos

[Benoit Jacob <jacob.benoit.1@xxxxxxxxx>]

Hi list,

I'd like to ask a question to the numerics gurus here.

I've always been considering that plain HouseholderQR (no pivoting)
should be considered not-very-stable on singular matrices, since a
tiny perturbation on the matrix could result in a completely different
householder transformation.

Is this correct? For sure HouseholderQR doesn't give as precise
results as pivoting variants, in my experiments. But how bad can it
be? Is there some upper bound on the imprecision on ill-conditioned
matrices or can it get arbitrarily bad?

Related question: bidiagonalization and tridiagonalizations are close
cousins of QR and will suffer from exactly the same problem. Worse:
contrary to QR, they can't be made pivoting (at least not in the
direction that matters the most).

Since bidiag and tridiag are the basic ingredient for SVD and
SelfadjointEigensolver respectively, this means that SVD and
SelfadjointEigensolver suffer from the same inaccuracy/instability
issues on near-singular matrices as HouseholderQR does.

I'm asking mostly because we're writing this page,
http://eigen.tuxfamily.org/dox-devel/TopicLinearAlgebraDecompositions.html
and need to know what to say about the accuracy/reliability of various algos.

Thanks,
Benoit