2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.