Numerical Solution of Large-Scale Sparse Linear Systems Arising from Problems with Constraints

由约束问题引起的大规模稀疏线性系统的数值求解

• 批准号: RGPIN-2017-04491
• 负责人: Greif, Chen
• 金额: $ 3.06万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=710475
• 关键词: Numerical; Solution; Large; Scale; Sparse

Recent advances in computational science and engineering, combined with the availability of increased computing power and new computational paradigms, require experts in the scientific computing domain to develop new algorithms and methodologies for solving problems that are larger than ever before, and whose features must be exploited in order to be able to generate robust, efficient, and reliable numerical solution techniques. This proposal aims to take on these challenges for the numerical solution of structured linear systems that arise throughout the computation of a large variety of problems with constraints. Linear systems that arise from problems with constraints are highly structured, yet they are notorious for being difficult to solve. Modern methods are based on model reduction techniques (namely, the attempt to turn the original problem into a smaller problem that maintains most of the original properties). For linear algebra problems arising from problems with constraints, preserving the structure and other attributes is critical and it presents a significant challenge. My primary goal will be to develop fast and robust solvers, which are scalable and respect the structure. To accomplish this goal, I will aim to generate a unified framework for a variety of problems from the area of constrained optimization and numerical solution of partial differential equations. Attributes such as symmetry, matrix rank property, and spectral distribution, to name just a few, should be explored and exploited for this mission to be successful. An equally important goal will be to develop numerical software for scalable, flexible, and portable solvers that allow for solving large-scale problems. There are many relevant applications here and many connections to other areas. Primarily, any problem that can be posed as a constrained optimization problem requires solving linear systems of the form discussed in this proposal. Problems in machine learning, computer graphics, robotics, medical imaging, and many other computational areas, provide a rich source. In addition, the numerical solution of partial differential equations provides a large collection of problems with constraints, too; computational electromagnetics or fluid dynamics are just two examples. Altogether, the large collection of problems to be solved and the importance of dealing efficiently with large-scale problems, make this area of research extremely active and important. Given the large number of applications that lead to mathematical models with constraints, and given the increasing amounts of data that our society needs to deal with, advances in fast numerical solvers for the problems concerned in this proposal may have a significant positive impact in computational science and engineering.

计算科学和工程的最新进展，加上计算能力的提高和新计算范式的可用性，要求科学计算领域的专家开发新的算法和方法来解决比以往任何时候都更大的问题，并且必须利用其特征以便能够生成强大、高效和可靠的数值求解技术。这个建议的目的是采取这些挑战的结构化线性系统的数值解，出现在整个计算的各种各样的问题的约束。 由约束问题产生的线性系统是高度结构化的，但它们以难以解决而闻名。现代方法基于模型简化技术（即试图将原始问题转化为保持大部分原始属性的较小问题）。对于由约束问题产生的线性代数问题，保持结构和其他属性是至关重要的，它提出了一个重大的挑战。 我的主要目标将是开发快速和强大的求解器，这是可扩展的，并尊重结构。为了实现这一目标，我将致力于从约束优化和偏微分方程数值解领域为各种问题生成一个统一的框架。属性，如对称性，矩阵秩属性，光谱分布，仅举几例，应该探索和利用这个使命是成功的。一个同样重要的目标将是开发可扩展的，灵活的，可移植的求解器，允许解决大规模的问题的数值软件。 这里有许多相关的应用程序，并与其他领域有许多联系。首先，任何可以作为约束优化问题提出的问题都需要求解本提案中讨论的形式的线性系统。机器学习、计算机图形学、机器人技术、医学成像和许多其他计算领域的问题提供了丰富的来源。此外，偏微分方程的数值解也提供了大量的约束问题;计算电磁学或流体动力学只是两个例子。总而言之，大量的问题需要解决，有效地处理大规模问题的重要性，使这一领域的研究非常活跃和重要。 鉴于大量的应用程序，导致数学模型的约束，并考虑到越来越多的数据，我们的社会需要处理，在快速数值求解器的进步，在这个建议中所涉及的问题可能会有一个显着的积极影响计算科学和工程。