On Friday, August 19, 2016 at 1:43:30 PM UTC-7, Joseph Hundley wrote:
>
> There are two reasons I was planning to have AbstractAlgebraicGroup be
> UniqueRepresentation
> (1) The passage in this tutorial
> <http://sporadic.stanford.edu/thematic_tutorials/coercion_and_categories.html>
> which
> reads
>
<snip>
It really depends on what you need to do to construct the parent. In most
cases, you just end up storing some of the construction parameters. Reusing
parents that were already constructed can save some memory, but the usual
pattern is that you construct only a few parents, which get naturally
passed around anyway. Reusing a parent that is handed to you is obviously
much more efficient than reusing a parent by trying to get a hold of it via
its construction parameters.So if you need UniqueRepresentation to limit
the number of parents in memory, it's probably a good idea to think of ways
of restructuring your computation (there may be cases where you can't,
though).
Using UniqueRepresentation does force a upfront cost, though: construction
parameters need to be processed so that they can be used for lookup in a
global dictionary to see if equivalent parameters have already been used to
construct such an object, and then this lookup needs to happen. In many
scenarios this search will come up empty, in which case you've just
incurred a cost without a direct gain. So whether UniqueRepresentation is a
performance gainer really depends on the scenario. Most of the time it is
not, so I'd say the rationale given in the tutorial is misleading.
UniqueRepresentation is needed in the coercion framework: If two different
sources produce polynomials in Q[x,y], the user would expect to be able to
combine them because they look indistinguishable to the user. In the
coercion framework it turned out to be much more efficient if the parents
of those two polynomials ARE indeed equal. The construction parameters in
this case are indeed easy to compare because it's just (Q,('x','y')), where
Q is a UniqueRepresentation itself, so you can recognize it by identity
itself.
As a consequence, if you're implementing a ring type that itself is likely
to be used as a base ring for a polynomial ring (or matrices etc.), you
should probably try to make it UniqueRepresentation. But otherwise it's not
immediately clear you'll be getting a benefit from it.
(2) It seems to me to make sense mathematically, since, mathematically
> speaking, the split connected reductive algebraic group with based root
> datum B is a unique mathematical object.
>
Yes, but in what category? and is it unique up to unique isomorphism?
> I admit I don't understand the "cost" of "non-locality"? Can you point me
> somewhere I could read up on relevant issues? Are there rules of thumb for
> when parents should and should not be UniqueRepresentation?
>
A possible example of the risks you run:
Suppose
K=NumberField(<something large>)
K.compute_classgroup( method="heuristic and conditional") #[*]
<do stuff, delete K. Suppose K is not yet garbage collected>
L=NumberField(<same thing>) #this will now get you K back!!!
L.classgroup() #suppose this gets you the class group cached on L, i.e.,
the one computed at [*]
alternatively, if K had been garbage collected already
L=NumberField(<same thing>) #this is now a fresh version
L.classgroup() #no classgroup info cached, you trigger (unconditional)
computation.
The fact that your result is now dependent on what happened to be in memory
is of course very bad. It makes your system unreliable. That means that
this pattern of "implement a computation routine that can use several
heuristics" combined with "use by default whatever is cached" cannot be
applied to UniqueRepresentation objects, because obviously, caching
heuristic computation results modifies the state of your object in a
noticeable way. UniqueRepresentation object need to take their immutability
quite seriously.
In a different direction: is there a good place to read about how to make
> something be hashable or implement _cache_key()?
>
Hashing in mathematics in general is hard, because you need a==b implies
hash(a)==hash(b), and at the same time you need that a!=b usually implies
hash(a)!=hash(b).
Due to coercion we can't actually do that:
http://www.sagemath.org/git-developer-guide/coding_in_python.html#the-hash-special-method
and it depends on what you want "a==b" to mean in your category whether
it's easy to decide and whether you can find a function Category -> [-2^63
.. 2^63-1] that's not too constant and respects the "==" equivalence.
There are categories in which we know that "a==b" in general is
undecidable. It may be easy for BasedRootDatum (it certainly is in your
reference implementation :-)).
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
