CAREER: Structured Matrix Computations: Foundations, Methods, and Applications

拟议的研究涉及创新的和系统的结构化矩阵计算。大规模矩阵在数学计算和工程模拟中经常出现。通过利用固有的结构，人们经常可以开发出新的快速和可靠的矩阵方法。这项工作尤其对秩结构和数据稀疏矩阵感兴趣，以及将它们用于解决实际数值问题(特别是高维离散化问题)的创新想法。PI建议提高结构化方法的灵活性和适用性。将包括对结构和方法的系统分析。将研究以下几个方面：(1)秩属性和新的嵌套层次结构的理论基础；(2)探索矩阵结构的新视角，如无矩阵的结构化稀疏分解、因式分解更新、嵌套局部化和稀疏化；(3)有效的秩结构矩阵算法、它们的分析以及它们在大型线性系统、最小二乘问题、特征值问题、离散化的偏微分方程组和大量工程应用中的应用。矩阵计算是大多数科学计算任务的核心。这项研究将系统地将经典的稠密和稀疏矩阵计算扩展到数据稀疏计算，并将新的结构化矩阵理论和技术引入科学和工程计算。该项目将导致揭示和使用结构的实用方法，这将进一步产生快速和可靠的算法，如稳定的直接三维偏微分方程组解算器，具有近线性的复杂性。了解这些结构还将为解决数值解中的经典挑战提供新的视角，例如大填充、病态、缺乏显式矩阵和具有高度可变参数的重复解。所提出的算法可用于许多复杂的数值问题，如偏微分方程组的求解、地震成像、信号处理、纳米结构建模和VLSI电路模拟。这项工作将为不同领域的研究人员提供多学科参与的机会。该项目将产生用于实际应用的免费开放源码包，以及能够激发来自不同背景的学生的兴趣和成就的教育推广计划的课程和教程和测试材料。

The proposed research is concerned with innovative and systematic structured matrix computations. Large-scale matrices arise frequently in mathematical computations and engineering simulations. By exploiting the inherent structures, one can often develop new fast and reliable matrix methods. This work is especially interested in rank structures and data-sparse matrices, as well as innovative ideas of using them in the solutions of practical numerical problems (especially high dimensional discretized problems). The PI proposes to enhance both the flexibility and the applicability of structured methods. Systematic analysis for the structures and the methods will be included. The following aspects will be studied: (1) theoretical foundations of rank properties and new nested hierarchical structures; (2) new perspectives for exploring matrix structures, such as matrix-free structured sparse factorization, factorization update, and nested localization and sparsification; (3) efficient rank structured matrix algorithms, their analysis, and their use in fast solutions of large linear systems, least squares problems, eigenvalue problems, discretized PDEs, and numerous engineering applications.Matrix computations lie at the heart of most scientific computation tasks. This research will systematically extend classical dense and sparse matrix computations to data-sparse ones, and will introduce new structured matrix theories and techniques into scientific and engineering computations. The project will result in practical ways to reveal and use structures, which will further yield fast and reliable algorithms such as stable direct three dimensional PDE solvers with nearly linear complexity. Understanding the structures will also provide new perspectives to classical challenges in numerical solutions, such as large fill-in, ill conditioning, lack of explicit matrices, and repeated solutions with highly varying parameters. The proposed algorithms can be used (say, as kernel solvers) in many complex numerical problems such as PDE solution, seismic imaging, signal processing, nanostructure modeling, and VLSI circuit simulation. The work will provide a multidisciplinary opportunity for researchers in different areas to participate. The project will result in freely available open source packages for practical applications, as well as courses ad tutorial and test materials for educational outreach programs that can stimulate the interest and achievement of students from diverse backgrounds.