The linboxing package for
GAP
provides a kernel-level interface from GAP to the
LinBox
C++ exact linear algebra library.
It provides alternative versions of some GAP
linear algebra routines that are considerably faster than the equivalent
GAP versions.
The functions provided by the linboxing
package are named the same as their
GAP equivalents, but are contained within
the LinBox record.
Currently provided are LinBox.DeterminantMat,
LinBox.RankMat, LinBox.TraceMat and
LinBox.SolutionMat. Computation over the integers and prime
fields (of order smaller than 228) are currently supported.
The table below give a comparison between
GAP's linear algebra routines
and those using the linboxing
package. Computation was performed on
a Intel Core 2 Duo machine running at 2.66GHz, with
GAP 4.4.10, LinBox 1.1.4
and version 0.5 of the linboxing package.
All matrices are dense n×n matrices. Integer matrices
are created with the GAP command RandomMat(n, n, Integers), while
matrices over the ‘large prime field’ are generated similarly,
but with GF(10007). The linboxing
package commands are compared with their
GAP equivalents, and for the integers we compare with the
specialist GAP integer functions DeterminantIntMat,
BaseIntMat and SolutionIntMat, which
(for n>20) are much faster (but still slower than
the linboxing package).
GAP is
always faster than the linboxing package for
TraceMat, and is also
faster for prime fields of order less than 256 (except possibly for very
large matrices).
DeterminantMat
|
|
Integers
| 50 | 100 | 200 | 400 |
| 0.012s |
0.152s |
2.768s |
53.063s |
| 0.048s |
0.212s |
1.748s |
16.241s |
| 0.25 |
0.7 |
1.6 |
3.3 |
|
Large prime field
| 50 | 100 | 200 | 400 | 800 |
| 0.008s |
0.024s |
0.176s |
1.361s |
10.613s |
| 0.004s |
0.012s |
0.060s |
0.268s |
1.124s |
| 2 |
2 |
2.9 |
5.1 |
9.4 |
|
RankMat
|
|
Integers
| 50 | 100 | 200 | 400 |
| 0.040s |
0.280s |
3.724s |
62.136s |
| 0.004s |
0.012s |
0.060s |
0.240s |
| 10 |
23.3 |
62.1 |
258.9 |
|
Large prime field
| 50 | 100 | 200 | 400 | 800 |
| 0s |
0.024s |
0.172s |
1.340s |
10.545s |
| 0.004s |
0.020s |
0.064s |
0.256s |
1.128s |
| 0 |
0.8 |
2.7 |
5.2 |
9.3 |
|
SolutionMat
|
|
Integers
| 50 | 100 | 200 | 400 |
| 0.040s |
0.324s |
7.448s |
171.634s |
| 0.060s |
0.360s |
2.388s |
17.113s |
| 0.7 |
0.9 |
3.1 |
10.0 |
|
Large prime field
| 50 | 100 | 200 | 400 | 800 |
| 0.004s |
0.044s |
0.324s |
2.500s |
19.777s |
| 0.012s |
0.040s |
0.148s |
0.660s |
2.949s |
| 0.3 |
1.1 |
2.2 |
3.8 |
6.7 |
|
Requirements
This package needs to compile a kernel module that is loaded at run-time. To
build this, you will need
- GAP version 4.4 or greater
- the GNU Multiprecision (GMP) library
- the BLAS and
LAPACK libraries
- LinBox version 1.1.6 or 1.1.7.
- Givaro version
3.2.16 or 3.3.3 (for the two LinBox versions respectively).
- and the standard tools for building C/C++ programs from source
This package has thus far only been tested on Linux and Mac OS X. It is
unlikely to work on Windows at the moment!
Download
Documentation
The documentation below gives detailed installation instructions, and
instructions and examples for using the
linboxing package within
GAP. This documentation is also available
in the downloaded archive, and can be accessed from the
GAP online help once the package is installed.