Ask Your Question
1

Speed up calculation of left kernel

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

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

A.left_kernel()

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
2

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

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

Stats

Asked: 2018-02-20 08:33:49 -0600

Seen: 74 times

Last updated: Feb 20