Fast and Accurate Algorithms for Structured Matrix Computations

在科学、工程和数学中的大量应用产生了涉及结构矩阵的问题，例如Toeplitz、Hankel、Vandermonde、可控性、能观性、柯西、Bezoutians以及许多其他结构模式。在许多这样的应用中，使用标准的数学软件工具(如MatLab、数学、Maple、LAPACK等)。这是不合适的，因为它们忽略结构需要不必要的存储以及极其大量的CPU时间。其次，许多结构矩阵，如Hankel，Pick，Hilbert，Vandermonde，都是病态的，以至于所有可用的标准方法往往无法在计算解中产生甚至一个正确的数字。这个项目的目标是研究与结构矩阵相关的理论和计算问题，这些问题出现在几个应用领域，包括信号和图像处理、系统论和控制理论。在有理矩阵插值和范数约束逼近问题、高斯求积问题以及信号和图像处理中出现的几类新的结构矩阵，将开发出新的精确、快速和超快的算法。与这些直接方法一起，该方法将被用来设计新的基于离散实数变换的预条件算子，以加速块Toeplitz-Plus-Hankel矩阵的共轭梯度法的收敛。

Numerous applications in sciences, engineering and mathematics give rise to problems involving structured matrices such as Toeplitz, Hankel, Vandermonde, controllability, observability, Cauchy, Bezoutians, along with many other patterns of structure. In many of these applications the use of standard mathematical software tools (such as MATLAB, Mathematica, Maple, LAPACK, etc.) is not appropriate, because their ignoring of structure requires unnecessary storage as well as an extremely large amount of CPU time. Secondly, many structured matrices, e.g., Hankel, Pick, Hilbert, Vandermonde, are extremely ill- conditioned, so that all available standard methods often fail to produce even one correct digit in the computed solution. The objective of this project is the study of theoretical and computational problems related to structured matrices which arise in several applied areas, including signal and image processing, system theory, and control theory. New accurate fast and superfast algorithms will be developed for several new classes of structured matrices, arising in rational matrix interpolation and approximation problems with norm constraints, in Gaussian quadrature as well as in signal and image processing. Along with these direct methods, the approach will be used to design new classes of preconditioners based on discrete real transforms to speed- up the convergence of the conjugate gradient method for block Toeplitz-plus-Hankel matrices.