LinBox¹, A Demonstration

The LinBox Group²

Three major threads have come together to form the linear algebra library LinBox. The first is the use of modular algorithms when solving integer or rational matrix problems. The second thread and original motive for LinBox is the implementation of black box algorithms for sparse/structured matrices. Finally, it has proven valuable to introduce elimination techniques that exploit the floating point BLAS libraries even when our domains are finite fields. The latter is useful for dense problems and for block iterative methods.

Black box techniques [4] are enabling exact linear algebra computations of a scale well beyond anything previously possible. The development of new and interesting algorithms has proceeded apace for the past two decades. It is time for the dissemination of these algorithms in an easily used software library so that the mathematical community may readily take advantage of their power. LinBox is that library [3]. In this demo, we sketch the current range of capabilities, describe the design and give several examples of use.

Exact black box methods are currently successful on sparse matrices with hundreds of thousands of rows and columns and having several million nonzero entries. The main reason large problems can be solved by black box methods is that they require much less memory in general than traditional elimination-based metshods do. This fact is widely used in the numerical computation area. We refer for instance to the templates for linear system solution and eigenvalue problems [1]. This has also led the computer algebra community to a considerable interest in black box methods. Since Wiedemann's seminal paper [5], many developments have been proposed especially to adapt Krylov or Lanczos methods to fast exact algorithms. We refer to [2] and references therein for a review of problems and solutions.

LinBox supplies efficient black box solutions for a variety of problems including linear equations and matrix normal forms with the guiding design principle of re-usability. The most essential and driving design criterion for LinBox is that it is generic with respect to the domain of computation. This is because there are many and various representations of finite fields each of which is advantageous to use for some algorithm under some circumstance. The integral and rational number capabilities depend heavily on modular techniques and hence on the capabilities over finite fields. In this regard, generic software methodology is a powerful tool.

Using examples from demanding applications (Trefethen's one hundred digits challenge, signature of a matrix arising in Lie group representation, Smith form for simplicial homology, determinants for combinatorial identities, characteristic polynomials in the study of graph properties, etc.), we demonstrate four general levels of use of our library. In order from least involved with the details to most involved, they are:

1. Access using a linbox web server³.

   The user at this level must attend to preparation of a matrix in a suitable file format and invoking the service. The server itself provides adequate documentation for this.

2. Access using already compiled functions or through an interface to linbox in a general purposes system such as Maple or GAP.

   The user at this level must see to installation, and then attend to preparation of her matrix in a suitable file format and to the form of the program or procedure invocation. A number of programs are available in the examples directory distributed with LinBox providing for rank, determinant, linear system solution, etc.

3. Use of LinBox as a programmers library for exact linear algebra functions.

   At this level a user must do at least the following:

   1. Choose a field or ring representation and construct a specific field or ring object R.
   2. Choose a black box or matrix representation suitable to your data and construct specific matrix A over R.
   3. Call needed algorithm. The solutions directory is designed to support this by providing functions with simple problem oriented interfaces (rank(), det(), solve(), etc.), yet allowing some user control of algorithm details. The programmer may be providing some of the parts such as an application specific black box matrix class.

4. Power development.

   Again, this is use of LinBox as a library, but with hands fully on the details. The programmer at this level apparently needs the best opportunities for high performance and is willing to use the more complicated internal interfaces to get it. Direct calls to functions in the algorithms directory and perhaps to related packages such as fflas, ffpack, or other components are being used.