finite free module iterator

[Rado]

Hello,

I needed to get all elements of a vector-space over a finite field. Here are three approaches, each ~ 10x faster than the previous:

A = random_matrix(GF(5), 5, 10)

#------

timeit('all2 = A.row_space().list()')

5 loops, best of 3: 1.07 s per loop

#------

timeit('all = [i*A for i in VectorSpace(GF(5),5)]')

5 loops, best of 3: 166 ms per loop

#------

def free_mod_iter(module):

    R = module.base_ring()

    L = module.gens()

    if len(L) == 1:

        for i in R:

            yield i * L[0]

    else:

        el = L[0]

        for rest in gen(L[1:], R): 

            for i in R:

                yield rest + i * el

timeit('list(free_mod_iter(A.row_space()))')

25 loops, best of 3: 14.7 ms per loop

sage: list(free_mod_iter(A.row_space())).sort() == A.row_space().list().sort()

True

Is the 3rd solution, already in Sage? It's basically the same as a generator for rational points on elliptic curves that Robert Bradshaw showed me at Sage Days 22. If not, it probably should be, but I am not sure where it fits (free_module.py is a 5k loc).

[Rado]

Ops, the code posted is not quite right (it's in the middle of a rewrite :)). Use the following

def inner_iter(L, R):

    if len(L) == 1:

        for i in R:

            yield i * L[0]

    else:

        el = L[0]

        for rest in inner_iter(L[1:], R): 

            for i in R:

                yield rest + i * el

                

def free_mod_iter(module):

    R = module.base_ring()

    L = module.gens()

    return inner_iter(L, R)

[Rob Beezer]

On Jul 16, 3:37 am, Rado <rki...@gmail.com> wrote:
> A = random_matrix(GF(5), 5, 10)
> #------
> timeit('all2 = A.row_space().list()')

This looks basically like:

sage: A = random_matrix(GF(5), 5, 10)
sage: V = A.row_space()
sage: it = V.__iter__()
sage: time x = list(it)
Time: CPU 0.58 s, Wall: 0.59 s
sage: timeit("x = list(it)")
625 loops, best of 3: 2.19 µs per loop

Note the results are cached, so watch out using timeit. (There is a
general method, _list_from_iterator_cached() in sage/structure/
parent.pyx.)

Perhaps your recursive approach could speed up

sage.modules.free_module.FreeModule_generic.__iter__

but maybe only in the case of a finite base ring? The current
iterator is allowed to run infinitely long over an infinite base ring,
in the event that it is used to obtain some finite collection of
elements. But it looks like the current iterator never escapes the
first coordinate (say with QQ^2), which might be the same with your
proposed iterator.

And where to put it may now be a moot question. ;-)

Rob

[Rado]

This should mean that there is no caching happening. 

sage: timeit('list(random_matrix(GF(5),5,10).row_space())')

5 loops, best of 3: 1.04 s per loop

sage: timeit('list(free_mod_iter(random_matrix(GF(5),5,10).row_space()))')

25 loops, best of 3: 14.6 ms per loop

Yeah, this iterator is "stuck" on the first coordinate on infinite base_rings(). it should be possible to write a diagonal iterator using a queue.

The old iterator in FreeModule_generic __iter__ does not maintain any state as it goes along. It takes (r1,r2,r3) -> r1*v1 + r2*v2 + r3*v3 by calling linear_combination_of_basis on the r-vector. Inside it does tons of type-checking, also coerces into Sequence once for each r-vector (this explains why naive multiplication gets you x10).

At each step it increments one r_i (most of the time) and goes through the scalar multiplication (all but one r's are the same) and vector addition of the whole \sum r_i*v_i. Using yield such computations are not repeated, which gives you another ~ 10x speed-up.