Exact linear algebra, polynomial systems and applications of computer algebra

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

• 批准号: RGPIN-2020-04276
• 负责人: Labahn, George
• 金额: $ 4.01万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=739690
• 关键词: 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 有限性。出现的问题和挑战包括具有参数的矩阵或矩阵多项式的线性代数，其中矩阵属性根据参数的特定值而变化。还有整数矩阵或多项式矩阵，其中系数算术的增长是高效算法的基本问题。  最后，虽然符号算法通常使用精确算术，但通常情况下，应用程序是用精确代数来描述的，但实际上却使用来自测量数据的数字浮点系数。例如，在线性系统理论或控制理论中就是这种情况，两者都利用矩阵多项式算术的代数形式。然后需要解决效率问题，同时还要解决数值稳定性问题。该提案的第二部分重点关注计算机代数在应用中的使用，特别是那些大量使用线性或多项式代数的应用。  在不变多项式和动力系统的情况下，我们希望改进用于在存在对称性的情况下减少这些系统的算法，对称性是自然界中自然发生的。具体来说，我们计算不变量并利用它们来找到更简单的系统，从而提供解决原始系统的有效方法。   在求和和积分的情况下，我们打算寻找新的、改进的算法来构建创造性伸缩的归约算法，一种寻找或验证求和和定积分公式的方法。  软件一直是我们研究的重要组成部分，因为它使人们能够验证理论与实践的一致性。