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

提出的研究涉及创新和系统的结构化矩阵计算。大规模矩阵在数学计算和工程模拟中经常出现。利用固有结构，往往可以开发出新的快速可靠的矩阵方法。这项工作对秩结构和数据稀疏矩阵特别感兴趣，以及在实际数值问题（特别是高维离散问题）的解决中使用它们的创新思想。PI建议提高结构化方法的灵活性和适用性。系统的分析结构和方法将包括在内。本文将从以下几个方面进行研究：(1)秩性质的理论基础和新的嵌套层次结构；(2)探索矩阵结构的新视角，如无矩阵的结构化稀疏分解、分解更新、嵌套定位和稀疏化；(3)高效秩结构矩阵算法，它们的分析，以及它们在快速求解大型线性系统、最小二乘问题、特征值问题、离散偏微分方程和众多工程应用中的应用。矩阵计算是大多数科学计算任务的核心。本研究将系统地将经典的密集稀疏矩阵计算扩展到数据稀疏矩阵计算，并将新的结构化矩阵理论和技术引入科学和工程计算中。该项目将带来揭示和使用结构的实用方法，这将进一步产生快速可靠的算法，例如具有接近线性复杂性的稳定的直接三维PDE求解器。了解这些结构也将为数值解中的经典挑战提供新的视角，例如大填充、不良条件、缺乏显式矩阵以及具有高度变化参数的重复解。所提出的算法可用于许多复杂的数值问题，如PDE解、地震成像、信号处理、纳米结构建模和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.