Opened 9 years ago

Closed 9 years ago

#13640 closed enhancement (fixed)

q-numbers coutings flags stable under a nilpotent endomorphism

Reported by: caruso Owned by: sage-combinat
Priority: major Milestone: sage-5.5
Component: combinatorics Keywords: combinatorics, q-numbers
Cc: Merged in: sage-5.5.beta2
Authors: Xavier Caruso Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by chapoton)

Here is a small patch implementing the function q_jordan which computes the number of complete flags in F_qn stable under a nilpotent linear endomorphism given by its Jordan type.

This function is used in ticket #13215.

Apply trac_13640_qjordan-4.patch

Attachments (1)

trac_13640_qjordan-4.patch (4.2 KB) - added by chapoton 9 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 9 years ago by caruso

  • Authors set to caruso
  • Status changed from new to needs_review

comment:2 Changed 9 years ago by caruso

  • Description modified (diff)

comment:3 follow-up: Changed 9 years ago by chapoton

  • Status changed from needs_review to needs_work
  • Work issues set to doctest, cached_function
  • it does not look good to use a global variable dict_jordan
  • You should instead use the decorator @cached_function to cache the results of a procedure.
  • every procedure should be doctested.
  • do you really need two procedures to do that ?

comment:4 in reply to: ↑ 3 Changed 9 years ago by caruso

  • Status changed from needs_work to needs_info

Replying to chapoton:

  • it does not look good to use a global variable dict_jordan
  • You should instead use the decorator @cached_function to cache the results of a procedure.
  • every procedure should be doctested.
  • do you really need two procedures to do that ?

The main problem is that lists are not hashable. Therefore a cached function can't take a list as an argument and, consequently, I can't use the decorator @cached_function to cache the result of q_jordan (at least without changing the prototype of this function). Moreover, working with just one function would imply to check the shape of the inputs at each recursive call (which is of course useless and may cost a lot).

I propose another implementation (using @cached_function and a nested function) in trac_13640_qjordan-2.patch. Please tell me whether it's better or not according to you.

comment:5 follow-up: Changed 9 years ago by chapoton

Thinking again about this, it now seems to me that q_jordan should be a method of the class Partitions. This is really the job of a partition constructor to check that something is a partition.

Maybe this would also solve the hash problem ?

comment:6 follow-up: Changed 9 years ago by caruso

Ok. I attach a third implementation where q_jordan is a method of Partition. It works but it's quite slow. (I suspect a problem with @cached_method, but I'm not sure.)

comment:7 in reply to: ↑ 5 ; follow-up: Changed 9 years ago by nthiery

Replying to chapoton:

Thinking again about this, it now seems to me that q_jordan should be a method of the class Partitions. This is really the job of a partition constructor to check that something is a partition. Maybe this would also solve the hash problem ?

Sorry I did not comment earlier; the network at the airport was crappy. It would certainly be natural for the input to q_jordan to be a partition, and it should indeed fix the problem.

That being said, this does not necessarily imply that q_jordan should be a method of partitions. It might be more natural to put instead q_jordan with the other q-analogues, as a function taking a partition as input.

I let you judge which option is best.

Cheers,

Nicolas

comment:8 in reply to: ↑ 6 Changed 9 years ago by nthiery

Replying to caruso:

Ok. I attach a third implementation where q_jordan is a method of Partition. It works but it's quite slow. (I suspect a problem with @cached_method, but I'm not sure.)

Did you run it with %prun? Among other things, it will tell you how many times the method is called, from which you can check whether the cache works.

Ah, in this situation, you probably want to use @cached_in_parent. Otherwise, the result for p.q_jordan() is cached in p. So if you recreate an identical partition as p2, p2.q_jordan won't see the cache in p.

Cheers,

Nicolas

comment:9 Changed 9 years ago by chapoton

apply trac_13640_qjordan-4.patch

ok, here is a new variant. Still slow, I am afraid.

comment:10 Changed 9 years ago by chapoton

apply trac_13640_qjordan-4.patch

here is a new one, thanks to Nicolas comments : with cached_in_parent_method

comment:11 Changed 9 years ago by chapoton

  • Status changed from needs_info to needs_review

comment:12 in reply to: ↑ 7 ; follow-up: Changed 9 years ago by caruso

Replying to nthiery:

That being said, this does not necessarily imply that q_jordan should be a method of partitions. It might be more natural to put instead q_jordan with the other q-analogues, as a function taking a partition as input.

I let you judge which option is best.

Well, I prefer this. Therefore I propose another new patch with the function q_jordan in q_analogues but taking a Parition as input. (And note that @cached_function works well with this solution.)

comment:13 in reply to: ↑ 12 Changed 9 years ago by nthiery

Replying to caruso:

Well, I prefer this. Therefore I propose another new patch with the function q_jordan in q_analogues but taking a Parition as input.

Sounds good to me.

(And note that @cached_function works well with this solution.)

Yup.

Changed 9 years ago by chapoton

comment:14 Changed 9 years ago by chapoton

apply trac_13640_qjordan-4.patch

here is a new patch, not touching partition.py at all

this seems ok to me

let us wait for the green light

comment:15 Changed 9 years ago by chapoton

  • Authors changed from caruso to Xavier Caruso
  • Description modified (diff)
  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, positive review

comment:16 Changed 9 years ago by jdemeyer

  • Work issues doctest, cached_function deleted

I assume the positive review implies that the work issues have been solved?

comment:17 Changed 9 years ago by chapoton

Yes, indeed. I should have removed them, sorry.

comment:18 Changed 9 years ago by jdemeyer

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