Ask Your Question

Efficient kernel-computing of sparse GF2 matrices

asked 2011-01-09 22:30:58 +0200

Mustafa gravatar image

updated 2011-04-28 18:44:11 +0200

Kelvin Li gravatar image

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


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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2011-01-10 12:56:59 +0200

niles gravatar image

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.

edit flag offensive delete link more


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

Mustafa gravatar imageMustafa ( 2011-01-11 07:52:02 +0200 )edit

answered 2011-01-10 09:40:01 +0200

niles gravatar image

updated 2011-01-10 12:57:44 +0200

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/ euclidean_domains import EuclideanDomains
    categories/        sage: EuclideanDomains().CartesianProducts()
    rings/ euclidean_domain_element import EuclideanDomainElement, is_EuclideanDomainElement
    rings/    very similar to the extended Euclidean algorithm. For more details,
    rings/        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! :)

edit flag offensive delete link 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 :)

Mustafa gravatar imageMustafa ( 2011-01-10 12:40:07 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2011-01-09 22:30:58 +0200

Seen: 621 times

Last updated: Jan 10 '11