# Efficient kernel-computing of sparse GF2 matrices

To compute the kernel of a sparse GF(2) matrix A I simply do

A.kernel()


But for (highly) sparse GF(2) matrices there are (many) much faster algorithm to compute the kernel, surely some of them are implemented in sage, but by which command I apply them? (Tutorial and online help could'nt answer that)

edit retag close merge delete

Sort by ยป oldest newest most voted

I wouldn't necessarily expect other algorithms to be implemented, but here are some things you could try:

1. Try using the sparse=True keyword when you create the matrix; if better algorithms are available, this would be the generic way to use them: e.g. sparse matrices over Z/n for n small. (note that that documentation page doesn't mention kernel specifically.

2. If you know of an algorithm with a distinctive name, you could try searching the source code for it, using search_src, search_doc, or search_def

sage: search_src('Euclidean')
categories/basic.py:44:from euclidean_domains import EuclideanDomains
categories/cartesian_product.py:169:        sage: EuclideanDomains().CartesianProducts()
...
rings/all.py:37:from euclidean_domain_element import EuclideanDomainElement, is_EuclideanDomainElement
rings/arith.py:1862:    very similar to the extended Euclidean algorithm. For more details,
rings/arith.py:1896:        the extended Euclidean algorithm.)
...

3. Lastly, you could try reading some of the source files themselves: there are a number of likely filenames in sage/matrix.

And, of course, if you don't find the algorithm you're looking for, you could always implement it, and add it to sage!

good luck! :)

more

First didn't change the speed, probably it uses the same algorithm with sparse=True?! Did not find one of the algorithm, Im a bit surprised about that, they should be of general interest, but Im new to sage, maybe I just didnt see it. Yes, implementation is always possible, but I hoped for done work :)

( 2011-01-10 05:40:07 -0500 )edit

Looking in sage/matrix/matrix_mod2_dense.pyx, I see that kernel_right uses the pluq algorithm, but otherwise I didn't see any other special implementations of kernel there. You could ask the sage-support list too.

more

Ok, thank you, perhaps it will be implemented in coming versions.

( 2011-01-11 00:52:02 -0500 )edit