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.
The project AF: Small: Collaborative Research: High Performance Exact Linear Algebra Kernels has led to improved algorithms for the exact solution of linear equations and has applied the new techniques to a mathematical problem arising in graph theory that could not be computed previously. This application required the calculation of the rank of a linear system with approximately 40 million equations and unknowns. The techniques developed use a hybrid numeric/symbolic approach to solving linear systems with rational coefficients along with block methods that allow the use of highly tuned dense matrix kernels to solve sparse systems, i.e. those with few non-zero coefficients. Initial work was done to automatically tune these kernels thus enabling portable high-performance. The new algorithms have been implemented and made available to researchers through the LINBOX library (www.linalg.org). Further a detailed analysis of the algorithms was carried out leading to better understanding of how these algorithms behave in practice. The grant has supported graduate students at Drexel University and the University of Delaware. Moreover, it has strongly influenced teaching to a broader audience through an undergraduate course in computer algebra at Drexel and a graduate course at Delaware. Both specifically emphasized exact linear algebra and rational solving.
