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?


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.

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

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.