arXiv:2610.39990 · v1
An Exact Parallel Dense Gauss-Seidel Algorithm with Trade-Offs between Parallel Execution Time and Preprocessing Time
摘要
The Gauss-Seidel iterative method is commonly used for solving systems of linear equations because of its good convergence properties. However, the Gauss-Seidel algorithm cannot be easily parallelized because of the data dependencies existing at each iteration. The best parallel execution time for dense systems of equations is $O(n)$ given that enough processors are available and no preprocessing is performed. In this paper we propose a new parallel Gauss-Seidel algorithm which is capable of achieving better parallel runtimes at the expense of more preprocessing time. The algorithm can be tuned in order to provide convenient trade-offs between the preprocessing time and the best parallel runtime achievable by the algorithm.
作者备注：This manuscript was originally written in July 2013, and the names and affiliation of the authors are reflecting the state at that time. Recently, the original manuscript went through a few rounds of AI-based reviews, which identified several typos and bugs, which were corrected, but which didn't change the original ideas. AI was only used for identifying issues, not for correcting them