Loading [MathJax]/jax/output/HTML-CSS/jax.js
Ask Your Question
1

Speed up calculation of left kernel

asked 7 years ago

Hilder Vitor Lima Pereira 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).

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
2

answered 7 years ago

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.

Preview: (hide)
link

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

Seen: 575 times

Last updated: Feb 20 '18