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.