Opened 13 months ago
Last modified 4 months ago
#32317 needs_work enhancement
Remove overhead from `annihilator_basis`
Reported by:  tkarn  Owned by:  

Priority:  major  Milestone:  sage9.7 
Component:  categories  Keywords:  gsoc2021 optimization annihilator 
Cc:  tscrim, tkarn  Merged in:  
Authors:  Trevor K. Karn  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/tkarn/annihilator_basis_optimization_32317 (Commits, GitHub, GitLab)  Commit:  5b1d22ac949bca7634c370637d291dd5d3fbf401 
Dependencies:  Stopgaps: 
Description
There are a few unnecessary matrices created in the FiniteDimensionalModulesWithBasis.annihilator_basis()
method. This streamlines them leading to a significant improvement in performance.
Attachments (1)
Change History (15)
comment:1 Changed 13 months ago by
comment:2 Changed 13 months ago by
 Branch set to u/tkarn/annihilator_basis_optimization_32317
 Commit set to d548c77d55f158f0f85ccfeeabd10a7d457040e6
 Status changed from new to needs_review
New commits:
d548c77  Optimize annihilator_basis method

comment:3 Changed 13 months ago by
 Status changed from needs_review to needs_work
Doctests are failing because you have changed how the matrix augmentation works:
sage t long randomseed=0 src/sage/categories/finite_dimensional_lie_algebras_with_basis.py # 1 doctest failed sage t long randomseed=0 src/sage/categories/finite_dimensional_algebras_with_basis.py # 4 doctests failed sage t long randomseed=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'
...
comment:4 Changed 13 months ago by
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)
comment:5 Changed 13 months ago by
 Commit changed from d548c77d55f158f0f85ccfeeabd10a7d457040e6 to feb51d81b5fbfe14db2186db5107ebfb30cf51e7
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
feb51d8  Assign matrix entries elementbyelement

comment:6 Changed 13 months ago by
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 elementbyelement

comment:7 Changed 13 months ago by
 Commit changed from feb51d81b5fbfe14db2186db5107ebfb30cf51e7 to 5b1d22ac949bca7634c370637d291dd5d3fbf401
comment:8 Changed 13 months ago by
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.
comment:9 Changed 13 months ago by
Don't we know that the number of entries in the output vector is going to be d
the dimension?
comment:10 Changed 13 months ago by
What I mean is that isn't block_dim == d
?
comment:11 Changed 13 months ago by
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 1dimensional.
comment:12 Changed 13 months ago by
Ah, right, it doesn't require the codomain to be the same as the domain.
comment:13 Changed 8 months ago by
 Milestone changed from sage9.5 to sage9.6
comment:14 Changed 4 months ago by
 Milestone changed from sage9.6 to sage9.7
With the original code:
With the updated code: