Fundamentally flawed

[Stefan van Zwam]

Hi all,

I encountered a major annoyance. Suppose you want to do a short computation with a partial field, and you don't want to go through the whole finite field business, so you grab a polynomial ring:

sage: H5.<a,b,c> = FractionField(PolynomialRing(ZZ, ['a', 'b', 'c']))

Then you build a set of fundamental elements. But there's trouble:

sage: S = set([1/(1-c)])
sage: (-1)/(c-1) in S
False

Unfortunately this becomes a problem in a quite well-optimized part of the code (the linear_extensions method and its friends). Can we afford to have a more robust test (in _line_cross_ratio_test)? I could imagine having an extra option to that function, "fast=False". The default would then check something like

if not any( s / r / t - p == 0 for p in fundamentals):
return False

and the fast version would be our current version.

Note that something needs to happen, because right now the code will return wrong answers.

Thoughts?

--Stefan.

[Volker Braun]

This is basically a consequence of http://www.sagemath.org/doc/developer/coding_in_python.html#the-hash-special-method

sage: 1/(1-c) == -1/(c-1)

True

sage: hash(1/(1-c))

-12672173288405813

sage: hash(-1/(c-1))

-12671077150117410

Ideally, the FractionField elements would either be automatically reduced, or have the hash computed from their reduced form if the automatic reduction has too much of a performance impact.

A workaround is to only store reduced fraction field elements in python collections.

[Stefan van Zwam]

The problem in this case is that the set membership test occurs pretty deep inside Sage library code (trac 7477) that is written in a generic way: it should work for any ring or field. And for the main use case, finite fields, we definitely want to use the fast set membership test.

--Stefan.

[Rudi Pendavingh]

>
> The problem in this case is that the set membership test occurs pretty deep inside Sage library code (trac 7477) that is written in a generic way: it should work for any ring or field. And for the main use case, finite fields, we definitely want to use the fast set membership test.
>

Then perhaps a subclass of LinearMatroid for finite fields should contain the optimized routines, and the top class the general routines ( with the 'fast' option as you suggested).

---Rudi

[Volker Braun]

On Monday, August 5, 2013 10:16:10 PM UTC+1, Stefan van Zwam wrote:

The problem in this case is that the set membership test occurs pretty deep inside Sage library code (trac 7477) that is written in a generic way: it should work for any ring or field. And for the main use case, finite fields, we definitely want to use the fast set membership test.

Thats why I said that the best solution is just to fix the hash method for fraction fields of polynomial rings. Sure, you can implement a conditional workaround just in the matroid code but that would be less than ideal.  

[Stefan van Zwam]

Ah, I misunderstood your first message. I'll have a look at it soon, but I'm already worried about fraction fields of polynomials over, say, ZZ.

--Stefan.

--
 
---
You received this message because you are subscribed to the Google Groups "sage-matroid" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-matroid...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Volker Braun]

On Monday, August 5, 2013 11:18:14 PM UTC+1, Stefan van Zwam wrote:

Ah, I misunderstood your first message. I'll have a look at it soon, but I'm already worried about fraction fields of polynomials over, say, ZZ.

Just divide by the gcd of all coefficients. And pick the sign to make the numerator leading coefficient positive, say.