Re: [eigen] Specialized QR |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Specialized QR
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Wed, 20 May 2009 06:48:05 -0400
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=B9AWJ68AKebWjvWc+zM0Co0f/NTsay9s6RL3YIyQ8mo=; b=Z1fgR8xc0ti0OHHkakqKoUjhIyrGQMgAGaBe6rlTgm486BWqp9NggUjgmOXkvp8Vv7 g8L3vjvowzftOZL53EP4ZbyGYL6anAHbQ1cj1Sfm+zwACRsYS6Q9MADx4cdI1Vg3ghm4 KS5fgY9mB1lfboGTzgJvMwjJg69qvEcL4jIyE=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=qgr/QpIFU+2uspyUrVtrPLWLXgMsE4A9T7eyBN4rApN/3UQYK4tDNUbLRY3vzNdOqx VAgmXC/4nMljo8fbT7IzGXHjUdbDyM02FloqaR97C2ruMpslZvDnUg1CdawYHgIXYM3G yRxC330WDkazjAiaMyWw0cR17e4cZ+/RhLs+0=
You are perfectly right, I overlooked this!
So indeed it would be nice to only compute Q if it's needed.
Benoit
2009/5/20 Jitse Niesen <jitse@xxxxxxxxxxxxxxxxx>:
> 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
>
>
>