MemoryError raised by WordMorphism.fixed_points method

[seblabbe]

The following bug was reported to me by Timo Jolivet last July 2012. It is still there is sage-5.3:

sage: s = WordMorphism({1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]})
sage: (s^7).fixed_points()
[word: 122..., word: 2,3,4,...]
sage: (s^7).reversal().fixed_points()
MemoryError [...]

Also reported by Timo Jolivet in October 2012 the following hangs forever:

sage: s = WordMorphism("1->321331332133133,2->133321331332133133,3->2133133133321331332133133")
sage: (s^2).fixed_points()

CC: @sagetrac-tjolivet

Component: combinatorics

Author: Sébastien Labbé

Reviewer: Timo Jolivet

Merged: sage-5.5.rc0

Issue created by migration from https://trac.sagemath.org/ticket/13668

[seblabbe]

comment:1

Also reported by Timo Jolivet in October 2012 the following hangs forever:

sage: s = WordMorphism("1->321331332133133,2->133321331332133133,3->2133133133321331332133133")
sage: (s^2).fixed_points()

It might be related to the bug in the description of this ticket... I will wait until a solution is found for the first before creating a new ticket for the second as the solution might fix both.

[seblabbe]

Attachment: trac_13668-sl.patch.gz

Tested on sage-5.2

[seblabbe]

comment:2

In fact, this bugs comes from the _fixed_point_iterator method which expand a possibly long word as a list :

sage: s = WordMorphism({1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]})
sage: s7 = s^7
sage: s7r = s7.reversal()
sage: M = matrix(s7r)^10             
sage: max(flatten(map(list, M)))
274861440
sage: s7r10 = s7r^10
sage: it = s7r10._fixed_point_iterator(1)
sage: it.next()
Traceback (most recent call last):
...
in _fixed_point_iterator(self, letter)
   1561             ('a', 1)
   1562         """
-> 1563         w = list(self.image(letter))
   1564         while True:
   1565             for a in self.image(w.pop(0)):

MemoryError:

[seblabbe]

comment:3

It might be related to the bug in the description of this ticket... I will wait until a solution is found for the first before creating a new ticket for the second as the solution might fix both.

Indeed, the solution (which make use of iterators instead of lists) fixes both problems. I just attached a patch. Needs review!

[seblabbe]

comment:4

Moreover, I am getting some timing improvements due to the change of the code of fixed_points method which do not depend anymore on the periodic_points method :

BEFORE:

   sage: f = WordMorphism('a->ab,b->cab,c->bcc')     
   sage: %timeit f.fixed_points()           
   125 loops, best of 3: 2.1 ms per loop        

AFTER:

   sage: f = WordMorphism('a->ab,b->cab,c->bcc')
   sage: %timeit f.fixed_points()               
   625 loops, best of 3: 340 µs per loop   

[sagetrac-tjolivet]

Author: Sébastien Labbé

[sagetrac-tjolivet]

Reviewer: Timo Jolivet

[sagetrac-tjolivet]

comment:7

I don't have any problematic examples anymore and the patch changes are simple and effective, so positive review.

[sagetrac-tjolivet]

comment:8

Note that this patch also fixes the following problem, thanks to better implementation:

sage: s = WordMorphism({1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]})
sage: (s.reversal()^7).fixed_points()
MemoryError
[...]

[jdemeyer]

Merged: sage-5.5.beta2

[jdemeyer]

Changed merged from sage-5.5.beta2 to sage-5.5.beta3

[jdemeyer]

Changed merged from sage-5.5.beta3 to sage-5.5.rc0