First time here? Check out the FAQ!

Ask Your Question
1

Efficient kernel-computing of sparse GF2 matrices

asked 14 years ago

Mustafa gravatar image

updated 13 years ago

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)

Preview: (hide)

2 Answers

Sort by » oldest newest most voted
0

answered 14 years ago

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.

Preview: (hide)
link

Comments

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

Mustafa gravatar imageMustafa ( 14 years ago )
0

answered 14 years ago

niles gravatar image

updated 14 years ago

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

Preview: (hide)
link

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 ( 14 years ago )

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: 14 years ago

Seen: 754 times

Last updated: Jan 10 '11