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 tgagne

  • Authors set to Thomas Gagne
  • 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: Changed 4 years ago by 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.

comment:3 Changed 4 years ago by tgagne

  • Dependencies changed from 3a14bb2edd87281873d4f2b49d1c5d210c4a4a3c to #18714

comment:4 in reply to: ↑ 2 Changed 4 years ago by tgagne

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 vdelecroix

  • 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)
Note: See TracTickets for help on using tickets.