Opened 4 years ago
Last modified 4 years ago
#18935 needs_work enhancement
Finite field linear function to polynomial
Reported by: | tgagne | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.10 |
Component: | finite rings | Keywords: | finite field, polynomial |
Cc: | rbeezer, malb, SimonKing | Merged in: | |
Authors: | Thomas Gagne | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | u/tgagne/finite_field_matrix_to_polynomial (Commits) | Commit: | 1608ecbe6702539fdbcbfef4f6b27dbe39d275dc |
Dependencies: | #18714 | Stopgaps: |
Description
Adding a method which converts a linear function over a finite field in the form of a matrix into a polynomial over that finite field.
This method uses dual bases to perform this calculation in milliseconds over fields such as GF(3^8)
, whereas a naive Lagrange interpolation calculation can take several minutes to get the same result.
Change History (5)
comment:1 Changed 4 years ago by
- Branch set to u/tgagne/finite_field_matrix_to_polynomial
- Commit set to 1608ecbe6702539fdbcbfef4f6b27dbe39d275dc
- Component changed from PLEASE CHANGE to finite rings
- Dependencies set to 3a14bb2edd87281873d4f2b49d1c5d210c4a4a3c
- Priority changed from major to minor
- Status changed from new to needs_review
- Type changed from PLEASE CHANGE to enhancement
comment:2 follow-up: ↓ 4 Changed 4 years ago by
comment:3 Changed 4 years ago by
- Dependencies changed from 3a14bb2edd87281873d4f2b49d1c5d210c4a4a3c to #18714
comment:4 in reply to: ↑ 2 Changed 4 years ago by
Replying to jdemeyer:
The dependency should be a trac ticket, not a commit. Do you have a ticket for your dependency? If yes, write the ticket number there. If no, just remove the dependency.
Whoops! Thanks for pointing that out!
comment:5 Changed 4 years ago by
- Milestone changed from sage-6.8 to sage-6.10
- Reviewers set to Vincent Delecroix
- Status changed from needs_review to needs_work
Why base_matrix_to_polynomial
and not simply matrix_to_polynomial
?
poly(el)
is simpler than poly.subs(x=el)
This test is really bad
not all([matrix[i,j] in self.base_ring() for i in range(n) for j in range(n)])
You have several better options
matrix.base_ring() == self
matrix = matrix.change_ring(self)
(this might make an unneeded copy)
If var
is already an element of a polynomial ring then you should not recreate another one. In particular, I might want to work over QQ[x,y] and obtain a polynomial in the variable x in this specific ring. I would simply do
if isinstance(var, str): from sage.rings.polynomial.polynomial_ring import polygen var = polygen(self)
If the matrix is sparse you are doing a lot of unwanted computations. I would actually separate
if matrix.is_sparse(): entries = matrix.nonzero_positions() else: entries = ((i,j) for i in range(n) for j in range(n)) for i,j in entries: # do the looping
And add a test with a huge matrix with very few coefficients like
sage: M = matrix(GF(3,4), 1000, sparse=True) sage: M[0,3] = 1
The operation gen**i
is actually very fast. So I would avoid computing the list basis
and replace basis[i]
with gen**i
You should not compute a list and then make a sum of elements. Do everything at once
s = 0 for i in range(10): s += 1
is much better than
l = [] for i in range(10): l.append(i) s = sum(l)
The dependency should be a trac ticket, not a commit. Do you have a ticket for your dependency? If yes, write the ticket number there. If no, just remove the dependency.