The usual story of Givens rotations vs Householder reflections is that Householder reflections are better if you want to map a long vector to $e_1$, while Givens is better if you want to map a 2-vector to $e_1$. However, I can't find a reference which explains why Givens is better in the 2-vector case. Can anyone explain?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
2
Typically you don't apply these matrices to a single vector; you apply them to a $m\times n$ matrix, where $n$ is large, so you can amortize the cost of computing the various coefficients. Applying a Householder reflector to a vector (with the formula $x \mapsto x - vv^Tx$) costs $4m-1$. Applying a Givens rotation works only for $m=2$, and costs $6$ operations, which is cheaper.
EDIT: To apply the Householder transformation, you could instead form the $2\times 2$ matrix $Q = I-vv^T$ and apply that to a vector, as suggested by @gTcV in the comments, for 6 operations. But it's not complicated to see that at this point $Q$ is essentially a Givens rotations with two signs swapped, so that's not really anything different from Givens transformations.
answered Aug 21 '19 at 9:43
-
$\begingroup$ The cost of applying a Givens rotation is that of a 2x2 matrix-vector product, and clearly applying a Householder reflection can't be more expensive than that because I can represent the Householder reflector as a dense 2x2 matrix. I therefore don't see how the performance argument works out. $\endgroup$ – gTcV Aug 21 '19 at 13:30
-
$\begingroup$ @gTcV Good point -- I was referring to Householder reflectors when applied in the usual form $I-vv^T$; if you convert them to a $2\times 2$ matrix and apply them directly then the cost becomes the same. $\endgroup$ – Federico Poloni Aug 21 '19 at 14:13
