| We outline the displacement rank approach with structured matrices in a unified way based on their association with the displacement operators, and then focus on its most fundamental stage of the inversion of the displacement operators. We show a general method for obtaining such expressions that works for all displacement operators, and thus provides foundation for the displacement rank approach to practical computations with structured matrices. We also apply our techniques to specify the expressions for various important classes of matrices, including the ones of the confluent matrices associated with the tangential Nevanlinna-Pick problems, which enables acceleration of the known solution algorithms. We substantially improve the known estimates for the nouns of the inverse displacement operators, which are critical numerical parameters for computations based on the displacement approach.; The classical and intensively studied problem of solving a structured linear system of equations is omnipresent in computations in sciences, engineering and signal processing. We use Newton's iteration to compute numerically the inverse of a structured matrix because of the strong numerical stability, local quadratic convergence, and convenience for parallel implementation. We propose two methods on controlling the growth of displacement rank in the iteration. These methods need good initial approximations, which we can find by combining the preconditioned conjugate gradient method and the homotopy method. Exploiting the structure of Toeplitz-like matrices, we combine the MBA algorithm with p-adic lifting for the exact inversion of an integer Toeplitz-like matrix. We accelerate the known algorithms for computing a selected entry of the extended Euclidean algorithm for integers. Consequently, we accelerate the largest singular value computation by using our algorithm to solve the rational number reconstruction problem. |
