Dear Nils, Thanks very much for your detailed and thoughtful reply.
Best, Joe On Friday, August 19, 2016 at 5:37:21 PM UTC-4, Nils Bruin wrote: > > 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.
