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

AF：小型：协作研究：高性能精确线性代数内核

• 批准号: 1016728
• 负责人: Jeremy Johnson
• 金额: $ 21.5万
• 依托单位: Drexel University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-15 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016728&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Performance

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.

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