Algorithms for exact linear algebra

精确线性代数算法

• 批准号: RGPIN-2018-05256
• 负责人: Storjohann, Arne
• 金额: $ 5.97万
• 依托单位: 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=750230
• 关键词: 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.

计算机代数系统，如Maple、数学、Magma，以及最近的SAGE，已经成为数学家、计算机科学家和教育工作者的基本工具。这些系统允许在各种各样的域上使用精确的算术对符号输入进行计算，例如整数和多项式。我的研究重点主要是涉及具有整数和多项式项的矩阵的问题。整数和多项式矩阵的计算在密码学和线性系统理论等不同领域中经常出现。这项研究的主要目标是发现改进的算法，将矩阵转换为特定的“范式”，自然地揭示矩阵的行和列中编码的结构和信息。目标是实现在所需位操作数量方面近乎最优的算法。开发的算法将是空间高效的，使用的中间空间不会超过写下输入和输出所需的空间。这项工作中的一个挑战是设计正确处理精确计算领域的算法。例如，在设计和分析算法时需要考虑整数的大小(位数)，特别是因为在计算过程中产生并出现在输出中的整数可能比输入矩阵中的整数大得多。长期目标是一个可移植的软件库，基于研究产生的新技术和算法，用于对整数和多项式矩阵进行精确的线性代数计算。研究产生的算法将允许解决更大的线性代数问题，并将更有效地利用计算机资源。