## 2 The Matrix Diagonalization
### The QR Algorithm  
The QR algorithm is employed to calculate the diagonal matrix \(D\) and the invertible matrix \(P\). This algorithm is an iterative method that relies on the QR factorization. The QR factorization involves decomposing a matrix \(A\) into the product of two matrices, \(Q\) and \(R\), where \(Q\) is an orthonormal matrix and \(R\) is an upper triangular matrix.  
Consider a nonsingular matrix \(A\) from which we determine the eigenvectors and eigenvalues. The QR algorithm initiates the iterative procedure with \(A_{0}=A\), and generates a sequence of matrices \(A_{j}\) as shown in Equation (1).  
The equations are as follows:  
\[A_{j-1}=Q_{j}R_{j},\ \Rightarrow\ Q_{j}^{-1}A\qquad=R_{j},\ \Rightarrow\ Q_{j}^{-1}AQ=R_{j}Q_{j},\ \Rightarrow\ A_{j}\qquad=R_{j}Q_{j} \tag{1}\]  
In Equation (1), the matrix \(A_{j-1}\) is decomposed into the matrices \(Q_{j}\) and \(R_{j}\). Here, \(Q_{j}\) is an orthonormal matrix, and \(R_{j}\) is an upper triangular matrix with non-negative values on its main diagonal. It is important to note that these matrices are unique.  
Through the process illustrated in Equation (1), the matrix \(A_{j}\) is derived by performing the commutation between \(Q_{j}\) and \(R_{j}\). This procedure is implemented in Algorithm 1 to obtain the diagonal matrix \(D\) from a nonsingular matrix \(A\).  
```
0: Non singular matrix \(A\).
0: Diagonal matrix \(D\), Orthonormal matrix \(P\).
0:\(D\gets A\) \(P\gets 1\) while\(D\) is non diagonal do \(D\to QR\) \(P\gets PQ\) \(D\gets RQ\) endwhilereturn D, P
```  
**Algorithm 1** The QR algorithm  
Algorithm 1 encompasses multiple variants of the QR algorithm, which are distinguished based on the chosen factorization method. The factorization method can be Gram-Schmidt, LU, Givens, Cholesky, or Householder. The convergence of the QR algorithm is influenced by both the input matrix \(A\) characteristics and the specific factorization method used.  
A Scalable and Efficient CPU-GPU Optimized Algorithm for Symmetric Tridiagonal Eigenvalue Solver Across Nodes  
The optimization of the QR algorithm involves two main improvements: tridiagonalization of the matrix and the use of the divide-and-conquer Cuppen's algorithm. This section will outline the steps involved in these advancements. The first step focuses on the iterative process of QR factorization, as explained in Section 2, to obtain a diagonal matrix. However, this process can be computationally expensive, and the number of iterations within the QR algorithm can be minimized by applying it to a tridiagonal matrix instead. The number of QR iterations required can be reduced by obtaining a tridiagonal matrix that closely resembles the original one. One effective approach to achieving a tridiagonal matrix is the Householder bi-factorization method, which will be detailed in Section 3.1. This method, with its technical prowess, transforms the input matrix into a tridiagonal form, optimizing the subsequent steps of the QR algorithm and impressively enhancing its performance.  
The second step focuses on applying the divide-and-conquer Cuppen's algorithm to reduce the size of the matrices involved in the diagonalization problem. This reduction in size helps minimize the number of iterations needed for convergence in the algorithm. Section 3.2 provides an explanation of [PERSON]'s algorithm, detailing how it efficiently partitions the matrices and computes the eigenvalues separately. By incorporating thisalgorithm, the optimization of the QR algorithm achieves faster convergence and improved efficiency in obtaining the desired results.