Opened 6 years ago

Last modified 4 years ago

#15296 new defect

LinearMatroid can't use sets for fundamentals

Reported by: Stefan Owned by:
Priority: major Milestone: sage-6.4
Component: matroid theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by Stefan)

Several methods in LinearMatroid? have an option fundamentals. Internally, this gets used as a set, and we test things like p in fundamentals. Even though both p and the elements of fundamentals come from the same ring or field, it is not guaranteed (and sometimes false) that p == q implies hash(p) == hash(q).

The default behavior of these methods should therefore be to test for equality with each member of fundamentals, instead of relying on the in keyword. An optional argument (such as use_fast_fundamental_test with default option False can be used to speed up computations when appropriate.

See #15297 for a change that makes the fast_fundamental_test work for a larger group of fields.

Change History (5)

comment:1 Changed 6 years ago by Stefan

  • Description modified (diff)

comment:2 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 4 years ago by Rudi

Hi Stefan,

There are several methods in LinearMatroid? that need to be adjusted for this, roughly _line_ratios() through _cross_ratio_test() in the linear_matroid.pyx source. I would suggest writing a second version for each of these routines which is safe for field of fractions, keeping the unsafe but fast version to use for `safe' fields. The initializer of LinearMatroid? should sniff out the unsafe fields and make sure that in such cases the safe methods get called throughout.

Now in c++ I would know how to do this, simply let the initializer replace the the pointers to the unsafe methods by pointers to their corresponding safe versions, but can this be done in cython? If so, I propose I write the safe versions and you fix up the initializer to finish up.

Rudi

Note: See TracTickets for help on using tickets.