Algorithms for the exact solution to problems in linear algebra

线性代数问题的精确求解算法

• 批准号: 262082-2013
• 负责人: Storjohann, Arne
• 金额: $ 2.19万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634833
• 关键词: Algorithms; exact; solution; problems; linear

Computer algebra systems such as Maple or Mathematica, 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或Mathematica，以及最近的SAGE，已经成为数学家，计算机科学家和教育工作者的重要工具。这些系统允许在各种域上对符号输入进行精确算术计算，例如整数和多项式。我的研究重点主要是涉及整数和多项式项的矩阵问题。整数和多项式矩阵的计算经常出现在不同的领域，如密码学和线性系统理论。该研究的主要目标是发现改进的算法，将矩阵转换为某些“范式”，这些范式自然地揭示了矩阵的行和列中编码的结构和信息。目标是实现在所需位操作的数量方面接近最优的算法。所开发的算法将是空间有效的，不使用比写下输入和输出所需的更多的中间空间。这项工作中的一个挑战是设计正确处理精确计算域的算法。例如，尺寸在算法的设计和分析中需要考虑整数的位数，特别是因为在计算过程中出现并出现在输出中的整数可能比输入矩阵中的整数大得多。长期目标是建立一个可移植的软件库，基于研究中产生的新技术和算法，用于整数和多项式矩阵的精确线性代数计算。从研究中产生的算法将允许更大的线性代数问题的解决方案，并将更有效地利用计算机资源。