Algorithms for exact linear algebra

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

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.