Optimized look-ahead recurrences for adjacent rows in the Padé table (Q1914867): Difference between revisions

The recursive solution of a nested set of Toeplitz systems is done by the Levinson or Schur algorithm in the Hermitian positive definite case; by nonsymmetric versions of these when the matrices are non-Hermitian but strongly regular; by look-ahead versions in exact arithmetic and by stable look-ahead versions when numerical rounding occurs. These algorithms compute recursively the solutions on two adjacent rows in a Padé table, that is when the denominator of the rational approximant is increased, keeping the numerator degree constant. Padé approximant should be considered in broad sense, i.e. Padé approximant of a Laurent series or Padé approximant in two points. In the case of a matrix which is not strongly regular, submatrices become singular when a so-called singular block is reached in the Padé table. Jumping over such a block (i.e., finding the solution for the next nonsingular submatrix) with the minimal amount of work can be complicated. Moreover, if the submatrix is nonsingular, but very ill-conditioned, it should be avoided as well because computing a solution there could introduce large rounding errors. Thus recurrences are used which allow to jump over several blocks simultaneously. Algorithms of this type were published before by \textit{T. F. Chan} and \textit{P. C. Hansen} [IEEE Trans. Signal Processing 40, No. 5, 1079-1090 (1992; Zbl 0756.65044)], \textit{R. W. Freund} and \textit{H. Zha} [Linear Algebra Appl. 188-189, 255-303 (1993; Zbl 0777.65011)] by \textit{R. W. Freund} [Numer. Math. 68, No. 1, 35-69 (1994; Zbl 0811.65023)]\ and by the authors [ibid. 70, No. 2, 181-227 (1995; Zbl 0823.65023)]. The optimization mentioned in the title refers to the fact that the present algorithm always takes the smallest possible look-ahead steps. Therefore, it alternates between the Levinson/Schur type algorithm and a sawtooth algorithm. The updating links well-conditioned pairs which are either regular (different neighbouring solutions on a diagonal) or column-regular (different neighbouring solutions on a column). With some extra computations, one can obtain from the same algorithm the (block) \(LDU\) decompositions of the Toeplitz matrix or its inverse. The paper describes only the basic formulas. Implementation details are not given.