Seminar of Scientific Department of Computational Physics

Systems of linear algebraic equations (SLAEs) with band coefficient matrices arise in many scientific, engineering, and real-time applications, often accounting for most of the computation time in finite element and finite difference problems. Developing efficient algorithms for solving such systems is therefore an important task.

This work builds on the parallel partition algorithm for tridiagonal SLAEs proposed by Austin et al., LA-VR-03-4149 (2004), originally designed for systems with up to 250 processors. The algorithm was implemented in CUDA with a number of optimisations, including ML-based heuristics for determining the optimum number of CUDA streams, sub-system size, and number of recursive steps. The algorithm was subsequently extended to handle multiple right-hand sides, implemented as a multi-GPU solver, and generalised to pentadiagonal and heptadiagonal SLAEs; performance analysis was carried out at every stage.

Symbolic algorithms for SLAEs with band matrices were also developed, resolving the correctness issue characteristic of classical Thomas-method-type algorithms without imposing any constraints on the characteristics of the coefficient matrix; the correctness conditions for the algorithms were formulated and proven as theorems.

Finally, an algorithm for solving the initial-boundary value problem for the heat equation, describing the thermal processes in working gas supply devices for an ion source, was developed and implemented in CUDA. The algorithm is based on the alternating direction implicit (ADI) method, which yields tridiagonal systems at each half-step. For numerical simulation, four approaches to solving tridiagonal systems were implemented in CUDA: the Thomas method, two-sided Thomas method, the partition method, and the cuSPARSE solver. Performance analysis was carried out and presented for all algorithms on the HybriLIT platform.