Implementing a Cholesky decomposition using SYCL

Abstract

PLSSVM, an LS-SVM implementation, now only uses the Conjugate Gradient algorithm for solving a set of linear equations. However, for an ill-conditioned matrix, it especially gets into trouble, as the converged solution drifts away from the actual solution due to rounding errors. Therefore, this thesis implements a different solver, e.g., the Cholesky Decomposition, which will be implemented in SYCL. We will implement multiple variations of the Cholesky Decomposition algorithm, including a blocked version, and utilize many different features of SYCL. The focus will primarily be on the fastest implementations. In the end, the fastest implementation will be integrated into PLSSVM alongside a Forward and Backward Substitution implementation for solving the set of linear equations. We will conclude with a runtime comparison between the implementations, a comparison of our best Cholesky Decomposition with the Conjugate Gradient using a dataset and a small discussion about numerical errors.

PLSSVM, eine LS-SVM-Implementierung, verwendet jetzt nur noch den Conjugate Gradient Algorithmus zur Lösung eines Satzes linearer Gleichungen. Bei einer schlecht konditionierten Matrix gerät es jedoch besonders in Schwierigkeiten, da die konvergierte Lösung aufgrund von Rundungsfehlern von der tatsächlichen Lösung abweicht. Daher implementiert diese Thesis einen anderen Solver, z.B. die Cholesky-Zerlegung, die in SYCL implementiert wird. Wir werden mehrere Variationen des Cholesky-Zerlegungsalgorithmus implementieren, einschließlich einer blockierten Version und viele verschiedene Funktionen von SYCL nutzen. Der Schwerpunkt wird hauptsächlich auf den schnellsten Implementierungen liegen. Am Ende wird die schnellste Implementierung in PLSSVM integriert, zusammen mit einer Forward- und Backward Substitution zur Lösung des Satzes linearer Gleichungen. Wir werden mit einem Laufzeitvergleich zwischen den Implementierungen, einem Vergleich unserer besten Cholesky-Zerlegung mit dem Conjugate Gradient unter Verwendung eines Datensatzes und einer kurzen Diskussion über numerische Fehler abschließen.