Symmetric Tridiagonal Eigenvalue Solver Across CPU Graphics Processing Unit (GPU) Nodes
In this work, an improved and scalable implementation of Cuppen’s algorithm for diagonalizing symmetric tridiagonal matrices is presented. This approach uses a hybrid-heterogeneous parallelization technique, taking advantage of GPU and CPU in a distributed hardware architecture. Cuppen’s algorithm i...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-11-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/14/22/10716 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846154423603036160 |
|---|---|
| author | Erika Hernández-Rubio Alberto Estrella-Cruz Amilcar Meneses-Viveros Jorge Alberto Rivera-Rivera Liliana Ibeth Barbosa-Santillán Sergio Víctor Chapa-Vergara |
| author_facet | Erika Hernández-Rubio Alberto Estrella-Cruz Amilcar Meneses-Viveros Jorge Alberto Rivera-Rivera Liliana Ibeth Barbosa-Santillán Sergio Víctor Chapa-Vergara |
| author_sort | Erika Hernández-Rubio |
| collection | DOAJ |
| description | In this work, an improved and scalable implementation of Cuppen’s algorithm for diagonalizing symmetric tridiagonal matrices is presented. This approach uses a hybrid-heterogeneous parallelization technique, taking advantage of GPU and CPU in a distributed hardware architecture. Cuppen’s algorithm is a theoretical concept and a powerful tool in various scientific and engineering applications. It is a key player in matrix diagonalization, finding its use in Functional Density Theory (FDT) and Spectral Clustering. This highly efficient and numerically stable algorithm computes eigenvalues and eigenvectors of symmetric tridiagonal matrices, making it a crucial component in many computational methods. One of the challenges in parallelizing algorithms for GPUs is their limited memory capacity. However, we overcome this limitation by utilizing multiple nodes with both CPUs and GPUs. This enables us to solve subproblems that fit within the memory of each device in parallel and subsequently combine these subproblems to obtain the complete solution. The hybrid-heterogeneous approach proposed in this work outperforms the state-of-the-art libraries and also maintains a high degree of accuracy in terms of orthogonality and quality of eigenvectors. Furthermore, the sequential version of the algorithm with our approach in this work demonstrates superior performance and potential for practical use. In the experiments carried out, it was possible to verify that the performance of the implementation that was carried out scales by 2× using two graphic cards in the same node. Notably, Symmetric Tridiagonal Eigenvalue Solvers are fundamental to solving more general eigenvalue problems. Additionally, the divide-and-conquer approach employed in this implementation can be extended to singular value solvers. Given the wide range of eigenvalue problems encountered in scientific and engineering domains, this work is essential in advancing computational methods for efficient and accurate matrix diagonalization. |
| format | Article |
| id | doaj-art-c8b95c3c1f9848ad82824777418fa2e7 |
| institution | Kabale University |
| issn | 2076-3417 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-c8b95c3c1f9848ad82824777418fa2e72024-11-26T17:49:53ZengMDPI AGApplied Sciences2076-34172024-11-0114221071610.3390/app142210716Symmetric Tridiagonal Eigenvalue Solver Across CPU Graphics Processing Unit (GPU) NodesErika Hernández-Rubio0Alberto Estrella-Cruz1Amilcar Meneses-Viveros2Jorge Alberto Rivera-Rivera3Liliana Ibeth Barbosa-Santillán4Sergio Víctor Chapa-Vergara5Sección de Estudios de Posgrado e Invetigación, Escuela Superior de Cómputo, Instituto Politécnico Nacional, Mexico City 07320, MexicoDepartamento de Computación, Cinvestav-IPN, Mexico City 07360, MexicoDepartamento de Computación, Cinvestav-IPN, Mexico City 07360, MexicoEscuela Superior de Cómputo, Instituto Politécnico Nacional, Mexico City 07320, MexicoDepartamento de Ciencias Computacionales, Instituto Tecnológico y de Estudios Superiores de Monterrey, Monterrey 45138, MexicoDepartamento de Computación, Cinvestav-IPN, Mexico City 07360, MexicoIn this work, an improved and scalable implementation of Cuppen’s algorithm for diagonalizing symmetric tridiagonal matrices is presented. This approach uses a hybrid-heterogeneous parallelization technique, taking advantage of GPU and CPU in a distributed hardware architecture. Cuppen’s algorithm is a theoretical concept and a powerful tool in various scientific and engineering applications. It is a key player in matrix diagonalization, finding its use in Functional Density Theory (FDT) and Spectral Clustering. This highly efficient and numerically stable algorithm computes eigenvalues and eigenvectors of symmetric tridiagonal matrices, making it a crucial component in many computational methods. One of the challenges in parallelizing algorithms for GPUs is their limited memory capacity. However, we overcome this limitation by utilizing multiple nodes with both CPUs and GPUs. This enables us to solve subproblems that fit within the memory of each device in parallel and subsequently combine these subproblems to obtain the complete solution. The hybrid-heterogeneous approach proposed in this work outperforms the state-of-the-art libraries and also maintains a high degree of accuracy in terms of orthogonality and quality of eigenvectors. Furthermore, the sequential version of the algorithm with our approach in this work demonstrates superior performance and potential for practical use. In the experiments carried out, it was possible to verify that the performance of the implementation that was carried out scales by 2× using two graphic cards in the same node. Notably, Symmetric Tridiagonal Eigenvalue Solvers are fundamental to solving more general eigenvalue problems. Additionally, the divide-and-conquer approach employed in this implementation can be extended to singular value solvers. Given the wide range of eigenvalue problems encountered in scientific and engineering domains, this work is essential in advancing computational methods for efficient and accurate matrix diagonalization.https://www.mdpi.com/2076-3417/14/22/10716Cuppen’s algorithmEigenvalue SolverGraphics Processing UnitHybrid-Heterogeneous computing |
| spellingShingle | Erika Hernández-Rubio Alberto Estrella-Cruz Amilcar Meneses-Viveros Jorge Alberto Rivera-Rivera Liliana Ibeth Barbosa-Santillán Sergio Víctor Chapa-Vergara Symmetric Tridiagonal Eigenvalue Solver Across CPU Graphics Processing Unit (GPU) Nodes Applied Sciences Cuppen’s algorithm Eigenvalue Solver Graphics Processing Unit Hybrid-Heterogeneous computing |
| title | Symmetric Tridiagonal Eigenvalue Solver Across CPU Graphics Processing Unit (GPU) Nodes |
| title_full | Symmetric Tridiagonal Eigenvalue Solver Across CPU Graphics Processing Unit (GPU) Nodes |
| title_fullStr | Symmetric Tridiagonal Eigenvalue Solver Across CPU Graphics Processing Unit (GPU) Nodes |
| title_full_unstemmed | Symmetric Tridiagonal Eigenvalue Solver Across CPU Graphics Processing Unit (GPU) Nodes |
| title_short | Symmetric Tridiagonal Eigenvalue Solver Across CPU Graphics Processing Unit (GPU) Nodes |
| title_sort | symmetric tridiagonal eigenvalue solver across cpu graphics processing unit gpu nodes |
| topic | Cuppen’s algorithm Eigenvalue Solver Graphics Processing Unit Hybrid-Heterogeneous computing |
| url | https://www.mdpi.com/2076-3417/14/22/10716 |
| work_keys_str_mv | AT erikahernandezrubio symmetrictridiagonaleigenvaluesolveracrosscpugraphicsprocessingunitgpunodes AT albertoestrellacruz symmetrictridiagonaleigenvaluesolveracrosscpugraphicsprocessingunitgpunodes AT amilcarmenesesviveros symmetrictridiagonaleigenvaluesolveracrosscpugraphicsprocessingunitgpunodes AT jorgealbertoriverarivera symmetrictridiagonaleigenvaluesolveracrosscpugraphicsprocessingunitgpunodes AT lilianaibethbarbosasantillan symmetrictridiagonaleigenvaluesolveracrosscpugraphicsprocessingunitgpunodes AT sergiovictorchapavergara symmetrictridiagonaleigenvaluesolveracrosscpugraphicsprocessingunitgpunodes |