what is Explicit And Implicit Qr Algorithms For Symmetric And Non-symmetric Matrices?

Question

I thought that QR algorithm decomposes a matrix into an orthogonal matrix Q and a upper triangular matrix R using GramSchmidth process for singular matrices but, what is meant by Explicit and Implicit QR algorithms? and how will they help in decomposing a non-singular matrix?

Answer 1

The explict QR algorithm for computing eigenvalues of a matrix $A$ works like this:

1. Compute $QR$ decomposition $A_i = Q_i R_i$
2. Set $A_{i+1} = R_i Q_i (=Q^{\mathsf T} A Q)$
3. Repeat until $A_{i+1}$ is sufficiently close to an upper triagonal matrix

One may prove convergence to an upper triangular matrix, if $|λ_i| \neq |λ_j|$ for all eigenvalues $λ_i, λ_j$ of $A$. The computation of the $QR$ decomposition is costly ($\mathcal{O}(n^3)$) and one doesn't wan't to do it in every step of the iteration.

If $A$ is of so-called upper Hessenberg form, i.e. a matrix where all entries below the first lower subdiagonal are zero (or in formulas: $a_{ij} = 0$, if $i>j+1$), the computation becomes less costly, namely only $\mathcal{O}(n^2)$. One can use the Givens rotations, Harry mentioned. Also, if $A$ is an upper Hessenberg matrix, all the iterates $A_i$ will be, too. Therefore, transforming your matrix into an upper Hessenberg matrix (using Householder transformations) pays out.

But even for Hessenberg matrices computing the $QR$ decomposition and then performing the matrix matrix multiplication $RQ$ is still expensive. This is where in »Implicit $Q$ Theorem« is used. It says, that if $Q A Q^{\mathsf T}$ is an upper Hessenberg matrix, then $Q$ is essentially uniqely defined by the first column of $Q$. But we already know, that all the iterates must be in Hessenberg form.

The idea now is as follows:

1. Compute the first column of the $QR$ decomposition of $A$. That is: Compute a Givens rotation $G_1$ such that $(G_1 A_1)_{2,1} = 0$. Now, update $\tilde{A}_1 := G_1A_1 G_1^{\mathsf T}$ (which may be done efficiently without actually doing matrix matrix multiplications)
2. The entry $(3,1)$ of $G_1A_1 G_1^{\mathsf T}$ will now be non zero. Compute another Givens rotation $G_2$such that $(G_2 G_1 A_1 G_1^{\mathsf T})_{3,1} = 0$ und update the matrix analogously to 1. Note, that the first column of $G_2 G_1$ is still given by the first column of $G_1$!
3. The entry $(4,2)$ will now be non zero. Iterate the procedure. This is known as "bulge chasing"

At the end, one has implictly computed $RQ$ at a cost of only $\mathcal O(n^2)$ per iteration step. This is way this algorithm is called the Implicit QR algorithm.

I hope that my answer helps you. This answer is based on my lecture notes and unfortunately I don't have a good reference suggestion at hand …

Answer 2

The classic QR algorithm iteration:

1. $QR = A $ ........decomposition

2. $A' = RQ $

due $Q$ is orthogonal, is also true:

2. $A' = Q^T Q RQ = Q^T A Q$

3. A=A' repeat, A should go diagonal after few iterations, probably bottom-right to left, chance to reduce the matrix or deflate.

The explicit/implicit QR algorithm is mentioned generaly in the context of adding shifts for faster convergence. QR can take a lot of iterations due to the convergence rate that depends on the magnitude between adjacent eigenvalues along the matrix.

The explicit shifted version. Differs from the classic subtracting a diagonal shift for faster convergence:

1. $QR = A - \mu I$ ........decomposition

and adding the shift:

2. $A' = RQ + \mu I$

There's little choice for this shift and is either implementation or kind of matrix dependent. There's also a double-shifted version for dealing with complex values.

The QR decomposition operation to choose depends; A could have been transformed upper hessenberg form (an upper triangle with a subdiagonal), if symmetric matrix this transform will lead to a tridiagonal matrix; whatever was, those pre-transforms $H$ must keep the input A and the real input A, similar $A_{real} = H^{-1} A_{input} H$, with $H$ inversible, meaning that both matrices have the same eigenvalues. Usually those pre-transforms use householder reflections.

The implicit shifted form of the QR algorithm, uses Francis Q theorem. The theorem says that if $A'$ is an upper hessenberg matrix any orthogonal matrix $Z$ can be suitable for the iteration:

2. $A' = Z^T A Z$

As long the first column of $Z$ equals to the first of $Q$, and $Z$ brings back the matrix to upper hessenberg form. In this case, Z and Q can only differ by a diagonal product of +-1 values.

This theorem allows the previous explicit-shift $A - \mu I$ to be "inserted" implicitly (instead of subtract, decompose, add - just multipling at left and right Z). So if $A - \mu I$ was the matrix, and the goal of the first transform $Q_0$ of Q is to reflect or rotate a first column vector to start zeroing the matrix towards a triangle - Knowing the matrix have the shift $\mu$ subtracted allows us to create a similar $Z_0$; however when you plug on the iteration step $A'=Z_n^T...Z_0^T$ A $Z_0...Z_n$ - at the first $Z_0^T$ A $Z_0$ theres a second effect - a non-zero "a bulge" will be introduced. The set of transforms $Z_1..Z_n$ and its transposes should enter the game of the "chase-the-bulge" (as mentioned in the previous post) to lead the matrix to the right form; those pairs of transforms will introduce and erase places. Due the theorem the set of $Z_1..Z_n$ must not damage the first column $Z_0$; and matrix $A'$ must end in an upper hessenberg, or a narrow version of, within less rows/cols affected by transforms as possible.