Opened 9 years ago

Closed 8 years ago

#14848 closed defect (fixed)

Inconsistencies with FreeAlgebra

Reported by: ppurka Owned by: AlexGhitza
Priority: major Milestone: sage-6.2
Component: algebra Keywords:
Cc: nthiery Merged in:
Authors: Travis Scrimshaw Reviewers: Punarbasu Purkayastha
Report Upstream: N/A Work issues:
Branch: 0f9bf9d (Commits, GitHub, GitLab) Commit: 0f9bf9dbdd714429fd290f8c42811e143ca5d70e
Dependencies: Stopgaps:

Status badges

Description

This ticket is "inspired" by this ask.sagemath question.

  1. First, there should be an easy way to get the variables out of an expression in FreeAlgebra?. Compare with the output of polynomial ring.
    sage: F.<x,y>=FreeAlgebra(ZZ)  
    sage: g=4+3*x^7*y^10*x^13
    sage: g.variables()            # <------------   Need this
    sage: h=g._FreeAlgebraElement__monomial_coefficients # This is what we need to do currently
    sage: h.items()[1][0]._element_list     # and do more post processing on the output.
    [(0, 7), (1, 10), (0, 13)]
    
    # Compare with polynomial ring
    sage: F.<x,y> = PolynomialRing(ZZ)
    sage: g=4+3*x^7*y^10*x^13
    sage: g.variables()
    (x, y)
    sage: g=4+3*x^7
    sage: g.variables()
    (x,)
    
  2. The element x^7*y^10*x^13 does not belong to the FreeAlgebra class once it is extracted from the expression. It belongs to FreeMonoid. I think the parent of it should be the same even after we extract it.
    sage: F.<x,y>=FreeAlgebra(ZZ)  
    sage: g=4+3*x^7*y^10*x^13
    sage: h=g._FreeAlgebraElement__monomial_coefficients
    sage: h
    {1: 4, x^7*y^10*x^13: 3}
    sage: hh = h.items()[1][0]; hh
    x^7*y^10*x^13
    sage: hh.parent()
    Free monoid on 2 generators (x, y)
    

Change History (27)

comment:1 Changed 9 years ago by broken_symlink

In regards to my question on ask.sagemath, what I would have really liked was if elements supported indexing. So for example, g[0] should return 4. g[1] should return 3*x7*y10*x13 and then g[1][0] should return 3 i guess, g[1][1] should return x7 and so on. After that, it would be nice to have a way to iterate over 4+3*x7*y10*x13. Maybe we would need len() for that? Has there ever been any talk about implementing something like this?

comment:2 Changed 9 years ago by ppurka

I think this kind of indexing has never been discussed or implemented. There could be several reasons, one of the foremost being that the order in which you enter the expression is not preserved.

sage: F.<x,y>=FreeAlgebra(ZZ)
sage: g = x^5 * y^4 + 3
sage: g
3 + x^5*y^4

comment:3 Changed 9 years ago by sam

elements support iteration, but not indexing, which is appropriate because as ppurka said there is no real ordering on the expressions.

sage: F.<x,y> = FreeAlgebra(ZZ)
sage: g = x^5 * y^4 + 3
sage: for m in g:
....:     print m
....: 
(3, 1)
(1, x^5*y^4)
sage: list(g)
[(3, 1), (1, x^5*y^4)]

all works fine.

Last edited 9 years ago by sam (previous) (diff)

comment:4 Changed 9 years ago by ppurka

  • Milestone changed from sage-5.13 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

Marking as invalid.

comment:5 Changed 9 years ago by ppurka

  • Milestone sage-duplicate/invalid/wontfix deleted
  • Status changed from needs_review to needs_work

Oh. Sorry. I forgot that the original questions were very different from the discussion that ensued.

comment:6 Changed 9 years ago by nbruin

Regarding point 1: Accessing underscore methods is bound to make your life hard: the underscore marks that these are methods/attributes for internal use. The interface is via iteration and using that one can easily accomplish the task:

sage: tuple({n[0] for m in g for n in m[1]})
(y, x)

(i.e., iterate over the terms making up the algebra element, extract the monomial and iterate over that to extract the variables that occur in them).

Whether this needs to be wrapped in a method: The operation isn't very natural: The parent will naturally tell you which variables CAN occur in in algebra elements. Are the ones that don't have all those variables really so special that there needs to be a method to query about that?

For polynomials, the same argument holds, but there it was probably added because some beginners will tend to think of polynomials in terms of SR, where the variables occurring is really a property of the expression and not really of SR.

Concerning point 2: The nested operation above shows why it's natural to return monomials NOT as elements of the algebra: iterating over an algebra element gives the pairs, iterating over a monomial gives variable-exponent pairs. The separation actually provides easier access to the underlying data.

For normal polynomial rings this is probably avoided for efficiency reasons, but you quickly notice that it's a little inconvenient: you end up testing quite a bit whether given polynomials are actually monomials, where doing this via a type check would often in principle be quite doable.

comment:7 Changed 9 years ago by ppurka

  1. The iteration operation was not clear to me at all, and it definitely not possible for beginner to figure it out. By a beginner, I don't mean a beginner to programming - more like a beginner to Sage, or this specific implementation in Sage. I don't find this kind of iteration documented anywhere, even for polynomial rings - maybe it is hidden somewhere. Secondly, the parent FreeAlgebra does have variable_name and variable_names methods. Both are undocumented. The first one, for some weird reason, returns only the first variable as a string. The second one returns all the variables as strings. This is quite useless for programming purposes. It is maybe ok for interactive use, where one can look at this output and then decide to run the F.inject_variables() once one is sure it won't clobber existing variables.
  1. Checking for monomials can be easily done using the list comprehension you provided. Or, even better for efficiency reasons - a for loop with an enumerate that returns False as soon as it encounters a second tuple.
    def is_monomial(self):
        for i,_ in enumerate(self):
            if i == 1:
                 return False
        return True
    

comment:8 follow-up: Changed 8 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to public/algebras/fix_free_algebras-14848
  • Cc nthiery added
  • Commit set to 0de106a5831e0a06e9f8f050f35b15d2d3494981
  • Milestone set to sage-6.2
  • Status changed from needs_work to needs_review

I've made FreeAlgebra inherit from CombinatorialFreeModule; it was close enough to it to begin with and is something Nicolas and I have wanted to do. I've had to hack together a combination of CombinatorialFreeModuleElement and AlgebraElement to pass a doctest in matrix0.pyx where FreeAlgebra is used as a base ring (this inspired #15947). So iterating through an element of FreeAlgera gives index,coeff now (finally consistency! this had bugged me a few times). I've also added a variables method as I don't think it does much harm to have it and support returns the monomials that occur.

Regarding point 2, you can now use the monomial_coefficients() to iterate over pairs (monomial in free algebra, coefficient)] (well...TBH actually it's a dict, so you need an additional items()). Also I agree with Nils' opinion.


New commits:

771ac4cConverted FreeAlgebra to inherit from CombinatrialFreeModule.
a2d1f8dFixes for coercion maps.
5045cc5pyflakes cleanup of free_algebra.py.
b52e779Merge branch 'develop' into public/algebras/fix_free_algebras-14848
c250702(Hack) Fix for making FreeAlgebraElement work as a base ring for matrices.
0de106aAdded variables() method to free module elements.

comment:9 Changed 8 years ago by git

  • Commit changed from 0de106a5831e0a06e9f8f050f35b15d2d3494981 to 23d8c7b0b0204d3b93e67969bfc7f4dccaeb5be6

Branch pushed to git repo; I updated commit sha1. New commits:

23d8c7bMerge branch 'develop' into public/algebras/fix_free_algebras-14848

comment:10 in reply to: ↑ 8 ; follow-up: Changed 8 years ago by nthiery

Replying to tscrim:

I've made FreeAlgebra inherit from CombinatorialFreeModule; it was close enough to it to begin with and is something Nicolas and I have wanted to do.

Yeah!

I've had to hack together a combination of CombinatorialFreeModuleElement and AlgebraElement to pass a doctest in matrix0.pyx where FreeAlgebra is used as a base ring (this inspired #15947).

Any chance to get rid of the use of AlgebraElement? there altogether?

Cheers,

Nicolas

comment:11 in reply to: ↑ 10 Changed 8 years ago by tscrim

Replying to nthiery:

Any chance to get rid of the use of AlgebraElement? there altogether?

Alas, no. We'd have to do something with _rmul_ and _lmul_ of the matrices without introducing a speed regression, which IDK what the best way to do it will be. The alternative would be to remove/change those failing doctests. I've posted an idea I've just had to #15947.

comment:12 Changed 8 years ago by git

  • Commit changed from 23d8c7b0b0204d3b93e67969bfc7f4dccaeb5be6 to 9f49f2f52c1125c8fd32f79a0f25f0032bd6ead3

Branch pushed to git repo; I updated commit sha1. New commits:

51b2e5fMerge branch 'develop' into public/algebras/fix_free_algebras-14848
9f49f2fMerge branch 'develop' into public/algebras/fix_free_algebras-14848

comment:13 Changed 8 years ago by ppurka

  • Status changed from needs_review to needs_work
  • Work issues set to fix doctests

I got one error in doctests:

sage -t --long src/sage/algebras/algebra.py
**********************************************************************
File "src/sage/algebras/algebra.py", line 29, in sage.algebras.algebra.is_Algebra
Failed example:
    is_Algebra(R)
Expected:
    True
Got:
    False
**********************************************************************

Point 1. in description is fixed, but I guess it is harder to fix point 2. So, other than this doctest, the patch looks OK to me.

comment:14 Changed 8 years ago by git

  • Commit changed from 9f49f2f52c1125c8fd32f79a0f25f0032bd6ead3 to 74734db11fe788440775741de7519e9f2b7f7956

Branch pushed to git repo; I updated commit sha1. New commits:

74734dbFixed failing doctests.

comment:15 Changed 8 years ago by tscrim

Fixed (and also some doctests in categories/rings.py that I found).

comment:16 follow-up: Changed 8 years ago by ppurka

I am surprised. I have two questions

  1. Why does this patch affect categories/rings.py?
  2. Can you be more specific with Exception? In which case did you run into the Exception? AttributeError? Can you include it in a doctest?

comment:17 in reply to: ↑ 16 ; follow-up: Changed 8 years ago by tscrim

  • Status changed from needs_work to needs_review

Replying to ppurka:

I am surprised. I have two questions

  1. Why does this patch affect categories/rings.py?

It's just a doctest and it's because I swapped the order when iterating over the objects (i.e., it became index, coefficient whereas before it was coefficient, index).

  1. Can you be more specific with Exception? In which case did you run into the Exception? AttributeError? Can you include it in a doctest?

There's a doctest in categories/commutative_ring_ideals.py which tries to pass off (incorrectly) Partitions(4) as a commutative ring, but the is_Algebra fails with a TypeError. However, it could also fail with other errors and I didn't want the is_Algebra to error out for similar reasoning to a __contains__() check. We can add additional doctests to is_Algebra but I think we're already covered by other parts of the library.

comment:18 Changed 8 years ago by tscrim

  • Work issues fix doctests deleted

comment:19 in reply to: ↑ 17 Changed 8 years ago by ppurka

  • Reviewers set to Punarbasu Purkayastha
  • Status changed from needs_review to positive_review

Ok. Then. Setting it to positive review.

comment:20 Changed 8 years ago by tscrim

Thank you for doing the review.

comment:21 Changed 8 years ago by vbraun

  • Status changed from positive_review to needs_work

Lots of doctests failures

comment:22 Changed 8 years ago by tscrim

Can you list which files?

comment:23 Changed 8 years ago by vbraun

Sorry, too late. But there was enough breakage that you should run the whole testsuite.

comment:24 Changed 8 years ago by tscrim

This is mostly for my records. Here's the list I got that were "bad" errors:

sage -t rings/quotient_ring.py  # 8 doctests failed
sage -t rings/ring.pyx  # 3 doctests failed
sage -t structure/sage_object.pyx  # 1 doctest failed
sage -t structure/factorization.py  # 1 doctest failed

The pickling one is going to be the most fun to deal with.

These were from dictionary orderings (likely from hash values):

sage -t libs/singular/groebner_strategy.pyx  # 2 doctests failed
sage -t rings/polynomial/plural.pyx  # 5 doctests failed
sage -t rings/polynomial/multi_polynomial_ideal.py  # 13 doctests failed

One I don't think is related:

sage -t doctest/test.py  # 1 doctest failed

These seem to be maxima related (i.e. local to my setup so I'm going to ignore them):

sage -t tests/french_book/integration_doctest.py  # 1 doctest failed
sage -t calculus/desolvers.py  # 8 doctests failed
sage -t /home/travis/sage/src/doc/en/prep/Quickstarts/Differential-Equations.rst  # 2 doctests failed
sage -t /home/travis/sage/src/doc/en/constructions/calculus.rst  # 4 doctests failed

comment:25 Changed 8 years ago by git

  • Commit changed from 74734db11fe788440775741de7519e9f2b7f7956 to 0f9bf9dbdd714429fd290f8c42811e143ca5d70e

Branch pushed to git repo; I updated commit sha1. New commits:

9899a9cFixing doctests in quotient_ring.py and ring.pyx.
073b577Fixed dict ordering doctests.
0f9bf9dFixed remaining doctests.

comment:26 Changed 8 years ago by tscrim

  • Status changed from needs_work to positive_review

Volker, double-check that I got them all please.

comment:27 Changed 8 years ago by vbraun

  • Branch changed from public/algebras/fix_free_algebras-14848 to 0f9bf9dbdd714429fd290f8c42811e143ca5d70e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.