-- AlexanderFedotov - 03-May-2011

Root class TDecompQRH -- how to use

The issue

The question is actually: How to understand a completely misleading description of the class?

The question has been raised in RootTalk -- TDecompQRH - how to use the householder decomposition? -- but was not answered properly by the author, Eddy Offermann .

User's Guide on TDecompQRH

Here is a snpashot of the description from the Root User's Guide v5.26 (which differs very little from what can be found in Reference Manual or in the comments in source files):

QRH_userguide526.gif

Comments to the "guide"

Having inspected the code, I found that the code may be ok, but the description is wrong and requires the following corrections line by line:

original comment / corrected version
Decompose an (m x n)-matrix A with m ≥ n. ok
A = QRH A = QR
  • no matrix H !
Q : orthogonal (m x n) - matrix, stored in fQ; Everything is wrong!
"Orthogonal" -- yes, but :
  • (m x m) instead of (m x n)
  • not stored in fQ
  • Q is not explicitly stored anywhere
Q is defined as , where
where is a Householder matrix of dimension ( with ) which performs a Householder transformation by reflecting about a hyperplane that is perpendicular to a Householder vector [1]
[2])

can be expessed via as
where
That allows the matrix Q to be stored implicitly via a set of (in fQ and fUp, see below) and -- for faster computations in future -- a set of (in fW).

Now we can describe what does fQ contain?
  • before the decomposition: it contains the matrix A
  • after the decomposition:
    • it contains the upper triangular matrix R in the diagonal and above the latter
    • it also contains a part of vectors , namely, the k-th column contains under the diagonal
    • i.e. the without its first element
R : upper triangular (n x n)-matrix, stored in fR; Right. R is found as , calculated iteratively:
(to be noted: ).
First, R is computed and placed into upper part of fQ, then copied into fR .
H : (n x n)-Householder matrix, stored through; The H matrix is a nonsense: as we see, the involved matrices are of dimension (m x m), and the matrices of dimensions (m x m), (m-1 x m-1), ... .
fUp : n-vector with Householder ups; This is correct if one deciphers [3] the "Householder ups" as upper components of Householder vectors , i.e.
fW : n-vector with Householder betas. Similarly, an explicit definition is much better:
The decomposition fails if in the formation of reflectors a zero appears, i.e. singularity. ? (I did not check this statement)

Footnotes



[1] Definition of Householder vectors for the decomposition.
The vector is chosen such that the corresponding Householder transform would reflect the first column of matrix A

onto the vector . This ensures that will have zeros in the the first column under the diagonal. It is quite obvious that there are two options: can be reflected
  • either into with
  • or into with
The choice is made in favour of in order to avoid the when is almost collinear with (in the latter case, an equality may lead to a big loss of precision while calculating ). Then,
The next Householder vector, , is defined similary via the second column of matrix , such that would have zeros under the diagonal in the 2nd column, and so on.



[2] Actually, matrices also represent Householder reflections in with Householder vectors



[3] Do terms "Householder's up's and beta's" come from the book "Matrix Computations" by Golub and Van Loan ?
There is a comment in the text of TDecompQRH::Decompose function:

  • "QR decomposition of matrix a by Householder transformations,
    see Golub & Loan first edition p41 & Sec 6.2."
The terms "up's and beta's" may be used in this book.
It looks a bit strange to refer to the first edition for the code written at ~2004, i.e. 8 years after the third edition had been published.
I did not find the 1ed, but found 3ed (here) and 2ed (in russian, 8MB or 58MB). In those editions, the notion of Householder's up's seems to be absent. Also the term Householders beta's is not used, though the symbol is employed for what is called Householders beta above, sometimes with an opposite sign.

Topic attachments
I Attachment History Action Size Date Who Comment
Unknown file formatdjvu Golub_VanLoan.Matr_comp_2ed_ru.djvu r1 manage 7867.5 K 2011-05-02 - 04:37 AlexanderFedotov  
PDFpdf Golub_VanLoan.Matr_comp_2ed_ru.pdf r1 manage 56447.9 K 2011-05-04 - 19:50 AlexanderFedotov  
PDFpdf Golub_VanLoan.Matr_comp_3ed.pdf r1 manage 11833.8 K 2011-05-02 - 04:25 AlexanderFedotov  
GIFgif QRH_userguide526.gif r1 manage 15.3 K 2011-05-03 - 20:05 AlexanderFedotov  
Edit | Attach | Watch | Print version | History: r6 < r5 < r4 < r3 < r2 | Backlinks | Raw View | WYSIWYG | More topic actions
Topic revision: r6 - 2011-05-04 - AlexanderFedotov
 
    • Cern Search Icon Cern Search
    • TWiki Search Icon TWiki Search
    • Google Search Icon Google Search

    Main All webs login

This site is powered by the TWiki collaboration platform Powered by PerlCopyright & 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback