S. Oliveira, A NEW PARALLEL CHASING ALGORITHM FOR TRANSFORMING ARROWHEAD MATRICES TO TRIDIAGONAL FORM, Mathematics of computation, 67(221), 1998, pp. 221-235
Rutishauser, Gragg and Harrod and finally H.Y. Zha used the same class
of chasing algorithms for transforming arrowhead matrices to tridiago
nal form. Using a graphical theoretical approach, we propose a new cha
sing algorithm. Although this algorithm has the same sequential comput
ational complexity and backward error properties as the old algorithms
, it is better suited for a pipelined approach. The parallel algorithm
for this new chasing method is described, with performance results on
the Paragon and nCUBE. Comparison results between the old and the new
algorithms are also presented.