Diagonal pivoting for partially reconstructible Cauchy-like matrices, with applications to Toeplitz-like linear equations and to boundary rational matrix interpolation problems (Q677917)

In an earlier paper [Integral Equations Oper. Theory 22, No. 1, 65-92 (1995; Zbl 0824.15028)], the authors designed a fast \(O(n^2)\) Gaussian elimination with partial pivoting algorithm for Cauchy-like matrices, and described a new fast Toeplitz-like solver called GKO. In the present paper, they focus on Hermitian matrices, and describe a fast \(O(n^2)\) symmetric Gaussian elimination, with diagonal pivoting, for partially reconstructible Cauchy-like matrices. On the basis of extensive testing, they found several numerically accurate algorithms that are about twice as fast as the original GKO algorithm (which does not preserve symmetry). The high accuracy of these new algorithms is achieved by allowing the corresponding displacement equations to have nontrivial kernels (i.e., nontrivial null-spaces). An application of these algorithms combined with diagonal pivoting to accurate recursive solution of certain boundary homogeneous interpolation problem is also described.