Parallel projected aggregation methods for solving large inconsistent systems

Abstract

The Projected Aggregation Methods (PAM) for solving linear systems of equali- ties and/or inequalities, generate a new iterate xk+1 by projecting the current point xk onto a separating hyperplane generated by a given linear combination of the original hyperplanes and/or halfspaces. In [9, 16, 17, 18] we introduced acceleration schemes for solving linear systems within a PAM like framework. The basic idea was to force the next iterate to belong to the convex region de ned by the new separating/or aggregated hyperplane computed in the previous iteration. In this paper we extend the above mentioned methods to the problem of nding the least squares solution to inconsistent systems. In the new algorithm we used a scheme of incomplete alternate projections for minimizing the proximity function, similar to the one of Csisz ar y Tusn ady described in [4] which uses exact projections. The parallel simultaneous projection ACCIM algorithm in [16] is very eÆcient for ob- taining approximations with suitable properties, and is the basis for calculating the incomplete intermediate projections. We discuss the convergence properties of the new algorithm and also present numerical experiences obtained by applying it to image reconstruction problems using the SNARK93 system [3].