A projection method for semidefinite linear systems and its applications (Q1888336)

The solution \(x\) of a linear system \(Ax=b\) with an \(n\times n\) matrix \(A\) can be seen as the vector in the intersection of the hyperplanes \(\langle A^T e_j, x \rangle = \langle e_j , b\rangle\), where \(e_j\) denotes the \(j\)th unit vector of length \(n\). Consequently, the block-iterative projection algorithm, a method for determining vectors in the intersection of a family of convex sets, yields a suitable approach for solving linear systems. In the first part of this paper, several flavors of this approach are considered, including a least-squares variant for rectangular matrices based on the normal equations. The second part is concerned with a general framework of subspace projection algorithms for solving a consistent linear system of the form \(Gx = c\), where \(G\) is a symmetric positive semidefinite matrix. It is shown that this framework includes a number of existing and seemingly new algorithms.