<var>QR</var> Factorization

next up previous contents index
Next: Eigenvalue Problems Up: Examples of Block Previous: Factorizations for Solving

QR Factorization


The traditional algorithm for QR factorization  is based on the use of elementary Householder  matrices of the general form

where v is a column vector and

is a scalar. This leads to an algorithm with very good vector performance, especially if coded to use Level 2 BLAS.

The key to developing a block form of this algorithm is to represent a product of b elementary Householder matrices of order n as a block form of a Householder matrix . This can be done in various ways. LAPACK uses the following form [68]:

where V is an n-by-n matrix whose columns are the individual vectors

associated with the Householder matrices

, and T is an upper triangular matrix of order b. Extra work is required to compute the elements of T, but once again this is compensated for by the greater speed of applying the block form. Table 3.6 summarizes results obtained with the LAPACK routine SGEQRF /DGEQRF .


                    No. of    Block   Values of n
                  processors   size   100    1000
CONVEX C-4640          1        64     81     521
CONVEX C-4640          4        64     94    1204
CRAY C90               1       128    384     859
CRAY C90              16       128    390    7641
DEC 3000-500X Alpha    1        32     50      86
IBM POWER2 model 590   1        32    108     208
IBM RISC Sys/6000-550  1        32     30      61
SGI POWER CHALLENGE    1        64     61     190
SGI POWER CHALLENGE    4        64     39     342

Table 3.6: Speed in megaflops of SGEQRF/DGEQRF for square matrices of order n

Tue Nov 29 14:03:33 EST 1994