Opened 6 years ago

Closed 6 years ago

#12528 closed enhancement (fixed)

Little optimizations in CombinatorialFreeModule

Reported by: nthiery Owned by: jason, was
Priority: major Milestone: sage-5.0
Component: linear algebra Keywords:
Cc: sage-combinat, jhpalmieri Merged in: sage-5.0.beta6
Authors: Nicolas M. Thiéry Reviewers: Florent Hivert, John Palmieri
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12484 Stopgaps:

Description (last modified by nthiery)

With the attached optimizations, the following typical calculation from Andrew Matthas goes twice faster (it involves a lot of arithmetic on module elements with very few terms)::

    sage: W = SymmetricGroup(4)
    sage: W.cartan_type = lambda: CartanType("A3")
    sage: R=FractionField(PolynomialRing(ZZ,'x')); x=R.gen()
    sage: H=IwahoriHeckeAlgebraT(W,x,base_ring = R)
    sage: L=[H.one()];                   # define Jucys-Murphy elements
    sage: for k in xrange(1,4): L.append(H._q1**-1*H.algebra_generators()[k]*L[k-1]*H.algebra_generators()[k])

    sage: content=[0,1,-1,0]   # content vector for Tableau([[1,2],[3,4]])

    sage: %time prod( (L[k]-x**c)/(x**content[k]-x**c) for k in xrange(len(content)) for c in xrange(-k,k+1) if c<>content[k])
    CPU times: user 2.26 s, sys: 0.00 s, total: 2.27 s
    Wall time: 2.27 s

Was 4.5s before the patch.

The patch also involve two changes in the Iwahori Hecke Algebra code to use better primitives of CombinatorialFreeModule?.

(trivial syntactical dependency upon #12484)

Attachments (1)

trac_12528_free_module-optimize-nt.patch (8.3 KB) - added by nthiery 6 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 6 years ago by nthiery

  • Status changed from new to needs_review

comment:2 Changed 6 years ago by nthiery

  • Dependencies set to #12484
  • Description modified (diff)

comment:3 follow-up: Changed 6 years ago by nthiery

  • Cc jhpalmieri added
  • Reviewers set to Florent Hivert, John Palmieri

The new patch fixes a (trivial?) doctest failure in sage.algebra/steenrod_algebra/steenrod_algebra.py (John, please double check it!), and includes further review improvements from Florent.

All test pass. I let Florent put the final positive review once John will have given his green light.

comment:4 in reply to: ↑ 3 ; follow-up: Changed 6 years ago by hivert

Replying to nthiery:

All test pass. I let Florent put the final positive review once John will have given his green light.

While we are waiting for John, can you add a proper commit message ? Jeroen will ask you to do so anyway...

Changed 6 years ago by nthiery

comment:5 in reply to: ↑ 4 Changed 6 years ago by nthiery

Replying to hivert:

While we are waiting for John, can you add a proper commit message ? Jeroen will ask you to do so anyway...

Shoot, I was sure I had done it. Well, now its done :-)

comment:6 follow-up: Changed 6 years ago by jhpalmieri

The Steenrod algebra change looks fine to me.

comment:7 in reply to: ↑ 6 Changed 6 years ago by hivert

  • Status changed from needs_review to positive_review

Replying to jhpalmieri:

The Steenrod algebra change looks fine to me.

Then it's good to go !

comment:8 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.0.beta6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.