Matt, Urs vonStewart, G. W.A rounding error analysis is presented for a divide-and-conquer algorithm to solve linear systems with block Hessenberg matrices. Conditions are derived under which the algorithm computes a backward stable solution. The algorithm is shown to be stable for diagonally dominant matrices and for M-matrices. (Also cross-referenced as UMIACS-TR-94-105)en-USTechnical Report