linear-algebranumericnumerical-methods

Reducing to Hessenberg form using Givens rotations


I'm trying to implement a function in Python that reduces a square matrix to upper Hessenberg form using Givens rotations. I know that this should be possible Wiki and sometimes preferred over Householder transformations for certain applications, but I haven't been able to find a clear algorithm or reference that shows how to do it with Givens rotations. Every ordering of givens rotations just destroys the previous zeros entirely.

Here's what I have so far:

def Hessenberg(A):
    n = len(A)
    for k in range(n - 2): #columns
        for j in range(n - 1, k + 1, -1): #rows
            if A[j, k] != 0:
                Givens(A, j,k) #Implemented in a way that zeroes in place
    return A

The Givens function is implemented to apply the rotation in-place to zero out the element at position (i,j) However, the resulting matrix is not in Hessenberg form, and I think I'm missing something about how the rotations should be applied, because every next rotation deletes the progress from the previous ones.

Questions:

Is there a standard or recommended way to apply Givens rotations to reduce a matrix to Hessenberg form? Are there any references or pseudocode that describe this process clearly?

Note that I want the matrix to remain similar, so the onesided Givens as in QR decomposition would not be ok.


Solution

  • Ok, I have figured out what was wrong.

    In most scenarios, we use Givens/Jacobi rotations Q_{i,j} acting on rows/columns i and j and want to zero out an element A(i,j), for example, in computing QR decomposition or using Jacobi rotations to compute eigenvalues for symmetric matrices. But here we do not want that, and instead we want to use Q_{i,j} and zero out an element A(i, j-1).

    Why?

    When we use Q_{i,j} from both sides we create linear combinations of i-th and j-th row/column and for element A(i,j) we add both the other column and row, which makes it harder to keep track of what we are doing.

    But if we want to zero out the element A(i, j-1), we only create the linear combination with the row j, which is easier to keep track of. Essentially, what we are doing is using A(j,j-1) to zero out elements A(j+1, j-1), A(j+2, j-1), ..., A(n,j-1) for the column j-1.