## 3 Description of Numerical Algorithms
### Schur Decomposition Methods  
Schur decomposition-based methods take advantage of the fact that, for any \(r\times r\) matrix \(\mathbf{A}\), there always exists a unitary matrix \(\mathbf{Q}\in\mathbb{C}^{r\times r}\), such that:  
\[\mathbf{T}=\mathbf{Q}^{\mathrm{H}}\mathbf{A}\mathbf{Q}\,, \tag{20}\]  
where \(\mathbf{T}\), \(\mathbf{T}\in\mathbb{C}^{r\times r}\), is an upper triangular matrix with diagonal elements all the eigenvalues of the pencil \(\mathbf{s}\mathbf{I}_{r}-\mathbf{A}\). Decomposition (20) is known as the Schur decomposition of \(\mathbf{A}\), and matrix \(\mathbf{T}\) as the Schur form of \(\mathbf{A}\). It appears that the most efficient algorithm for computing the Schur decomposition of a given matrix is the QR algorithm. In an analogy to the previously described methods, the QR algorithm can be understood as a nested subspace iteration or as a nested sequence of \(r\) power iterations [50]. Starting with matrix \(\mathbf{A}^{(0)}=\mathbf{A}\), the main steps of the QR algorithm at \(k\)-th iteration, \(k=1,2,3,\ldots\) are:  
\[\mathbf{A}^{(k-1)} =\mathbf{Q}^{(k)}\mathbf{R}^{(k)}\,, \tag{21}\] \[\mathbf{A}^{(k)} =\mathbf{R}^{(k)}\mathbf{Q}^{(k)}\,, \tag{22}\]  
where \(\mathbf{Q}^{(k)}\) is orthogonal and \(\mathbf{R}^{(k)}\) is upper triangular. The QR decomposition (21) is computed by applying Householder transformations, see [51].  
If \(\mathbf{A}^{(k)}\) converges, say, after \(\kappa\) steps, then \(\mathbf{A}^{(\kappa)}=\mathbf{T}\). The diagonal elements of \(\mathbf{A}^{(\kappa)}\) are the eigenvalues of \(\mathbf{A}\). The corresponding right eigenvectors are found as the columns of the matrix:  
\[\mathbf{Q}=\mathbf{Q}^{(1)}\mathbf{Q}^{(2)}\ldots\mathbf{Q}^{(\kappa)}\,, \tag{23}\]  
where \(\mathbf{Q}\in\mathbb{C}^{r\times r}\). Notice that, throughout the algorithm, matrices \(\mathbf{A}^{(k)}\), \(\mathbf{A}^{(k-1)}\) are similar and, thus, they have the same eigenvalues with the same multiplicities. The QR algorithm uses a complete basis of vectors and computes all of the eigenvalues of the matrix pencil \(s\mathbf{I}_{r}-\mathbf{A}\). In practice, the QR algorithm is not typically used as it is, but multiple shifts are applied to accelerate convergence, which leads to the implicitly shifted QR algorithm [52].  
The analog of the QR algorithm for the GEP is the QZ algorithm. The QZ algorithm takes advantage of the fact that for any \(r\times r\) matrices \(\mathbf{A}\), \(\mathbf{E}\), there always exist unitary matrices \(\mathbf{Q}\in\mathbb{C}^{r\times r}\), \(\mathbf{Z}\in\mathbb{C}^{r\times r}\), such that:  
\[\mathbf{T}_{1} =\mathbf{Q}^{\mathrm{H}}\mathbf{A}\mathbf{Z}\,,\] \[\mathbf{T}_{2} =\mathbf{Q}^{\mathrm{H}}\mathbf{E}\mathbf{Z}\,, \tag{24}\]  
are upper triangular, and the eigenvalues of the pencil \(s\mathbf{E}-\mathbf{A}\) are the ratios \(w_{1,\mathrm{i}}/w_{2,\mathrm{i}}\) of the diagonal elements of \(\mathbf{T}_{1}\), \(\mathbf{T}_{2}\), respectively. The decomposition (24) is known as generalized Schur decomposition. From the implementation viewpoint, the algorithm computes all of the eigenvalues of the matrix pencil \(s\mathbf{E}-\mathbf{A}\) by first reducing \(\mathbf{A}\), \(\mathbf{E}\), to upper Hessenberg and upper triangular form, respectively, through Householder transformations. The method can be perceived as equivalent to applying the implicitly shifted QR algorithm to \(\mathbf{A}\mathbf{E}^{-1}\), without, nonetheless, explicitly computing \(\mathbf{E}^{-1}\)[52].