PCR algorithm for parallel computing minimum-norm (T) least-squares (S) solution of inconsistent linear equations

摘要

This paper presents a new highly parallel algorithm for computing the minimum-norm (T) least-squares (S) solution of inconsistent linear equations Ax=b(A∈Rm×nr,b∉R(A)). By this algorithm the solution x=AS,T+b is obtained in T=(1+m)(1+log2m)+n(6+log2(n−r+1)+log2m+log2n)−r(1+log2n) steps with P=mn processors when m⩾2(n−1) and with P=2n(n−1) processors otherwise.