12
$\begingroup$

It’s obvious that Givens rotation works better with sparse matrices. But I don’t know why Householder reflection is better for dense matrices. Does it require less computations? Or it’s numerically more stable than Givens rotation?

(Original post)

$\endgroup$
3
  • $\begingroup$ I am downvoting, since the question does not given enough context. What is better ? Why do you believe that it is better. This question should be handled on math.se. $\endgroup$
    – Pushpendre
    Jan 3, 2016 at 13:32
  • 4
    $\begingroup$ I'm assuming "better" means something like "cheaper" if numerical calculations are considered as having a cost, but I agree that it would help the more "theoretically-minded" (faute de mieux) if the OP could clarify what is meant in the post. (Parenthetically, not being in numerical analysis culture myself, the linked Wikipedia articles have a strange appearance in citing Givens and Householder as mathematicians who "introduced" these transformations in the 1950's, when these seem to me like very basic linear algebra things which would have been known to mathematicians for about 150 years.) $\endgroup$
    – Todd Trimble
    Jan 3, 2016 at 18:52
  • $\begingroup$ @Pushpendre I think you are right, My question seems a bit unclear, but the answer below is exactly what I wanted, so should I edit the question or leave it be? $\endgroup$
    – lino
    Jan 3, 2016 at 19:14

2 Answers 2

14
$\begingroup$

Implementing the QR factorization with Householder rotations is cheaper ($2n^2m$ vs $3n^2m$ for a $m\times n$ matrix), and equally accurate in practice. See Section 19.6 of Higham's Accuracy and Stability of Numerical Algorithms, or Golub-Van Loan for more explicit algorithms.

Moreover, in a Householder-based implementation there is a higher fraction of level-2 BLAS operations vs level 1, which makes them easier to optimize on a real-world computer.

$\endgroup$
1
$\begingroup$

Givens rotations cost you a lot of memory when working on a big dense Matrix, if you want to reduce a matrix to its upper Hessenberg form for example, then for each element under the subdiagonal, you'll perform a matrix product, imagine if you want to reduce a 1-milionX1-million matrix that cost a lot. Householder reflections are better than Givens rotations since it allows you to reduce a whole column then zeroing only one element.

But Gram-schmidt is better than these two methods If I'm not wrong, since there is no matrix product.

$\endgroup$
1
  • 2
    $\begingroup$ Gramm Schmidt, even the modified version, suffers from high numerical instability and is therefore not used in practice for QR decompositions. $\endgroup$ Aug 22, 2023 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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