CHA - linboxing package

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.

1. What the package provides
2. Performance
3. Download and installation
4. Future plans
5. Thanks
5. Further information

What the package provides

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 2²⁸) are currently supported.

Performance

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


n
GAP
LinBox
speedup

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


n
GAP
LinBox
speedup

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


n
GAP
LinBox
speedup

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

Download

To download this package, details of the package's requirements, and installation instructions, please see the download section of this website.

Future plans

It should be possible to extend this package to support the following additional facilities of LinBox;

extension fields GF(pⁿ)
Smith Normal Form (for which see also the GAP homology package in the further information below)
characteristic polynomial
minimal polynomial

If you would particularly like one of these supporting in this package, please let me know.

Thanks

The linboxing package for GAP is supported by a Marie Curie Transfer of Knowledge grant based at the Department of Mathematics, NUI Galway (MTKD-CT-2006-042685)

If you download and use this package, and have any feedback, good or bad, please let me know: paul.smith(at)nuigalway.ie

Further information

The manual for this linboxing package
The GAP website
The LinBox website
The GAP homology package. As part of its homology computations, this provides a general function that computes the Smith Normal Form of sparse integer matrices using LinBox. It does this via an external program, which is slower than using a kernel module. (But the linboxing package does not currently support sparse matrices or Smith Normal Form!)

linboxing