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

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?

• I don't think it necessarily involves Gram-Schmidt. I recall implementing this using Householder transformations. And I think Givens rotations are another choice. (If I remember correctly, "Numerical Recipes, The Art of Scientific Computing" was an excellent reference. I don't remember if they talked specifically about the singular and nonsingular cases). Commented Dec 5, 2019 at 15:34
• yeah! I have familiarity with Householder process. Can we say that Householder is Implicit and GramSchmidth is explict? Commented Dec 5, 2019 at 16:05
• The implicit QR algorithm is an method for finding the matrix $A^{k+1}$ using $A^{k}$ without getting too much catastrophic cancellation during shifted QR algorithm, which is frequent. The $A^{k}$ sequences produced in shifted QR algorithm and implicit shifted QR algorithm is mathematically the same, but not numerically the same. Commented Aug 27, 2021 at 0:14

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 …

• An implementation of this, together with an not-so-thorough explanation, can be found in Numerical Recipes in Fortran 77.
– csha
Commented Feb 20, 2020 at 19:44
• Are you able to link to your lecture notes or are they copyrighted? I would like to read them to better understand the math behind how this works. Commented Dec 28, 2022 at 14:21

The classic QR algorithm iteration:

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

2. $$A' = RQ$$

due $$Q$$ is orthogonal, is also true:

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

2. 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

1. $$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:

1. $$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.