SORbased

SORbased refers to methods and algorithms that are built on the Successive Over-Relaxation (SOR) technique. SOR is a stationary iterative method used to solve linear systems Ax = b, by extending Gauss-Seidel with a relaxation factor ω chosen to accelerate convergence. The term is commonly applied to approaches that implement or optimize this idea directly in the iteration.

Convergence for SOR depends on the properties of the coefficient matrix A. For symmetric positive definite matrices, SOR converges when 0 < ω < 2, with an optimal ω typically between 1 and 2 that minimizes the spectral radius of the iteration matrix. For general matrices, convergence is not guaranteed and performance can vary significantly with problem structure. The choice of ω is problem dependent and often determined empirically or via spectral analysis.

Algorithmically, SOR modifies the standard Gauss-Seidel update by blending the latest updated components with the previous iterate, using the relaxation factor. A common formulation updates each component i as x_i^{k+1} = (1 − ω) x_i^k + ω x_i^{GS}, where x_i^{GS} is the Gauss-Seidel value computed from the newest available components. This can also be expressed in matrix form through a decomposition of A and leads to variants such as line, block, or multicolor versions to improve computational behavior on certain architectures.

Applications and considerations: SOR-based methods are often used for large, sparse linear systems arising from discretized partial differential equations and structural problems. They can be effective when the matrix has suitable spectral properties, but their sequential character can limit parallelism. Variants like SSOR (symmetric SOR) and SOR-based preconditioners are employed to enhance convergence in conjunction with Krylov methods.