| 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: Sun, 17 May 2009 00:06:55 -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=s8wONBQT/CGSwOTN8GKdoL2InD7owrzUfIWaSVhUr4o=; b=R8Y4d4v1XwYu0166oRVgrBy76CN2UqXXXoh8zpPBOd6fOzAM7rYqMqVB+ze8QPuB94 yPXJRB/xPP0adopOyt7ymje0XnNESwcJk/EE15m3dK/oRmcYWi0IKWYcDw0tS5SxtJ4a jyrYlLB9qTHoZfUbNXPBxyxBk2upHYTFi1FvM=
- 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=O+WdYsmGRX42AjufeeB8rc1fFOwBv0xButA8G3VSEMeHiOQd5dhvX289ZcKROfacyQ emdb7VtOHk6AadGfQiFPNfVQssU/F5jCsHXOW1GcuUIkbrfn/KTwLnBPyzR6AEpolsVX 1j4JP/Dg03CPwyasYdKyIApmhnYfzZ7I1Ony4=
there we go, yet another spam from me.
i remember you said that Givens was only preferable for size==2. so is
your QR restricted to that case? that would explain a lot of stuff i
didn't understand at first about your code, like why your m_qr had
only 2 rows... you've got to explain me, i can't guess everything ;-)
also i guess that means that your benchmark was for 2 rows so you
meant up to size 2x150 and not 150x150... now it makes sense that it's
much faster than householder in that case.
what i really don't understand is, that 2xN QR is basically one
operation, so i guess you meant something else.. like 2xN RQ or Nx2 QR
?
also is any of these cases important? naively i would have thought
that the only important case with 2 rows is ... 2x2. For the rest it's
probably not a big deal to fall back to Gram-Schmidt...
Benoit
2009/5/16 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>:
> yet another thing:
>
> if (b == Scalar(0))
>
> this needs to be replaced by the appropriate fuzzy comparison
> (ei_isMuchSmallerThan with appropriate parameters depending on your
> context).
>
> As we always say... implementing a basic version of a numeric
> algorithm is only the beginning... then the real "fun" begins!
> Benoit
>
> 2009/5/17 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>:
>> One more thing...
>> While your code is a great start for Givens-based QR, it is not what
>> we mean by "QR specialized for fixed-size". For example, the QR
>> currently in Eigen, when applied to a fixed-size matrix, specializes
>> exactly as well as your code to that case. But when we say that having
>> fixed-size specializations would be nice, we mean something else:
>> compilers tend to do a poor job unrolling nested for loops, so what we
>> really mean is that we'd need either hand-unrolled or meta-unrolled
>> code. For examples of meta-unrolled code, you can have a look at the
>> unrollers in Eigen/src/Core/Assign.h. For examples of hand-unrolled
>> specializations (moreover using custom algorithms depending on the
>> matrix size) have a look at Eigen/src/LU/Inverse.h. These are two
>> possible approaches. This is the kind of optimizations for fixed-size
>> that we had in mind when we said "fixed-size specializations of QR".
>>
>> Cheers,
>> Benoit
>>
>