Backward error analysis of the AllReduce algorithm for Householder QR decomposition (Q692038)

The authors give an error analysis of the AllReduce algorithm for the Householder QR decomposition of tall and skinny matrices. They derive bounds on the backward error and the deviation from orthogonality of the computed Q factor. It is shown that the bounds are smaller than in other QR algorithms and they decrease as the level of recursion increases. Computational results are given in support of the theoretical results. Thus the authors have shown that the all reduce algorithm can be used reliably in a parallel environment.