Ask Your Question
1

Efficient kernel-computing of sparse GF2 matrices

asked 2011-01-09 15:30:58 -0500

Mustafa gravatar image

updated 2011-04-28 11:44:11 -0500

Kelvin Li gravatar image

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

2 answers

Sort by ยป oldest newest most voted
0

answered 2011-01-10 02:40:01 -0500

niles gravatar image

updated 2011-01-10 05:57:44 -0500

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! :)

edit flag offensive delete link more

Comments

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 05:40:07 -0500 )edit
0

answered 2011-01-10 05:56:59 -0500

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

Comments

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

Mustafa gravatar imageMustafa ( 2011-01-11 00:52:02 -0500 )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

Stats

Asked: 2011-01-09 15:30:58 -0500

Seen: 203 times

Last updated: Jan 10 '11