Exact linear algebra, polynomial systems and applications of computer algebra

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

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

计算机代数系统是科学家和工程师的重要工具。它们包含大量的数学知识，并提供操作表达式的能力，以使用精确和扩展精确数字来扩展这些知识。精确算法中的高效算法和数值算法中的正确算法是这些系统的关键组成部分。