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 -有限性，这些计算源于算法的分析。出现的问题和挑战包括具有参数的矩阵或矩阵多项式的线性代数，其中矩阵性质取决于参数的特定值而变化。还有整数矩阵或多项式矩阵，其中系数算法的增长是高效算法的基本关注点。最后，虽然符号算法通常使用精确算术，但通常情况下，应用程序是根据精确代数描述的，但实际上使用来自测量数据的数字浮点系数。这是一种情况，例如，在线性系统理论或控制理论中，它们都使用矩阵多项式算法的代数形式。然后需要解决效率问题，同时还要解决数值稳定性问题。本建议的第二部分侧重于在应用程序中使用计算机代数，特别是那些重要使用线性或多项式代数的应用程序。在不变多项式和动力系统的情况下，我们希望改进用于在存在对称性的情况下减少这些系统的算法，这是自然界中自然发生的事情。特别是计算不变量，并利用这些来找到更简单的系统，从而提供解原系统的有效方法。在求和和积分的情况下，我们打算找到新的，改进的算法来构建创造性伸缩的约简算法，一种寻找或验证求和和定积分公式的方法。软件一直是我们研究的重要组成部分，因为它使人们能够验证理论与实践的一致性。