Overview - Project LinBox

What is Project LinBox?

Project LinBox is a C++ template library for high-performance exact computational linear algebra. What does all this mean?

• Computational linear algebra. LinBox provides tools for linear algebra computations over the integers, the rational numbers, and finite fields and rings. It can solve linear systems, and compute several matrix invariants, such as minimal and characteristic polynomials, rank, determinant, Smith normal form. It can find least-norm, least-squares solutions to singular and inconsistent systems. There is capability for positive definiteness determination and signature (inertia) of symmetric integer matrices.
• Sparse and Dense Matrices. LinBox was originallly designed primarily to work with sparse and structured matrices, which are defined in this context as those matrices where the computational cost of application of an m by n matrix to a vector is significantly less than O(mn), the cost for a dense matrix. Now, increasingly, LinBox also has codes for dense matrix computations using floating point BLAS routines for speed while not sacrificing exactness.
• Exact. All of LinBox's computational results are exact, unlike the case with numerical systems such as Matlab. LinBox can be used to provide the computational infrastructure needed for rigorous theorem-proving in addition to number-crunching.
• High-performance. LinBox implements iterative system-solving methods such as those of Wiedemann and Lanczos to operate on very large, sparse linear systems. This avoids the potential fill-in associated with elimination-based methods and keeps memory use relatively constant through the computation. These methods allow LinBox to be used to solve systems with hundreds of thousands of equations and hundreds of thousands of variables.
• C++ template library. C++ templates are used to provide both high performance and genericity. In particular, LinBox algorithms are generic with respect to the field or ring over which they operate and with respect to the internal organization of the black box matrix.

Project goals

LinBox aims to provide world-class high performance implementations of the most advanced algorithms for exact linear algebra.

Functionality:

• System solutions:
  • Problem variant:
    • Nonsingular systems
    • Random solutions for consistent singular systems
    • Nullspace basis and random sample of nullspace
    • Least-norm, least-squares solutions
    • Certificate of inconsistency
  • Domain of computation:
    • Over a finite field
    • Integer solutions (i.e., Diophantine systems)
    • Rational solutions, using rational reconstruction
• Linear operator invariants:
  • Determinant
  • Trace
  • Rank [1]
  • Minimal polynomial
  • Characteristic polynomial
  • Eigenvalues/eigenvectors
  • Similarity testing
• Matrix canonical forms:
  • Smith normal form
  • Frobenius (rational) normal form