On Mon, 30 Oct 2006 19:21:09 -0800, David Harvey
<[EMAIL PROTECTED]> wrote:
> On Oct 30, 2006, at 7:44 PM, Martin Albrecht wrote:
>> On Monday 30 October 2006 22:38, David Harvey wrote:
>>> I want to start applying our arithmetic architecture to _mul_. The
>>> fast
>>> pathway for __mul__ needs to be able to quickly identify the case of
>>> multiplying an element of a base ring of an algebra by an element of
>>> the algebra (or commutative algebra as the case may be). The
>>> sanest way
>>> to do this really fast is for base_ring to be a cdef attribute of
>>> Algebra and CommutativeAlgebra.
>>>
>>> Unfortunately this is going to run us into multiple inheritance
>>> problems with matrices (and possibly other things). Currently in
>>> William's development code, the MatrixSpace_generic class inherits
>>> from
>>> Generators. This has a bunch of cdef'd attributes. So it won't be
>>> possible to simultaneously inherit from Algebra too, if Algebra has a
>>> cdef'd base_ring.
>>
>> I've got an evil idea: What if Generators had a base_ring cdef'd? I
>> know that
>> this makes no sense for general Generators but it would only be one
>> single
>> pointer which isn't even visible to Python (i.e. not confusing the
>> higher
>> levels). A big fat warning in a comment where it is defined would
>> clarify
>> everything for library developers. It's a hack and probably to
>> reject but I
>> guess it should be on the table before being rejected.
>
> I had thought of that too. It's a hack. REJECT.
Generators is badly named. It should be SageObjectWithGenerators, since
inheritence is an "is a" relationship, and everything that inherits
from a class should satisfy an "is a" relationship with it. E.g.,
a polynomial Ring "is a" object with generators. David Kohel and I
discussed this sort of algebra stuff a long time ago, and decided that
if possible most parent objects in SAGE should have some sort of base
structure, e.g., a base ring. So I propose:
class SageObjectWithGenerators(SageObject):
cdef gens (whatever that var is called)
class SageObjectOverBaseWithGenerators(SageObjectWithGenerators):
cdef object base_ring
...
Then things like rings, matrix spaces, etc., will all inherit from
SageObjectOverBaseWithGenerators. Other things which don't
have a base ring (e.g., monoids, groups, etc.) inherit from
SageObjectWithGenerators. Does that work.
NOTE: Actually, technically according to Bourbaki those classes should be
called "MagmaObjectWithGenerators", etc., which is where the word
"magma" comes from (for the computer algebra system), but that would
cause way too much cconfusion.
>>> On the other hand.... maybe this test doesn't need to be so fast
>>> after
>>> all. We can still test first for matching RingElement parents very
>>> quickly. If it's true that algebra elements are generally quite
>>> complicated objects, then probably a python attribute lookup is not
>>> such a big deal. Maybe I'm over-optimising.
>>
>> About the quite complicated objects: I guess the simplest/smallest
>> algebra
>> element I can think of is a dense matrix over GF(2), i.e. a
>> bitstring. That's
>> something SAGE should have in a very fast way.
>
> This is true.
>
> For such an object, here's what I know about the memory requirements
> for each element:
>
> * Python's ob_type field --- a single pointer
> * Python's reference count field --- a single word integer
> * _parent --- a single pointer
> * Some info describing the matrix data. I would expect in a typical
> implementation, this would be a pointer to a block of bits describing
> the entries. A really optimised implementation would probably store
> this inline with no separate pointer, but it would have to know the
> matrix size statically.
>
> So adding a base_ring pointer increases memory consumption by 25% at
> most. Actually it's less than that, due to overheads of memory
> management.
I'm right now opposed to storing the base ring in the object. To me this
seems like more of a hack than storing the base ring in Generators.
Moreover, in addition to increased memory usage, there may be efficiency
issues, since we have to *set* the base_ring pointer whenever we
initialize an element. Also, there could be algebras where the storage
for elements really is tiny, e.g., QQ(i) viewed as an algrebra over
itself in some funny way.
William
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
