DIAGONAL PIVOTING FOR PARTIALLY RECONSTRUCTIBLE CAUCHY-LIKE MATRICES,WITH APPLICATIONS TO TOEPLITZ-LIKE LINEAR-EQUATIONS AND TO BOUNDARY RATIONAL MATRIX INTERPOLATION PROBLEMS

In an earlier paper we exploited the displacement structure of Cauchy- like matrices to derive for them a fast O(n(2)) implementation of Gaus sian elimination with partial pivoting. One application is to the rapi d and numerically accurate solution of linear systems with Toeplitz-li ke coefficient matrices, based on the fact that the latter can be tran sformed into Cauchy-like matrices by using the fast Fourier, sine, or cosine transform. However, symmetry is lost in the process, and the al gorithm given is not optimal for Hermitian coefficient matrices. In th is paper we present a new fast O(n(2)) implementation of symmetric Gau ssian elimination with partial diagonal pivoting for Hermitian Cauchy- like matrices, and show how to transform Hermitian Toeplitz-like matri ces to Hermitian Cauchy-like matrices, obtaining algorithms that are t wice as fast as those in the earlier work. Numerical experiments indic ate that in order to obtain not only fast but also numerically accurat e methods, it is advantageous to explore the important case in which t he corresponding displacement operators have nontrivial kernels; this situation gives rise to what we call partially reconstructible matrice s, which are introduced and studied in the present paper. We extend th e transformation technique and the generalized Schur algorithms (i.e., fast displacement-based imple mentations of Gaussian elimination) to partially reconstructible matrices. We show by a variety of computed e xamples that the incorporation of diagonal pivoting methods leads to h igh accuracy. We focused in this paper on the design of new numericall y reliable algorithms for Hermitian Toeplitz-like matrices. How ever, the proposed algorithms have other important applications; in particul ar, we briefly describe how they recursively solve a boundary interpol ation problem for J-unitary rational matrix functions.