An Accelerated Symmetric Gauss‐Seidel Algorithm for a Linear System of Equations

ABSTRACT This paper introduces an accelerated symmetric Gauss‐Seidel (asGS) algorithm for solving large‐scale linear systems. Our approach is fundamentally rooted in optimization theory. By rigorously establishing the intrinsic relationship between the symmetric Gauss‐Seidel (sGS) iteration and the proximal gradient method in convex composite quadratic optimization, we integrate the Accelerated Proximal Gradient (APG) framework with the sGS algorithm. This theoretical foundation enables a significant improvement in convergence rate. Furthermore, we develop a novel matrix augmentation technique that extends the asGS algorithm to handle asymmetric linear systems by embedding them into a higher‐dimensional symmetric positive definite (SPD) system. This systematic extension distinguishes our approach from conventional Gauss‐Seidel variants, which typically require specialized treatments for asymmetric cases. Numerical experiments demonstrate that the proposed asGS algorithm substantially reduces the number of iterations and computational time compared to classical Gauss‐Seidel methods, especially for large‐scale problems. The optimization‐theoretic perspective adopted in this work provides a principled and distinct pathway for accelerating Gauss‐Seidel‐type methods, complementing existing lines of research. In scenarios with memory constraints or requirements for deterministic execution times, asGS provides a viable and efficient alternative to traditional Krylov subspace methods.