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?
2
$\begingroup$
$\endgroup$
0
$\begingroup$
$\endgroup$
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 costs $4m-1$. Applying a Givens rotation works only for $m=2$, and costs $6$ operations, which is cheaper.
-
$\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 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 at 14:13
