3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – Harry
    Commented Dec 5, 2019 at 15:34
  • $\begingroup$ yeah! I have familiarity with Householder process. Can we say that Householder is Implicit and GramSchmidth is explict? $\endgroup$ Commented Dec 5, 2019 at 16:05
  • $\begingroup$ 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. $\endgroup$ Commented Aug 27, 2021 at 0:14

2 Answers 2

7
$\begingroup$

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 …

$\endgroup$
2
  • $\begingroup$ An implementation of this, together with an not-so-thorough explanation, can be found in Numerical Recipes in Fortran 77. $\endgroup$
    – csha
    Commented Feb 20, 2020 at 19:44
  • $\begingroup$ 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. $\endgroup$
    – James
    Commented Dec 28, 2022 at 14:21
3
$\begingroup$

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

and adding the shift:

  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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .