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: sage-9.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:

Status badges

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)

timing-right-kernel.txt (15.9 KB) - added by tkarn 13 months ago.
Timing comparison of changes of commit 5b1d2

Download all attachments as: .zip

Change History (15)

comment:1 Changed 13 months ago by 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)

comment:2 Changed 13 months ago by tkarn

  • Branch set to u/tkarn/annihilator_basis_optimization_32317
  • Commit set to d548c77d55f158f0f85ccfeeabd10a7d457040e6
  • Status changed from new to needs_review

New commits:

d548c77Optimize annihilator_basis method

comment:3 Changed 13 months ago by tscrim

  • Status changed from needs_review to needs_work

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'...

comment:4 Changed 13 months ago by 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)

comment:5 Changed 13 months ago by git

  • Commit changed from d548c77d55f158f0f85ccfeeabd10a7d457040e6 to feb51d81b5fbfe14db2186db5107ebfb30cf51e7

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

feb51d8Assign matrix entries element-by-element

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

feb51d8Assign matrix entries element-by-element

comment:7 Changed 13 months ago by git

  • Commit changed from feb51d81b5fbfe14db2186db5107ebfb30cf51e7 to 5b1d22ac949bca7634c370637d291dd5d3fbf401

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

88bd4c6Optimize annihilator_basis method
5b1d22aBuild matrix to use right_kernel

Changed 13 months ago by tkarn

Timing comparison of changes of commit 5b1d2

comment:8 Changed 13 months ago by 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.

comment:9 Changed 13 months ago by tscrim

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 tscrim

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

comment:11 Changed 13 months ago by 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.

comment:12 Changed 13 months ago by tscrim

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

comment:13 Changed 8 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:14 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.