Remove overhead from `annihilator_basis`

[tkarn]

There are a few unnecessary matrices created in the FiniteDimensionalModulesWithBasis.annihilator_basis() method. This streamlines them leading to a significant improvement in performance.

[tkarn]

With the original code:

sage: F = FiniteDimensionalAlgebrasWithBasis(QQ).example();                                                                                                                           
sage: x,y,a,b = F.basis()                                                                                                                                                             
sage: %time F.annihilator_basis([x])                                                                                                                                                  
CPU times: user 164 ms, sys: 66.2 ms, total: 230 ms
Wall time: 564 ms
(y, a, b)

With the updated code:

sage: sage: F = FiniteDimensionalAlgebrasWithBasis(QQ).example();                                                                                                                     
sage: x,y,a,b = F.basis()                                                                                                                                                             
sage: %time F.annihilator_basis([x])                                                                                                                                                  
CPU times: user 1.6 ms, sys: 471 µs, total: 2.07 ms
Wall time: 2.13 ms
(y, a, b)

[tkarn]

New commits:

​d548c77

Optimize annihilator_basis method

[tscrim]

Doctests are failing because you have changed how the matrix augmentation works:

sage -t --long --random-seed=0 src/sage/categories/finite_dimensional_lie_algebras_with_basis.py  # 1 doctest failed
sage -t --long --random-seed=0 src/sage/categories/finite_dimensional_algebras_with_basis.py  # 4 doctests failed
sage -t --long --random-seed=0 src/sage/categories/finite_dimensional_modules_with_basis.py  # 12 doctests failed

sage: matrix([[1,2],[3,4]]).augment(matrix([vector([5,6]), vector([7,8])]))
[1 2 5 6]
[3 4 7 8]
sage: matrix([[1,2],[3,4]]).augment(vector([5,6])).augment(vector([7,8]))
[1 2 5 7]
[3 4 6 8]

Actually, each time you augment with a vector, it is actually creating a matrix:

sage: vector([1,2]).column()  # called in augment
[1]
[2]
sage: type(_)
<class 'sage.matrix.matrix_integer_dense.Matrix_integer_dense'>

It also creates a lot more transient objects. So this really should not be faster (although I don't think you can get around the bug. I also cannot reproduce your timings. Your branch:

sage: F = FiniteDimensionalAlgebrasWithBasis(QQ).example()                                                                         
sage: x,y,a,b = F.basis()                                                                                                          
sage: %time F.annihilator_basis([x])                                                                                               
CPU times: user 56.2 ms, sys: 4.28 ms, total: 60.5 ms
Wall time: 59.8 ms
(y, a, b)

Previous code:

CPU times: user 23.2 ms, sys: 0 ns, total: 23.2 ms
Wall time: 33.2 ms
(y, a, b)

Although I get quite a bit of variation in these timings, so it isn't so definitive. Yet it nothing on the order of magnitude difference in comment:1.

Potentially a way to improve the speed is just create one big matrix in one go, and maybe also get rid of the extra function calls with side='right'...

[tkarn]

I think the speedup I was seeing was because I was being sloppy about clearing the cache. If I call annihilator basis twice consecutively, I see the performance gains I thought I was getting from the code.

sage: F = FiniteDimensionalAlgebrasWithBasis(QQ).example()                                                                            
sage: x,y,a,b = F.basis()                                                                                                             
sage: %time F.annihilator_basis([x])                                                                                                  
CPU times: user 155 ms, sys: 55.9 ms, total: 211 ms
Wall time: 545 ms
(y, a, b)
sage: %time F.annihilator_basis([x])                                                                                                  
CPU times: user 2.1 ms, sys: 572 µs, total: 2.68 ms
Wall time: 2.74 ms
(y, a, b)

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​feb51d8

Assign matrix entries element-by-element

[tkarn]

I tried to create one big matrix in one go and it seems to have slowed things down just a tiny bit. Code is pushed just for completeness.

---

New commits:

​feb51d8

Assign matrix entries element-by-element

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​88bd4c6	Optimize annihilator_basis method
​5b1d22a	Build matrix to use right_kernel

[tkarn]

Timing comparison of changes of commit 5b1d2

[tkarn]

I noticed that in the call of .left_kernel() there is a call of .transpose().right_kernel() so I thought maybe we could build the matrix in a way that the right kernel is really what we want. To get the dimensions right I had to add some overhead. When I did the comparison the new changes may have been slightly faster, but I'm unconvinced that this change should be made.

[tscrim]

Don't we know that the number of entries in the output vector is going to be d the dimension?

[tscrim]

What I mean is that isn't block_dim == d?

[tkarn]

I originally made that assumption as well, but it causes the test which is the computation of the orthogonal complement as the kernel of a scalar product to fail, because the module is d-dimensional, but the scalar product is 1-dimensional.

[tscrim]

Ah, right, it doesn't require the codomain to be the same as the domain.