A fast stable algorithm for frequency response problems

Frequency response problems (FRPs) are important computations in control theory and engineering applications. The task requires computing the transfer function of a linear system at different frequencies. First one reduces the linear system to a compact form and then one evaluates the transfer function at a large sample of frequencies. Current practice reduces the system to Hessenberg form. At the second stage one solves a Hessenberg system of linear equations at every frequency. For an n by n system, this method requires $O(n\sp2)$ effort at each frequency. This dissertation presents a new modification of the Lanczos algorithm that preserves stability and produces a reduced matrix that is not quite tridiagonal. It has extra rows and/or columns whenever an instability occurs in the standard Lanczos algorithm. The new form resembles the backbones of a fish. The main feature is that the arithmetic effort of the new solution is approximately $10\over n$ times the arithmetic effort of the standard solution.