AF: Small: Collaborative Research: High Performance Exact Linear Algebra Kernels

这个项目将提高实现和优化精确线性代数计算算法的技术水平。通过精确计算，线性方程组的求解从有限精度提高到精确解。这大大增加了可访问的应用范围，并允许计算矩阵不变量，如秩，行列式，特征和最小多项式，以及Smith和Frobenius范式。我们将把线性代数中的块黑箱方法的新发展的理论基础与构建这些实现的计算内核的硬件和软件的高性能实现结合起来。最终的实现将在LinBox软件库的框架中公开提供。一个用于自动调整底层计算机代数内核的系统将作为LinBox库的一部分被开发和分发。自动调整框架也将使其他计算机代数系统受益。由此产生的有限域计算的进步，如模数和有限代数域扩展，将有利于许多领域，包括密码学和编码理论。该项目具有以下实际影响：提高实验数学水平。在实验数学中，符号计算提供了对猜想的检验。也许更重要的是，来自符号计算的数据可以指导推测的表述，然后作为正式证明的候选。通过允许更大的精确线性代数计算，这个项目将增加这种计算在数学中的有用性。这个项目最广泛的，也许也是最重要的成果是能够解决许多目前根本没有解决方法的问题。该项目将使有效地求解线性系统中由于问题实例的病态而导致数值方法失败的问题成为可能，尽管数据的近似性质，但能否得到准确的结果是有效和有意义的。

This project will improve the state of the art of the implementation and optimization of algorithms for exact linear algebra computation. With exact computation, solving systems of linear equations is advanced from limited accuracy to exact solutions. This greatly increases the scope of accessible applications and allows matrix invariants such as rank, determinant, characteristic and minimal polynomial, and Smith and Frobenius normal forms to be computed.We will combine a newly developed theoretical basis for block blackbox methods in linear algebra with high performance implementation, in hardware and software, of the computational kernels from which these implementations are constructed. The resulting implementations will be made publicly available in the framework of the LinBox software library. A system for automatically tuning the underlying computer algebra kernels will be developed and distributed as part of the LinBox library. The autotuning framework will benefit other computer algebra systems as well. The resulting advances for computation in finite domains, such as modular numbers and finite algebraic field extensions, will benefit many areas including cryptography and coding theory.The project has many practical impacts as follows:Experimental mathematics will be enhanced. In experimental mathematics, symbolic computation provides for testing of conjectures. And, perhaps more importantly, data from symbolic computations can guide the formulation of conjectures that are then candidates for formal proof. By permitting larger exact linear algebra computations, this project will increase the usefulness of such computation in mathematics.The broadest, and perhaps most significant, outcome of this project is an ability to solve many problems which currently have no solution method at all. This project will make it possible to efficiently solve linear systems where numerical methods fail due to ill-condition of the problem instance, yet the exact result, could it be obtained, is valid and meaningful despite the approximate nature of the data.