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 finititions。出现的问题和挑战包括带有参数的物质或矩阵多项式的线性代数，其中矩阵属性根据参数的特定值而变化。这也是整数或多项式材料的矩阵，其中核心算术的生长是对有效算法的基本关注。最后，虽然符号算法通常使用精确的算术，但通常以确切的代数来描述应用程序，但实际上与来自测量数据的数字，浮点系数一起使用。例如，在线性系统理论或控制理论中就是这种情况，这两者都利用了矩阵多项式算术的代数形式。然后，一个人需要解决效率和同时数值稳定性。该提案的第二部分重点是在应用中使用计算机代数，尤其是那些大量使用线性或多项式代数的应用程序。在不变的多项式和动态系统的情况下，我们希望改善在存在对称性的情况下用于减少这些系统的算法，这是自然界自然发生的。特别是，一个人计算不变性并利用这些不变来查找更简单的系统，而哪些系统又提供了有效的解决原始系统的方法。在总结和集成的情况下，我们打算找到用于构建创造性电信的还原算法的新的，改进的算法，一种用于查找或验证求和并定义集成公式的方法。软件一直是我们研究的重要组成部分，因为它可以验证理论与实践一致。