Fast and Numerically Accurate Algorithms for Matrices with Displacement Structure

在科学和工程以及计算、应用和纯数学中的大量应用引起了涉及具有Toeplitz、Hankel、Toeplitz-Plus-Hankel、Vandermonde结构、可控性、能观性、Cauchy、Loewner、Pick、Schur-Cohn、Russ-Hurwitz矩阵、Bezoutians以及许多其他结构模式的矩阵的问题。标准数学软件工具(例如，MatLab、MathCad、Maple V、NAG库、LAPACK)基于标准(忽略结构)方法，因此它们的使用通常不适合于获得满意的解。这里有两个主要原因。首先，忽略结构会人为地平方数据的大小，这需要不必要的存储和极其大量的CPU时间。其次，许多结构矩阵，如Hankel，Pick，Hilbert，Vandermonde，都是病态的，这意味着所有可用的标准方法往往无法在计算解中产生一个正确的数字。本项目的主题是研究与Cauchy和Cauchy-like矩阵有关的几个理论和计算问题，这些问题出现在许多应用领域，包括信号处理、系统理论H-无穷控制。位移结构的概念表明，类柯西矩阵的算法可以用来设计许多其他重要的结构矩阵的实用算法，如Toeplitz、Hankel、Toeplitz-plus-Hankel、Vandermonde、Chebyshev-Vandermonde矩阵等，实际上，所有这些矩阵都可以通过应用几个快速的傅立叶、余弦正弦变换来变换成类Cauchy矩阵。它计划扩展结果，为新的结构矩阵类开发快速和数值准确的算法。***

Numerous applications in sciences and engineering, as well as in computational, applied and pure mathematics give rise to problems involving matrices with Toeplitz, Hankel, Toeplitz-plus-Hankel, Vandermonde structures, controllability, observability, Cauchy, Loewner, Pick, Schur-Cohn, Routh-Hurwitz matrices, Bezoutians, along with many other patterns of structure. standard mathematical software tools (e.g., MATLAB, MathCad, Maple V, NAG library, LAPACK), are based on standard (structure-ignoring) methods, and therefore their use is often not appropriate for obtaining a satisfactory solution. Here are two major reasons. First, ignoring the structure artificially squares the size of the data, which requires unnecessary storage and an extremely large amount of CPU time. Secondly, many structured matrices, e.g. Hankel, Pick, Hilbert, Vandermonde, are extremely ill- conditioned, which means that all available standard methods often fail to produce even one correct digit in the computed solution. The theme of this project is the study of several theoretical and computational problems related to Cauchy and Cauchy-like matrices, which arise in many applied areas, including signal processing, system Theory H-infinity control. Use of the concept of displacement structure suggests that algorithms for Cauchy-like matrices can be used to design efficient practical algorithms for many other important kinds of structured matrices, such as Toeplitz, Hankel, Toeplitz-plus- Hankel, Vandermonde, Chebyshev-Vandermonde matrices, etc. In fact, all these matrices can be transformed into Cauchy-like matrices just by applying a few fast Fourier, cosine of sine transforms. It is planned to extend the results to develop fast and numerically accurate algorithms for new classes of structured matrices. ***