Arithmetique et algorithmique en algebre lineaire exacte pour la bibliotheque LinBox

Description

Abstract: For a few decades, numerical linear algebra has seen intensive developments in both mathematical and computer science theory which have led to genuine standard software like BLAS or lapack. In computer algebra the situation has not advanced as much, in particular because of the diversity of the problems and because of much of the theoretical progress have been done recently. This thesis falls into a recent class of work which aims at uniforming high-performance codes from many specialized libraries into a single platform of computation. In particular, the emergence of robust and portable libraries like GMP or ntl for exact computation has turned out to be a real asset for the development of applications in exact linear algebra. In this thesis, we study the feasibility and the relevance of the re-use of specialized codes to develop a high performance exact linear algebra library, namely the LinBox library. We use the generic programming mechanisms of C++ (abstract class, template class) to provide an abstraction of the mathematical objects and thus to allow the plugin of external components. Our objective is then to design and validate, in LinBox. high level generic toolboxes for the implementation of algorithms in exact linear algebra. In particular, we propose ''exact/numeric'' hybrid computation routines for dense matrices over finite fields which nearly match with the performance obtained by numerical libraries like LAPACK. On a higher level, we reuse these hybrid routines to solve very efficiently a classical problem of computer algebra : solving diophantine linear systems. Hence, this allowed us to validate the principle of code reuse in LinBox library and more generally in computer algebra. The LinBox library is available at www.linalg.org.