PCR algorithm for the parallel computation of the solution of a class of singular linear systems

摘要

The paper presents a new highly parallel algorithm for computing the solution of a class of singular linear systemsWAWx=b,b∈R((WA)k2),x∈R((AW)k1).By the algorithm the solution x = Ad,Wb is obtained in T=m{7+⌈log2n⌉+(1+⌈log2m⌉)2+⌈log2(m-r+1)⌉}+⌈log2mn⌉ steps with P = mn processors when n ⩾ 2(m − 1) and with P = 2m(m − 1) processors otherwise.