#8871: Finding digit sets for dilation matrices
-----------------------------+----------------------------------------------
   Reporter:  ecurry         |       Owner:  Eva Curry   
       Type:  enhancement    |      Status:  needs_work  
   Priority:  minor          |   Milestone:  sage-feature
  Component:  number theory  |    Keywords:              
     Author:  Eva Curry      |    Upstream:  N/A         
   Reviewer:                 |      Merged:              
Work_issues:                 |  
-----------------------------+----------------------------------------------
Changes (by ecurry):

  * status:  new => needs_work


Comment:

 Replying to [ticket:8871 ecurry]:
 Function with centered canonical digit set method implemented:

 {{{
 def finddigits(A,method):
     """
     To Do:
         Implement "minimal" method
         Implement "colinear" method
         Can the algorithm for "centered" method be made more efficient? -
 It is *slow* already in the 4x4 case!
         How to input method as a name rather than as a string?

     Inputs:
         A - a dilation matrix (square, integer entries, all eigenvalues l
 with |l|>1)
         method - centered (for centered canonical digit set);
                  minimal (for minimum modulus digit set);
                  colinear (for colinear digit set, if exists)
     Outputs:
         a standard digit set for A using the designated method

     EXAMPLES:
         A = Matrix(ZZ,[[2,0],[-8,-1]])
         finddigits(A,"centered")
         [(0, 0), (1, -4)]

         B = Matrix(ZZ,[[1,2,3],[1,0,2],[1,-2,-1]])
         finddigits(B,"centered")
         [(0, 0, 0), (1, 0, -1), (1, 1, 0), (2, 1, -1)]

         C = Matrix(ZZ,[[1,0,1,1],[-1,1,1,1],[1,2,0,-1],[-2,0,0,1]])
         finddigits(C,"centered")
         [(0, -1, 0, -1), (0, 0, 0, 0), (0, 1, 0, 1)]
     """
         from sage.combinat.permutation import Arrangements
     from sage.geometry.polyhedra import Polyhedron
     from sage.matrix.all import matrix
     d = A.ncols()

     """
     Method: centered
     F = (-1/2,1/2]^d
     G = AF, considered as a Polyhedron (so closed on all sides)
     find test_points := list of too many integer lattice points that might
 be in G
     uses the half-plane inequalities defining G to find integer lattice
 points that are in the interior of G, together with those on just half of
 the facets of G
     """
     if method=="centered":
         prelist=[]
         for i in range(2**d):
             if i-2**(d-1) >= 0: prelist.append(1)
             if i-2**(d-1) < 0: prelist.append(-1)
         matF = (1/2)*matrix(Arrangements(prelist,d).list()).transpose()
         matG = A*matF
         vertG = matG.columns()
         G = Polyhedron(vertG)
         R = floor(G.radius())
         pretest = [floor(i/d) for i in range(-R*d,(R+1)*d)]
         test_points = matrix(Arrangements(pretest,d).list())
         ieqlist = list(G.inequality_generator())
         excl_ineq = ieqlist[0:d]
         incl_ineq = ieqlist[d:2*d]
         digitslist=[]
         for p in test_points:
             i = 0
             while i < d and excl_ineq[i].interior_contains(p) and
 incl_ineq[i].contains(p):
                 i = i+1
             if i == d:
                 digitslist.append(p)
         return digitslist

     if method=="minimal":
         return "Minimum modulus digit set not yet implemented."

     if method=="colinear":
         return "Colinear digit set not yet implemented."
 }}}

-- 
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8871#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, 
and MATLAB

-- 
You received this message because you are subscribed to the Google Groups 
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to 
[email protected].
For more options, visit this group at 
http://groups.google.com/group/sage-trac?hl=en.

Reply via email to