Exact linear algebra: nearly optimal algorithms for nonuniform problems

该研究计划的目的是设计和分析新的算法，在线性代数领域的问题的精确解。 我们的重点是问题涉及矩阵填充整数和多项式。 目标是发现有效利用计算机资源的算法，包括时间（所需机器字操作的数量）和空间（内存需求）。精确线性代数的快速算法是计算机代数系统数学引擎的核心组成部分。 计算机代数被数学、科学和工程界的研究人员和实践者广泛使用。 代数计算出现在不同的领域，如图形和机器人。 在这些领域中复杂问题的解决方案通常需要精确线性代数问题的解决方案，或者作为计算过程中的关键步骤，或者在许多情况下，作为计算瓶颈。 例如，在某些类型的密码系统的安全性研究期间，出现了涉及大整数矩阵的计算问题。 新算法的开发，既严格分析和实际快速是特别受欢迎的。 我们计划实现我们设计的算法的原型，并使用它们来解决实践中出现的大型问题。

The objective of this research program is to design and analyse new algorithms for the exact solution of problems in the area of linear algebra.  Our focus is on problems involving matrices filled with integers and polynomials.  The goal is to discover algorithms that make efficient use of computer resources including time (number of required machine word operations) and space (memory requirements).Fast algorithms for exact linear algebra are a central component of the mathematical engines of computer algebra systems.  Computer algebra is very widely used by researchers and practitioners in the mathematical, scientific and engineering communities.  Algebraic computations arise in diverse areas such as graphics and robotics.  The solutions of complex problems in these areas typically requires the solution of exact linear algebra problems, either as key steps during the computation or, in many cases, as the computational bottleneck.  Computational problems involving large integer matrices arise, for example, during the security study of certain types of cryptographic systems.  The development of new algorithms that are both rigorously analysed and practically fast is especially welcome.  We plan to implement prototypes of the algorithms we design and use them to solve large problems occurring in practice.