-- 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):

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 up‘s;	This is correct if one deciphers [3] the "Householder up‘s" as upper components of Householder vectors , i.e.
fW : n-vector with Householder beta‘s.	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.