Ask Your Question

Speed up calculation of left kernel

asked 2018-02-20 08:33:49 -0500

Vitor gravatar image

Is there any way to accelerate the calculation of the left kernel of a matrix? It could be by allowing sage to use more memory or using some parallelism, for instance.

I have a 1230 x 74 dense matrix over Integer Ring

A = Matrix(ZZ, 1230, 74)

and when I try to use


the calculations doesn't finish (it has run for three days and then I interrupted the script).

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2018-02-20 12:16:01 -0500

First, calculations over the integers will be slow, and the best way to speed them up is, if possible, work over a field (or several fields) instead. Can you get the information you need from A.change_ring(QQ) and A.change_ring(GF(2))?

If that won't work, then you should try some of the different available algorithms for left_kernel. I tried this with much smaller matrices, just to test things:

sage: %timeit random_matrix(ZZ, 123, 74).left_kernel()
1 loop, best of 3: 8.25 s per loop
sage: %timeit random_matrix(ZZ, 123, 74).left_kernel(algorithm='default')
1 loop, best of 3: 8.28 s per loop
sage: %timeit random_matrix(ZZ, 123, 74).left_kernel(algorithm='pari')
1 loop, best of 3: 1.07 s per loop
sage: %timeit random_matrix(ZZ, 123, 74).left_kernel(algorithm='flint')
1 loop, best of 3: 7.77 s per loop
sage: %timeit random_matrix(ZZ, 123, 74).left_kernel(algorithm='padic')
1 loop, best of 3: 7.93 s per loop

The different algorithms may not scale equally well, though, so experiment with different algorithms and with different sizes of matrices.

edit flag offensive delete link more

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: 2018-02-20 08:33:49 -0500

Seen: 50 times

Last updated: Feb 20