Exact linear algebra, polynomial systems and applications of computer algebra

精确线性代数、多项式系统及计算机代数应用

• 批准号: RGPIN-2020-04276
• 负责人: Labahn, George
• 金额: $ 4.01万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750207
• 关键词: Exact; linear; algebra; polynomial; systems

Computer algebra systems are vital tools for scientists and engineers. They contain a vast store of mathematical knowledge and  provide abilities to manipulate  expressions to expand this knowledge using both exact and extended precision numerics.  Efficient algorithms in exact arithmetic and correct algorithms in numeric arithmetic are key components in these systems. This proposal naturally falls into two parts, (1) fast algorithms for symbolic linear algebra  and (2) applications of symbolic computation. The second theme is equally divided into (i) algorithms for reduction of invariant polynomial and dynamical systems and (ii) algorithms for determining identities and solutions for multiple definite summation and integration. In the first part we will pay particular attention to algorithms for faster integer and polynomial matrix arithmetic, something at the heart of modern symbolic computation systems.  In particular we will look at  matrix normal forms, order bases and their uses for fast matrix polynomial arithmetic along with their applications.  As an example, there are computations in algebraic combinatorics which requires fast order basis computation to determine D-finiteness of specific formal power series originating from analysis of algorithms. Problems and challenges which arise includes linear algebra with matrices or matrix polynomials having parameters, one where the matrix properties change depending on specific values of the parameters. Also matrices of integers or matrices of polynomials, where the growth of coefficient arithmetic  is a fundamental concern for efficient algorithms.  Finally,  while symbolic algorithms typically use exact arithmetic,  it is often the case that applications are described in terms of exact algebra but actually work with numeric, floating point coefficients coming from measured data. This is the case, for example, in linear systems theory or control theory, both of which make use of the algebraic formalism of matrix polynomial arithmetic. One then needs to address efficiency and at the same time numerical stability. The second part of this proposal focuses on the use of computer algebra  in applications, particularly those which make significant use of linear or polynomial algebra.  In the case of invariant polynomial and dynamical systems we wish to improve the algorithms used to reduce these systems in the presence of symmetries, something which occurs naturally in nature. Specifically one computes invariants and makes use of these to find simpler systems and which in turn provide efficient methods of solving  the original systems.   In the case of summation and integration, we intend to find new, improved algorithms for constructing reduction algorithms for creative telescoping, a method for finding or verifying summation and definite integration formulas.  Software has always been an important component of our research as it enables one to verify that theory agrees with practice.

计算机代数系统是科学家和工程师的重要工具。它们包含了大量的数学知识，并提供了使用精确和扩展精度数值来处理表达式以扩展这些知识的能力。精确算术中的高效算法和数值算术中的正确算法是这些系统中的关键组件。这一建议自然分为两部分，(1)符号线性代数的快速算法；(2)符号计算的应用。第二个主题被平均地分为(I)不变多项式和动力系统的约化算法和(Ii)确定多个定和和积分的恒等式和解的算法。在第一部分中，我们将特别关注更快的整数和多项式矩阵算术的算法，这是现代符号计算系统的核心。我们将特别关注快速矩阵多项式算术的矩阵标准形、序基及其用途及其应用。例如，代数组合学中的计算需要快速的阶基计算来确定特定形式幂序列的D-有限性，这源于对算法的分析。出现的问题和挑战包括具有矩阵的线性代数或具有参数的矩阵多项式，其中矩阵属性根据参数的特定值而变化。还有整数矩阵或多项式矩阵，其中系数算术的增长是高效算法的基本考虑因素。最后，虽然符号算法通常使用精确算术，但通常情况下，应用程序以精确代数的形式描述，但实际上处理来自测量数据的数值浮点系数。例如，在线性系统理论或控制理论中就是这种情况，这两者都利用矩阵多项式算术的代数形式。然后，人们需要解决效率问题，同时还要解决数字稳定性问题。这项建议的第二部分侧重于在应用程序中使用计算机代数，特别是那些大量使用线性或多项式代数的应用程序。在不变多项式和动力系统的情况下，我们希望改进用于在存在对称性的情况下简化这些系统的算法，这是自然界中自然发生的事情。具体地说，人们计算不变量，并利用这些不变量来找到更简单的系统，从而提供解决原始系统的有效方法。在求和和积分的情况下，我们打算找到新的、改进的算法来构造创造性伸缩的归约算法，一种寻找或验证求和和确定积分公式的方法。软件一直是我们研究的重要组成部分，因为它使人能够验证理论与实践的一致性。