ITR/ACS: Collaborative Research LinBox: A Generic Library for Seminumeric Black Box Linear Algebra

North Carolina State University, Raleigh NC

Investigators

Abstract

The LinBox group of twelve researchers in three countries (USA, France, Canada) proposes research in the design of efficient algorithms for linear algebra, in their implementation in a software library, and in how to interface the library to widely-used scientific computing software. Algorithms will be implemented, and new algorithms designed, for the black box representation of matrices---hence the name LinBox---over entry domains that are either symbolic, that is, exact, or floating point, that is, inexact. The library is generically programmed as C++ template classes with abstract underlying arithmetics; they can be compiled with a variety of fast libraries for the basic field, floating point, and polynomial operations. A server/client interface seamlessly attaches the library to the common general purpose symbolic systems Maple and Mathematica and to the numeric system MatLab. Parallel execution of the implemented algorithms is facilitated. Black box matrices are stored as functions (as linear operators in effect): the matrix is a procedure that takes an arbitrary vector as input and efficiently computes the matrix-times-vector product. Black box linear algebra generalizes sparsity. The LinBox library will contain algorithms for solving singular and non-singular systems of linear equations whose coefficient matrix is given in black box representation. Furthermore, it is proposed to develop fast methods for the rank and the minimal and characteristic polynomial of a black box matrix. Finally, LinBox will contain methods for linear Diophantine problems with black box matrices, such as computing an integral solution to a linear system with integer entries and computing the Smith normal form of an integer matrix.