Description
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
[1] These methods are probabilistic for a finite field, though for
rank there exists a certification when the field is of
characteristic zero.
Related packages
We offer related packages: