No label defined (Q4463369)

The column-decomposed accelerated over-relaxation (CDAOR) method is a stationary iterative method for solving linear least-squares problems of the form \[ \min\limits_x \| Ax - b\| _2, \] where the \(m \times n\) matrix \(A\) is assumed to have full column rank. The basic idea of CDAOR is to consider a block column partitioning of \(A\) and to solve the least-squares problems belonging to the block columns successively. CDAOR depends upon two parameters \(\gamma\) and \(\omega\), which can be chosen to control its convergence, and the authors provide \(12\) different, sufficient convergence conditions. Moreover, particular choices of \(\gamma\) and \(\omega\) lead to simplified methods called column-decomposed successive over-relaxation (CDSOR), Gauss-Seidel (CDGS), and Jacobi (CDJ). All these methods are mathematically equivalent to the corresponding accelerated overrelaxation methods for solving the normal equations \(A^T A x = A^T b\). However, as the methods described in this paper exploit this relationship only implicitly they are likely to be exempt from certain numerical difficulties associated with the normal equations approach. This is illustrated by a \(3\times 2\) example. Also, a parallel version of CDAOR is described. It should be noted that similar methods have been studied before, see, e.g., \textit{J. E. Dennis} and \textit{T. Steihaug} [SIAM J. Numer. Anal. 23, 717--733 (1986; Zbl 0614.65059)].