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 Matrix Berlekamp/Massey algorithm as described by the PI in his thesis and journal publication has been integrated into the LinBox library. The implementation has been tested for accuracy in computation and is available to be used in methods based on the block Wiedemann algorithm. One such method, a non-singular Block Wiedemann solver has been written and is currently being tested for performance and robustness. Application to matrix rank computation is in progress. Preliminary results are encouraging but need to be tested and improved. After the successful testing of the non-singular solver, we can then turn attention on various related linear algebra computations and speed improvements to the algorithms. The first such computation is rank. By using the Matrix Berlekamp/Massey algorithm to compute a matrix generator with random bilinear projections, one can with high probability compute the rank of a matrix. After the generator computation, one needs to compute the degree and trailing degree of the determinant of the generator. As a result of the PI's prior work the degree is known, however the trailing degree is not. Options for computation of the trailing degree include a new method based on LU decomposition or a standard interpolation method. In addition to rank, computations such as smith normal form, determinant, singular solving and characteristic/minimum polynomial are possible using block Wiedemann methods. The Matrix Berlekamp/Massey implementation and non-singular block Wiedemann solver can be improved by tuning. Currently we do not take full advantage of all the fast arithmetics that are available and possible. One of the main triumphs of the Matrix Berlekamp/Massey algorithm is the encoding of matrix algebra into polynomial algebra. It should be possible and advantageous to apply known methods of fast matrix arithmetic and fast polynomial arithmetic to enhance the algorithms. Over specific fields and blocking dimensions, the field and vector arithmetic can be tuned specifically for the algorithm. Finally, by imposing some restrictions, it should be possible to benefit from sub-quadratic methods based on the half-gcd algorithm.
