The Instability of Parallel Prefix Matrix Multiplication
Roy Mathias · SIAM Journal on Scientific Computing · 1995
It is shown that when parallel prefix is used to compute the leading principal minors of a tridiagonal matrix T within a bisection algorithm to compute the eigenvalues of T the relative error in the computed eigenvalues can be as great as $\epsilon \kappa ^3 $, where $\epsilon $ is machine precision and $\kappa $ is the condition number for the problem of computing the eigenvalues of T. An ideal algorithm, like serial bisection, would have forward error $\epsilon \kappa $. Forward and backward error bounds for the computed leading principal minors are given. Also, error bounds for the parallel prefix computation of the partial products of a sequence of matrices are given and some applications to other related problems in numerical linear algebra, including the parallel implementation of the differential qd algorithm, are presented.