Efficient and stable solution of structured Hessenberg linear systems arising from difference equations

This paper is concerned with the efficient solution of (block) Hessenberg linear systems whose coefficient matrix is a Toeplitz matrix in (block) Hessenberg form plus a band matrix. Such problems arise, for instance, when we apply a computational scheme based on the use of difference equations for the computation of many significant special functions and quantities occurring in engineering and physics. We present a divide‐and‐conquer algorithm that combines some recent techniques for the numerical treatment of structured Hessenberg linear systems. Our approach is computationally efficient and, moreover, in many practical cases it can be shown to be componentwise stable. Copyright © 2000 John Wiley & Sons, Ltd.