Re: [eigen] Specialized QR |

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

On Wed, 20 May 2009, Benoit Jacob wrote:

Unless someone who knows better disagrees, I think that in plain QR
decompositions (not RRQR) it's pretty safe to assume that the Q matrix
is wanted.

I'm not so sure. Suppose you solve Ax = b via QR. The steps are: factor

`A = QR, compute y = Q^{-1} b = Q^T b, solve the triangular system Rx = y.
``So you don't need Q, but only Q^T b. To form Q, you apply O(n^2) Givens
``rotations to the identity matrix, total cost O(n^3). But you can compute
``Q^T b by applying the Givens rotations directly to the vector b, for a
``cost of only O(n^2).
`

`I'm not sure about the details. And I don't know a use case for
``solving Ax = b by QR instead of LU. But I note that LAPACK has routines
``for the factorization (with and without pivoting) without computing Q, for
``computing Q, and for computing Q (or Q^T) times a vector [1]. And Golub &
``van Loan say something similar in the context of Householder QR for least
``squares problems.
`
[1] http://www.netlib.org/lapack/lug/node44.html#2830
Givens rotations, that is the loop
for (int i = k1; i < cols; ++i){
tmp = m_R.coeff(k1, i);
m_R.coeffRef(k1, i) = ei_conj(o1)*m_R.coeff(k1, i)
+ ei_conj(o2)*m_R.coeff(k2, i);
m_R.coeffRef(k2, i) = o1*m_R.coeff(k2, i) - o2*tmp;
}

`are used in many algorithms, for instance SVD (in the algorithm we're
``using at the moment) and GMRES (iterative method for solving Ax = b). So
``if possible we should have an optimized version in a separate function.
`
Jitse