Ask Your Question

# Speed up calculation of left kernel

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 close merge delete

## 1 Answer

Sort by » oldest newest most voted 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.

more

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2018-02-20 15:33:49 +0200

Seen: 234 times

Last updated: Feb 20 '18