ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 11 Jan 2011 07:52:02 +0100Efficient kernel-computing of sparse GF2 matriceshttps://ask.sagemath.org/question/7841/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)Sun, 09 Jan 2011 22:30:58 +0100https://ask.sagemath.org/question/7841/efficient-kernel-computing-of-sparse-gf2-matrices/Answer by niles for <p>To compute the kernel of a sparse GF(2) matrix A I simply do</p>
<pre><code>A.kernel()
</code></pre>
<p>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)</p>
https://ask.sagemath.org/question/7841/efficient-kernel-computing-of-sparse-gf2-matrices/?answer=11954#post-id-11954Looking in [sage/matrix/matrix_mod2_dense.pyx][1], 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][2] list too.
[1]: http://hg.sagemath.org/sage-main/file/120c07be6358/sage/matrix/matrix_mod2_dense.pyx#l1
[2]: http://groups.google.com/group/sage-supportMon, 10 Jan 2011 12:56:59 +0100https://ask.sagemath.org/question/7841/efficient-kernel-computing-of-sparse-gf2-matrices/?answer=11954#post-id-11954Comment by Mustafa for <p>Looking in <a href="http://hg.sagemath.org/sage-main/file/120c07be6358/sage/matrix/matrix_mod2_dense.pyx#l1">sage/matrix/matrix_mod2_dense.pyx</a>, I see that <code>kernel_right</code> uses the <code>pluq</code> algorithm, but otherwise I didn't see any other special implementations of kernel there. You could ask the <a href="http://groups.google.com/group/sage-support">sage-support</a> list too.</p>
https://ask.sagemath.org/question/7841/efficient-kernel-computing-of-sparse-gf2-matrices/?comment=22305#post-id-22305Ok, thank you, perhaps it will be implemented in coming versions.Tue, 11 Jan 2011 07:52:02 +0100https://ask.sagemath.org/question/7841/efficient-kernel-computing-of-sparse-gf2-matrices/?comment=22305#post-id-22305Answer by niles for <p>To compute the kernel of a sparse GF(2) matrix A I simply do</p>
<pre><code>A.kernel()
</code></pre>
<p>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)</p>
https://ask.sagemath.org/question/7841/efficient-kernel-computing-of-sparse-gf2-matrices/?answer=11953#post-id-11953I 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](http://www.sagemath.org/doc/reference/sage/matrix/matrix_modn_sparse.html). (note that that documentation page doesn't mention `kernel` specifically.
1. If you know of an algorithm with a distinctive name, you could try searching the source code for it, using [`search_src`][3], [`search_doc`][2], or [`search_def`][1]
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](http://hg.sagemath.org/sage-main/file/120c07be6358/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][4]!
good luck! :)
[1]: http://www.sagemath.org/doc/reference/sage/misc/sagedoc.html#sage.misc.sagedoc.search_def
[2]: http://www.sagemath.org/doc/reference/sage/misc/sagedoc.html#sage.misc.sagedoc.search_doc
[3]: http://www.sagemath.org/doc/reference/sage/misc/sagedoc.html#sage.misc.sagedoc.search_src
[4]: http://www.sagemath.org/doc/developer/index.html
Mon, 10 Jan 2011 09:40:01 +0100https://ask.sagemath.org/question/7841/efficient-kernel-computing-of-sparse-gf2-matrices/?answer=11953#post-id-11953Comment by Mustafa for <p>I wouldn't necessarily expect other algorithms to be implemented, but here are some things you could try:</p>
<ol>
<li><p>Try using the <code>sparse=True</code> keyword when you create the matrix; if better algorithms are available, this would be the generic way to use them: e.g. <a href="http://www.sagemath.org/doc/reference/sage/matrix/matrix_modn_sparse.html">sparse matrices over Z/n for n small</a>. (note that that documentation page doesn't mention <code>kernel</code> specifically.</p></li>
<li><p>If you know of an algorithm with a distinctive name, you could try searching the source code for it, using <a href="http://www.sagemath.org/doc/reference/sage/misc/sagedoc.html#sage.misc.sagedoc.search_src"><code>search_src</code></a>, <a href="http://www.sagemath.org/doc/reference/sage/misc/sagedoc.html#sage.misc.sagedoc.search_doc"><code>search_doc</code></a>, or <a href="http://www.sagemath.org/doc/reference/sage/misc/sagedoc.html#sage.misc.sagedoc.search_def"><code>search_def</code></a></p>
<pre><code>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.)
...
</code></pre></li>
<li><p>Lastly, you could try reading some of the source files themselves: there are a number of likely filenames in <a href="http://hg.sagemath.org/sage-main/file/120c07be6358/sage/matrix">sage/matrix</a>.</p></li>
</ol>
<p>And, of course, if you don't find the algorithm you're looking for, you could always implement it, and <a href="http://www.sagemath.org/doc/developer/index.html">add it to sage</a>!</p>
<p>good luck! :)</p>
https://ask.sagemath.org/question/7841/efficient-kernel-computing-of-sparse-gf2-matrices/?comment=22311#post-id-22311First 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 :)Mon, 10 Jan 2011 12:40:07 +0100https://ask.sagemath.org/question/7841/efficient-kernel-computing-of-sparse-gf2-matrices/?comment=22311#post-id-22311