Algorithms for exact linear algebra

精确线性代数算法

• 批准号: RGPIN-2018-05256
• 负责人: Storjohann, Arne
• 金额: $ 2.99万
• 依托单位: 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=713114
• 关键词: Algorithms; exact; linear; algebra

Computer algebra systems such as Maple, Mathematica, Magma, and more recently SAGE, have become essential tools for mathematicians, computer scientists and educators. These systems allow computations with exact arithmetic on symbolic inputs over a wide variety of domains, for example integers and polynomials. My research focus is primarily on problems involving matrices with integer and polynomial entries. Computations with integer and polynomial matrices occur frequently in diverse areas such as cryptography and linear systems theory. The primary objective of the research is to discover improved algorithms for transforming matrices to certain "normal forms" which naturally reveal the structure and information that is encoded in the rows and columns of the matrix. The goal is to achieve algorithms which are nearly optimal in terms of the number of required bit operations. The algorithms developed will be space-efficient, using no more intermediate space than required to write down the input and output. A challenge in this work is to design algorithms that correctly handle the exact domains of computation. For example, the sizes (number of digits) of integers need to be taken into account in the design and analysis of algorithms, especially since integers arising during the computation and appearing in the output can be much larger than those in the input matrix. The long term goal is a portable software library, based on the novel techniques and algorithms arising from the research, for doing exact linear algebra computations with integer and polynomial matrices. The algorithms arising from the research will allow the solution of larger linear algebra problems, and will make more effective use of computer resources.

枫木，Mathematica，Magma和Sage等计算机代数系统已成为数学家，计算机科学家和教育工作者的重要工具。 这些系统允许对各种域（例如整数和多项式）的符号输入进行精确算术计算。 我的研究重点主要是涉及具有整数和多项式条目的矩阵的问题。 用整数和多项式矩阵进行计算经常发生在密码学和线性系统理论等不同领域。 该研究的主要目的是发现改进的算法将矩阵转换为某些“正常形式”，这些矩阵自然揭示了在矩阵的行和列中编码的结构和信息。 目的是实现在所需的位操作数量方面几乎最佳的算法。 开发的算法将是空间效率的，使用不超过写入输入和输出所需的中间空间。 这项工作的挑战是设计正确处理计算确切域的算法。 例如，在算法的设计和分析中需要考虑整数的大小（数字数），尤其是因为在计算过程中出现并出现在输出中的整数可能比输入矩阵中的整数大得多。 长期目标是基于研究引起的新技术和算法的便携式软件库，用于使用整数和多项式矩阵进行精确的线性代数计算。 研究引起的算法将允许解决较大的线性代数问题，并将更有效地利用计算机资源。