Block SOR methods for the solution of indefinite least squares problems (Q2017963)

The indefinite least squares problem is to minimize \((b-Ax)^TS(b-Ax)\) over \(x\) with signature \(S=I_p\oplus -I_q\), \(p+q=m\) and \(A=(A_1^T, A_2^T)^T\) with \(A_1\in\mathbb{R}^{p\times n}\) of full rank and \(A_2\in\mathbb{R}^{q\times n}\). For large and sparse \(A\), iterative methods are preferred. The normal equations are equivalent to a block system whose diagonal blocks \(A_1^TA_1\), \(-I_q\) and \(I_n\) are all nonsingular. Two block successive overrelaxation (SOR) algorithms are given to solve this: a 3-block version using the three blocks and a 2-block version where the first two are considered as one block. They both only involve a skinny QR factorization of \(A_1\) and allow efficient iteration steps. Convergence is proved for both and their optimal SOR parameter \(\omega\) is derived. In practice, \(\omega\) can be chosen from some small intervals. The methods behave in a similar way and they are generally more effective than block Jacobi or Gauss-Seidel methods as numerical experiments show.