Implementing QR Algorithm from Golub & Van Loan's "Matrix Computations" - notation and operation assistance

Question

I am implementing the Francis QR Algorithm from Golub & Van Loan's "Matrix Computations" (see algorithms below).

I am unsure about the meaning of the following step:

"Find the largest nonnegative $q$ and the smallest non-negative $p$ such that..."

EDIT 4/30/2020: I have made some progress, the notation being used is "Block Matrix" notation, however I have noticed more difficulties. To simplify the question I am removing components that are no longer relevant.

1. Francis Step requires a Matrix of minimum size $3\times 3$. Does this mean the algorithm is only viable for matrices of minimum size $5\times 5$ ($p=q=1$)? Are there workarounds for $3\times3$ & $4\times4$ matrices?
2. When partitioning the block matrix, I have not been able to find dimensions that satisfy the given conditions.

For example, using the following $8\times8$ matrix $A$ (larger size so it's a bit easier to demonstrate),

1  2  3  4  5  6  7  8
9 10 11 12 13 14 15 16
0 18 19 20 21 22 23 24
0  0 27 28 29 30 31 32
0  0  0 36 37 38 39 40
0  0  0  0 45 46 47 48
0  0  0  0  0 54 55 56
0  0  0  0  0  0 63 64

There are a number of ways to partition it (while maintaining an $H_{22}$ of at least size $3\times3$), for example:

$p = 1 ;\; q = 4$

 1   2 3 4      5 6 7 8     

 9   10 11 12   13 14 15 16 
 0   18 19 20   21 22 23 24 
 0    0 27 28   29 30 31 32 

 0   0 0 36     37 38 39 40 
 0   0 0  0     45 46 47 48 
 0   0 0  0      0 54 55 56 
 0   0 0  0      0  0 63 64

$p = 2 ;\; q = 3$

 1  2    3  4  5    6  7  8 
 9 10   11 12 13   14 15 16 

 0 18   19 20 21   22 23 24 
 0  0   27 28 29   30 31 32 
 0  0    0 36 37   38 39 40 

 0 0    0 0 45     46 47 48 
 0 0    0 0  0     54 55 56 
 0 0    0 0  0      0 63 64 

$p = 3 ;\; q = 2$

 1  2  3    4  5  6    7  8 
 9 10 11   12 13 14   15 16 
 0 18 19   20 21 22   23 24 

 0 0 27    28 29 30   31 32 
 0 0  0    36 37 38   39 40 
 0 0  0     0 45 46   47 48 

 0 0 0     0 0 54     55 56 
 0 0 0     0 0  0     63 64 

$p = 4 ;\; q = 1$

 1  2  3  4    5  6  7    8 
 9 10 11 12   13 14 15   16 
 0 18 19 20   21 22 23   24 
 0  0 27 28   29 30 31   32 

 0 0 0 36     37 38 39   40 
 0 0 0  0     45 46 47   48 
 0 0 0  0      0 54 55   56 

 0 0 0 0      0 0 63     64 

$p = 1 ;\; q = 3$

 1   2 3 4 5       6 7 8    

 9   10 11 12 13   14 15 16 
 0   18 19 20 21   22 23 24 
 0    0 27 28 29   30 31 32 
 0    0  0 36 37   38 39 40 

 0   0 0 0 45      46 47 48 
 0   0 0 0  0      54 55 56 
 0   0 0 0  0       0 63 64 

and on and on. Essentially, I have not been able to find combinations that result in a zero matrix in the $H_{12}$ spot. Every time it shifts it picks up a new subdiagonal non-zero scalar.

What am I doing wrong?

Answer 1

The text says to find the largest $q\geq0$ and smallest $p\geq0$ such that H is split into a 3x3 block matrix with the following requirements on the blocks:

1. $H_{11}$ is $p\times p$,
2. $H_{22}$ is unreduced (no zeros on sub-diagonal),
3. $H_{33}$ is $q\times q$ and upper quasi-triangular (it can be written as an upper triangular block matrix where each block on the diagonal is either $1\times1$ or $2\times2$),
4. $H_{21}$, $H_{31}$, $H_{32}$ are all zero matrices.

Generally we want to make $q$ as large as possible and $p$ as small as possible. The example you give above is an $8\times8$ unreduced Hessenberg matrix. If $q>0$ then it's impossible to make $H_{32}$ all zeros because any diagonal block will have a non-zero entry to the left of it, so we must have $q=0$. If we set $p=0$ as well then we satisfy all of the requirements. $H_{22}$ is the entire matrix and it is unreduced.

So the answer to your question about the example matrix is setting $q=0$ and $p=0$.

The solution for the general case is as follows. Let $\vec{s}$ be the vector of sub-diagonal values of H. Starting at the end of $\vec{s}$ and working backwards, find the first cluster of at least two adjacent non-zero values in $\vec{s}$. Set $q$ to the number of entries before that cluster, and set $p$ to the number of entries after that cluster.

Since for your example $\vec{s}$ is all non-zero values, it's easy to see why $q=0$ and $p=0$.