Résumé
ACM Transactions on Mathematical Software 35, 3 (2009) article 19 In the past two decades, some major efforts have been made to reduce exact
(e.g. integer, rational, polynomial) linear algebra problems to matrix
multiplication in order to provide algorithms with optimal asymptotic
complexity. To provide efficient implementations of such algorithms one need to
be careful with the underlying arithmetic. It is well known that modular
techniques such as the Chinese remainder algorithm or the p-adic lifting allow
very good practical performance, especially when word size arithmetic are used.
Therefore, finite field arithmetic becomes an important core for efficient
exact linear algebra libraries. In this paper, we study high performance
implementations of basic linear algebra routines over word size prime fields:
specially the matrix multiplication; our goal being to provide an exact
alternate to the numerical BLAS library. We show that this is made possible by
a carefull combination of numerical computations and asymptotically faster
algorithms. Our kernel has several symbolic linear algebra applications enabled
by diverse matrix multiplication reductions: symbolic triangularization, system
solving, determinant and matrix inverse implementations are thus studied.