Fast and Accurate Algorithms for Structured Matrix Computations

快速准确的结构化矩阵计算算法

• 批准号: 9732355
• 负责人: Vadim Olshevsky
• 金额: $ 14.09万
• 依托单位: Georgia State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-07-01 至 2001-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9732355&HistoricalAwards=false
• 关键词: Fast; Accurate; Algorithms; Structured; Matrix

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.

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