Re: [sage-devel] Re: AlgebraicReal.minpoly slow

[Jonas Jermann]

Hi

Factoring first and then calculating the roots of the factors (you don't 
need the multiplicity of the factor) worked fast for me...


Side note:
In AA I noticed that most operations become much faster after a 
num.simplify(). But in this case the simplify operation is slow itself...


Best
Jonas

On 20.09.2016 14:22, Marc Mezzarobba wrote:

Clemens Heuberger wrote:

x = polygen(QQ)
equation = -96000*x^7 + 41600*x^6 - 6640*x^5 + 560*x^4
- 28*x^3 + 8400*x^2 - 140*x + 1 roots = equation.roots(QQbar)
a_root = roots[-1][0]
abs_root = abs(a_root)

[...]

Is this expected behaviour?


Well, QQbar has a number of well-known but not yet fixed efficiency
problems...


I am intersted in the smallest root(s) in
absolute value only, any suggestions for achieving that in less time?


You could perhaps compute a polynomial whose roots include the z·conj(z)
for all roots z of equation (e.g., with a resultant), factor that
polynomial, and sort its root numerically while increasing the
precision until you can tell which of the factors correspond to
dominant roots. Or something like that :-/



--
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.

Re: [sage-devel] subs semantic

[Jonas Jermann]

Hi

+1 by me.
How is the order of variables for "call" determined?
How would this work for SR?


Regards
Jonas

On 06.12.2015 15:24, Vincent Delecroix wrote:

Hello,

We have substitution available for various objects (e.g. matrices when
the base ring is a polynomial ring). I would like to fix the conventions
of the parent of

  my_object.subs(var1=val1, var2=val2)

versus

  my_object(var1=val1, var2=val2)

With .subs, univariate polynomial ring somehow chooses the "minimal ring"

 sage: R. = ZZ[]
 sage: (x+3).subs(x=2).parent()
 Integer Ring
 sage: (x+3).subs(x=x+4).parent()
 Univariate Polynomial Ring in x over Integer Ring
 sage: (x+3).subs(x=4.).parent()
 Real Field with 53 bits of precision

Whereas multivariate are somehow "undecided"

 sage: (x+3).subs(x=2).parent()
 Multivariate Polynomial Ring in x, y over Integer Ring
 sage: (x+3).subs(x=x+4).parent()
 Multivariate Polynomial Ring in x, y over Integer Ring
 sage: (x+3).subs(x=4.).parent()
 Real Field with 53 bits of precision

Whereas the symbolic ring is as always a black hole

 sage: x = SR('x')
 sage: x.subs(x=3.).parent()
 Symbolic Ring
 sage: x(x=3.).parent()
 Symbolic Ring

My proposition is:

  - .subs should be considered as an *internal* operation. Hence, the
result will always be in the same parent (or the result of a pushout).
In particular we would have

 sage: R. = ZZ[]
 sage: x.subs(x=4).parent()
 Univariate Polynomial Ring in x over Integer Ring
 sage: x.subs(x=4.).parent()
 Univariate Polynomial Ring in x over Real Double Field

- __call__ is considered as an external operation. The result should
(more or less) be the smallest parent in which the result belong.

 sage: R. = ZZ[]
 sage: x(3,5).parent()
 Integer Ring
 sage: (x+y)(3., polygen(ZZ))
 Univariate Polynomial Ring in x over Real Field with 53 bits of
precision

Does it look reasonable?

Best,
Vincent



--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Do we really need Element, RingElement, AdditiveGroupElement, ...?

[Jonas Jermann]

What if it is inconvenient to define multiplication in terms of the 
basis (e.g. what if we don't want to work with a basis unless it is 
really necessary)?


What if we have infinite dimensional spaces but multiplication can
still be defined (without using a basis)?

Best
Jonas

On 28.11.2015 20:49, Travis Scrimshaw wrote:


 > Or what is the "modern" approach/solution for this?

It is possible to do everything based on
sage.combinat.free_module.CombinatorialFreeModule. It is a clean
mathematical approach (for defining something like a multiplication on
a module, it is enough to define what happens on a basis). But it is
pure python code and it uses an amazing amount of indirections. So, I
would recommend against using it for time-critical applications. And
that's part of the motivation for the two tickets that I mentioned
before:
I want to make it possible to define a multiplication action in some
Cython file, and let the categoy framework (written in Python) put the
appropriate fast Cython methods into the parent's action cache.

A lot of the functionality has also been abstracted up to the category
ModulesWithBasis. However, I agree that there are a large number of
indirections that we might want to simplify, and CombinatorialFreeModule
would likely benefit from more cythonization (and common abstraction
with sparse free modules).

Best,
Travis

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Do we really need Element, RingElement, AdditiveGroupElement, ...?

[Jonas Jermann]

Hi

In one case I was forced to use CommutativeAlgebraElement because I
needed it's operations (e.g. __mul__) even though the category/class
from the parent (module) doesn't support it:

It sometimes makes sense to view (homogeneous) elements of a graded
ring as module elements (because operations might be specific to that 
module and not to the whole ring).


On the other hand we still want to be able to multiply those *module* 
elements of possibly different homogeneous parts.


So if we inherit from CommutativeAlgebraElement we get the __mul__
operation but we can still treat elements as module elements...

Or what is the "modern" approach/solution for this?
I found my own way of working with graded rings in sage but I also
noticed that the framework doesn't solve all problems and tricks
have to be used...


Best
Jonas

On 27.11.2015 13:59, Simon King wrote:

Hi Jeroen,

On 2015-11-26, Jeroen Demeyer  wrote:

On 2015-11-23, Travis Scrimshaw  wrote:

However, I'm +1 for flatting things down to Element as it would probably
solve #15160  and #15947
.


See #18756 or #18758. I think these would solve it eventually.


I don't really see how those tickets are related to getting rid of
classes like RingElement.


Perhaps I recall wrongly what I did in these tickets. Anyway, what I
recall is this:
- Implement the generic coercion framework in Element rather than in
   RingElement.
- Make it possible to implement an action via parent methods of a
   category.
- Preserve RingElement and friends for backwards compatibility and for
   applications for which few nanoseconds slowdown in multiplication
   matter.

Best regards,
Simon



--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Review of tickets #17909, #17943, #18043

[Jonas Jermann]

Hi again

Ping: Can someone review #17909 (and/or #17943)?
#18043 was reviewed and applied/closed (thanks Travis).


Best
Jonas

On 02.11.2015 15:40, Jonas Jermann wrote:

Hi all

I already sent this to sage-nt but didn't get a response, so I try
again: Can someone maybe have a look at one of the tickets above
(in particular  #17909)?

They are for modular forms for Hecke triangle groups.
In particular this includes (classical) modular forms for SL2(Z)
and for the Theta subgroup (see the readme for more information).

I no longer work in academics (I'm a software developer now)
but the code might be useful for others (e.g. in the classical cases)
and in my opinion it would be a pity if the functionality got lost in
the ticket graveyard...

I didn't expect a fast review but the tickets are there since
quite a while already... :-)

#17909: Rankin Cohen brackets (also for quasi forms) and more
 decomposition methods for quasi forms

#17943: Depends on #17909 (but I could make it separate I guess).
 Here I tried to make some experimental code (conversions
 from numerical coefficients to exact forms) more robust
 and fixed some bugs

#18043: I tried my best to add support for HyperbolicPlane(), it could
 certainly be improved by someone familiar with the
 HyperbolicPlane code...

So if someone has time or is interested, it's appreciated. :-)


Best
Jonas



PS
I would be interested in generalizing the implementation to Jacobi
forms if someone has the time to help me with the algebraic structure.

PPS
Using appropriate subspaces it's quite easy to find some differential
equations satisfied by the forms (e.g. E2). For instance I found:
n=4
E2.derivative(4) == -3/2*E2^2*E2.derivative(2) + 5/2*E2*E2.derivative(3)
+ 9/4*E2*E2.derivative()^2 -3*E2.derivative()*E2.derivative(2)
n=5 (non-arithmetic)
E2^3*E2.derivative(2) == E2^2*E2.derivative(3) + 3/2 *
E2^2*E2.derivative()^2 + 4*E2*E2.derivative()*E2.derivative(2) -20/3 *
E2.derivative()*E2.derivative(3) -22/3*E2.derivative()^3 +
40/9*E2.derivative(2)^2
Maybe that's of interest to someone...


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] [sage-nt] Review of tickets #17909, #17943, #18043

[Jonas Jermann]

Hi all

I already sent this to sage-nt but didn't get a response, so I try 
again: Can someone maybe have a look at one of the tickets above

(in particular  #17909)?

They are for modular forms for Hecke triangle groups.
In particular this includes (classical) modular forms for SL2(Z)
and for the Theta subgroup (see the readme for more information).

I no longer work in academics (I'm a software developer now)
but the code might be useful for others (e.g. in the classical cases) 
and in my opinion it would be a pity if the functionality got lost in

the ticket graveyard...

I didn't expect a fast review but the tickets are there since
quite a while already... :-)

#17909: Rankin Cohen brackets (also for quasi forms) and more
decomposition methods for quasi forms

#17943: Depends on #17909 (but I could make it separate I guess).
Here I tried to make some experimental code (conversions
from numerical coefficients to exact forms) more robust
and fixed some bugs

#18043: I tried my best to add support for HyperbolicPlane(), it could
certainly be improved by someone familiar with the
HyperbolicPlane code...

So if someone has time or is interested, it's appreciated. :-)


Best
Jonas



PS
I would be interested in generalizing the implementation to Jacobi
forms if someone has the time to help me with the algebraic structure.

PPS
Using appropriate subspaces it's quite easy to find some differential 
equations satisfied by the forms (e.g. E2). For instance I found:

n=4
E2.derivative(4) == -3/2*E2^2*E2.derivative(2) + 5/2*E2*E2.derivative(3) 
+ 9/4*E2*E2.derivative()^2 -3*E2.derivative()*E2.derivative(2)

n=5 (non-arithmetic)
E2^3*E2.derivative(2) == E2^2*E2.derivative(3) + 3/2 * 
E2^2*E2.derivative()^2 + 4*E2*E2.derivative()*E2.derivative(2) -20/3 * 
E2.derivative()*E2.derivative(3) -22/3*E2.derivative()^3 + 
40/9*E2.derivative(2)^2

Maybe that's of interest to someone...

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Algebraic numbers: the '?' could be more informative (e.g.: 1.4142?)

[Jonas Jermann]

On 13.07.2015 19:33, Nathann Cohen wrote:

I agree with Simon, although finding a nice expression like sqrt(2)+3^(1/3)
can be very costly deppending on how the algebraic number was constructed.


Yepyep. As Simon said we cannot always express algebraic numbers in
such a nice way, though. Well, if you want to build such an object
*in Sage* then you must describe your value somehow, and it is also
stored internally somewhere.. And I wonder how, and whether we can
base the representation on this internal version of the value :-)


Anyways we could have such an expression for the cases where it is evident
from the number construction.


-1

I definitely prefer a uniform output.
If you want a symbolic representation then convert the element to
one from SR (symbolic ring). This is basically what you are asking with
where it is evident anyway...

Of course you could add a function which tries to do exactly that
but in my opinion the default output should have a uniform look
for a given parent. That way you also realize (better) over what
parent you are working with currently.

Sidenote: Another useful representation is the minimal polynomial + 
exact bounds (maybe interval field element?) for a root location.


I implemented a proof of concept of such a field once where all elements
were displayed as their minimal polynomial + bounds for the root 
location. Arithmetic operations like addition or multiplication can
be defined for the root polynomial. What is harder are the root location 
bounds (+ irreducible parts of the polynomial) which have to

be recalculated I suppose.


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: polynomial ring (bis)

[Jonas Jermann]

Hi

Just a side question:

What if there are infinitely/arbitrary many variables and the need to
print/reference/etc them (fetch the next) appropriately?
A PhD colleague of mine had this issue (iirc with Power-series rings)...


Regards
Jonas

On 10.05.2015 01:54, Nils Bruin wrote:

On Saturday, May 9, 2015 at 10:50:08 AM UTC-7, vdelecroix wrote:

Hi Nils,

Should I count your e-mail as a -1 for allowing

 PolynomialRing(QQ, (2,3), 'a')
 FreeAlgebra(QQ, (2,3), 'a')

and that I should instead document

 PolynomialRing(QQ, variable_names((2,3), 'a'))
 FreeAlgebra(QQ, variable_names((2,3), 'a'))


Yes. Mathematically, the only thing important for defining a polynomial
ring is the dimension (the number of variables). In sage we need
variable names in addition, and given a list of variables, it's easy to
recover the dimension (from the number of variables specified).

By the time we specify the dimension as (2,3) I think we're getting
into the non-obvious territory. You mean 2*3, but 2+3 (as a 3-variable
ring over a 2-variable one, for instance) would be equally plausible. Or
it could be a graded polynomial ring in 2 variables with weights 2,3
respectively.

The problem you're trying to address is generating variable names
according to some pattern. The most direct solution for that is to
generate the list of variable names. That already works and works well
(using the standard string construction tools in python). Given the
problems for dimension specification by anything else than a simple
integer, I think we should just rely on the direct solution.

--
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
mailto:sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com
mailto:sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: help with conventions for python properties and __init__ question

[Jonas Jermann]

Hi Martin

What about something like this:

class A(SageObject):
def __new__(cls, a, b=None, c=None):
if isinstance(a, A):
print just use a
return a
else:
print create new instance
return super(A, cls).__new__(cls, a, b, c)

def __init__(self, a, b=None, c=None):
if isinstance(a, A):
print no init required
return
print init

Regards
Jonas

On 29.03.2015 18:35, 'Martin R' via sage-devel wrote:

Since the above appears to be a very difficult question (:-), I'm going
to add another one - which is actually mentioned in the thread title,
but I somehow forgot to ask...

Suppose I have a class A with an __init__ method taking a single
mandatory argument:

class A(SageObject):

 def __init__(self, a, b=None, c=None):

What I'd like to achieve is that A(a) yields a, if a is an instance of
A.  I have read a bit about unique representation and
CachedRepresentation, etc., but what I really want to achieve here is, I
hope, much simpler.

I don't want to use CachedRepresentation, since the arguments of
__init__ would be expensive to cache.

Many thanks,

Martin

--
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
mailto:sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com
mailto:sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] 'git trac' instructions for rebasing/merging

[Jonas Jermann]

Hi

On 12.03.2015 08:28, Nathann Cohen wrote:

Hello everybody,

I just noticed that we do not seem to have in our developer's manual
instructions about how to rebase/merge a branch when it becomes
incompatible with the latest beta.

I do not use 'git trac' myself, but it would be cool if anybody who
does could add such an entry in the developer's manual: this is
something that we are bound to explain individually many many times
otherwise.

In the meantime I will try to make the 'git the hard way' version of
it a bit easier to follow.


Just an idea:

What about suggesting to use git rebase instead of git merge
(at least at the end)?

At the moment the git history of sage looks quite messy
and I assume it will get worse, not better.

Having a git rebase before inclusion policy (or at least a suggestion)
would help.


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Review 17261

[Jonas Jermann]

Hi

Can someone review the following (small) ticket:
http://trac.sagemath.org/ticket/17261

It's an enhancement for modular forms for hecke triangle groups.
It adds support for coercions from form spaces/rings over the full
modular group to form spaces/rings over the Theta subgroup.


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Addition of zero in the coercion model

[Jonas Jermann]

Hi

In my case there is a cm.coercion_map(parent(myElement), parent(0))
(line 907) namely the coercions into the modular forms ring.
These maps are then used to map both myElement and 0 to the modular 
forms ring (in contrast to the (vector) space myElement.parent()).


Unfortunately the check for the special case 0 comes after this,
not before. :-(


Regards
Jonas

On 22.02.2015 16:39, Simon King wrote:

Hi Eric,

On 2015-02-22, Eric Gourgoulhon egourgoul...@gmail.com wrote:

Note that the function is_Integer used in sage.structure.coerce.pyx is=20
*not* the above one: it is defined in lines 134-139 and it returns True for=
is_Integer(int(0)).=20


Seriously? But when the integer zero is treated in a special way, then why
did sum(...) not work in the original post, while sum(..., P.zero())
did?

Best regards,
Simon



--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Addition of zero in the coercion model

[Jonas Jermann]

Hi

It's a good idea but it won't work (in fact the _element_constructor_ 
does accept zero correctly in my case). The coercion framework _first_

tries to find a common parent and _then_ the rest happens.

Best
Jonas

On 21.02.2015 22:59, Eric Gourgoulhon wrote:

Hi,

Le samedi 21 février 2015 21:59:05 UTC+1, Jonas Jermann a écrit :


The parent is a vector space / module not a ring. Every vector space
contains zero, so in my opinion from a conceptual point of view
adding zero should not change the parent space.

However since it views 0 as an integer and not as (an element) the zero
subspace (unless we forcefully map it there) it seems hard to change
this behavior. :-(


It seems that a possible way to have 0 + MyElement work even if ZZ does
not coerce to MyElement.parent() is to have
MyElement.parent()._element_constructor_ accept 0 (i.e. Integer(0)) as
an argument and return the zero element of your vector space / module
for such an argument.  Am I correct?

Eric.

--
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
mailto:sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com
mailto:sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Addition of zero in the coercion model

[Jonas Jermann]

Hi

In my case 0 + MyElement does find a common parent,
namely the modular forms _ring_.

So basically in my case 0 + some_element is the same
as some_element.as_ring_element(), unless the weight of
some_element (resp. its parent) is 0 with multiplier 1
in which case ZZ coerces into the space.

In any case, it's ok. I can work around these issues.


Best
Jonas

On 21.02.2015 23:44, Eric Gourgoulhon wrote:



Le samedi 21 février 2015 23:09:24 UTC+1, Jonas Jermann a écrit :

Hi

It's a good idea but it won't work (in fact the _element_constructor_
does accept zero correctly in my case). The coercion framework _first_
tries to find a common parent and _then_ the rest happens.


At least in the cases I've tried (free modules as implemented in
#15916), if no common parent is found, there is then a conversion of 0
via _element_constructor_, followed by the addition via the _add_
(single underscore) of the module elements.
Do I understand correctly that 0 + whatever first calls
sage.structure.element.RingElement.__add__, which starts by
   if have_same_parent(left, right):
(line 1570 of sage/structure/element.pyx);  if this fails, it performs
   return coercion_model.bin_op(left, right, add)
(line 1579)
and the latter shall invoke your parent._element_constructor_ to convert
0 to your zero element. I am not completely sure about this... (this is
my understanding why it works in my case).

Eric.


Best
  Jonas

On 21.02.2015 22:59, Eric Gourgoulhon wrote:
  Hi,
 
  Le samedi 21 février 2015 21:59:05 UTC+1, Jonas Jermann a écrit :
 
 
  The parent is a vector space / module not a ring. Every
vector space
  contains zero, so in my opinion from a conceptual point of view
  adding zero should not change the parent space.
 
  However since it views 0 as an integer and not as (an
element) the zero
  subspace (unless we forcefully map it there) it seems hard to
change
  this behavior. :-(
 
 
  It seems that a possible way to have 0 + MyElement work even if
ZZ does
  not coerce to MyElement.parent() is to have
  MyElement.parent()._element_constructor_ accept 0 (i.e.
Integer(0)) as
  an argument and return the zero element of your vector space /
module
  for such an argument.  Am I correct?
 
  Eric.
 

--
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
mailto:sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com
mailto:sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Addition of zero in the coercion model

[Jonas Jermann]

Hi Simon

On 21.02.2015 21:47, Simon King wrote:

Hi Jonas,

On 2015-02-21, Jonas Jermann jjerma...@gmail.com wrote:

ZZ does not coerce into myElement.parent() so I end up in a much
larger space than myElement.parent(). However I would prefer if adding
zero didn't change the parent space.


If ZZ does not coerce into the parent of your element, then the parent
is not a (unitary) ring.


The parent is a vector space / module not a ring. Every vector space 
contains zero, so in my opinion from a conceptual point of view

adding zero should not change the parent space.

However since it views 0 as an integer and not as (an element) the zero 
subspace (unless we forcefully map it there) it seems hard to change

this behavior. :-(


One reason is for instance that
sum(...) no longer works properly because it always prepends 0+.


You can avoid it by explicitly providing the starting element to the sum
function.


Eg: from sage.modular.modform_hecketriangle.all import *
  myElement = ModularForms().E4()
  myElement.parent() != sum([myElement]).parent()

Clearly 0 is a special case (the zero subspace does coerce into any of
the spaces).

How should I fix this?


By providing a starting point for the summation:
   sage: sum([myElement]).parent()
   ModularFormsRing(n=3) over Integer Ring
   sage: myElement.parent()
   ModularForms(n=3, k=4, ep=1) over Integer Ring
   sage: sum([myElement], myElement.parent().zero()).parent()
   ModularForms(n=3, k=4, ep=1) over Integer Ring


Thanks. Yes, I was aware of this, for instance I could also use
python's reduce function or a for loop. I was hoping to fix the issue
in a proper way, namely to get adding zero to work. Always having to
work around sum is annoying. What if sum is called outside of my
control in some other function? The issue can also be a hidden source 
for bugs.



Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Addition of zero in the coercion model

[Jonas Jermann]

Hi

On 21.02.2015 21:57, Simon King wrote:

On 2015-02-21, Simon King simon.k...@uni-jena.de wrote:

If ZZ does not coerce into the parent of your element, then the parent
is not a (unitary) ring.


PS:
And if it is not a ring, then many things don't work as smoothly as they
should.

For example, if P is a commutative additive group with an element x, then most
people would expect that x+0 should be equal to x. Reason: The ADDITIVE
group of ZZ coerces into P.


I'm confused. Why does the additive group of ZZ coerce into P?


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Addition of zero in the coercion model

[Jonas Jermann]

Hi

On 21.02.2015 22:13, Nils Bruin wrote:

On Saturday, February 21, 2015 at 12:57:44 PM UTC-8, Simon King wrote:


I.e., if P is a commutative additive group, then P.coerce_map_from(ZZ)
should return a morphism in the category of commutative additive
groups.
Then, x+0 should work (because the coercion map is a morphism in the
category of additive groups), but x*0 should not work (because it is
not
a morphism of multiplicative groups).


I'm not so sure. How does x+3 make unambiguous sense? We can map ZZ onto
any cyclic subgroup. There is not necessarily a unique maximal one (for
x+0 it obviously doesn't matter which one we choose, though)


x+3 makes no sense. I was trying to argue that x+0 makes sense. But
I guess it works against the way the coercion model is set up. So I will
just have to deal with +0 and sum() issues I guess.

Thanks to both of you and Simon for the clarifications.
So I will consider the issue closed/answered.


Best
Jonas

P.S. in sage.modular.modform_hecketriangle I implemented both, the ring
of modular forms and the vector spaces (homogeneous parts of the graded 
ring). Note in particular that I implemented it in such a way that

multiplication of module elements give again module elements (in a
different space). Check it ouf if you're interested.

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Addition of zero in the coercion model

[Jonas Jermann]

Hi

When I do 0 + myElement the coercion framework seems to map this
to a common parent of 0 and myElement (by checking the parent of 0 and
myElement).

ZZ does not coerce into myElement.parent() so I end up in a much
larger space than myElement.parent(). However I would prefer if adding
zero didn't change the parent space. One reason is for instance that
sum(...) no longer works properly because it always prepends 0+.

Eg: from sage.modular.modform_hecketriangle.all import *
myElement = ModularForms().E4()
myElement.parent() != sum([myElement]).parent()

Clearly 0 is a special case (the zero subspace does coerce into any of 
the spaces).


How should I fix this?


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] coercion issue

[Jonas Jermann]

Hi

Set x=GF(5)['x'].gen()
I dunno if this helps but here is an explanation why one gets a
different behavior for x/7 than cm.bin_op(x,7,operator.div):

If you do x/7 then I think it calls __div__ from polynomial_element 
(Polynomial class):


try:
  if not isinstance(right, Element) or right.parent() != self.parent():
R = self.parent().base_ring()
x = R._coerce_(right)
return self * ~x
except (TypeError, ValueError):
  pass
return RingElement.__div__(self, right)

Here right=ZZ(7), self=x, so right.parent() != self.parent()
so it does x = GF(5)._coerce_(7)
which is why you end up without the Fraction Field...

If on the other hand you do cm.bin_op(x,7,operator.div) or x._div_(7) 
you get a Fraction Field element at the moment.



Best
Jonas

On 05.02.2015 22:08, Vincent Delecroix wrote:

2015-02-05 21:38 UTC+01:00, John Cremona john.crem...@gmail.com:

If you ask for operator.mul instead of operator.div then you get the
poly ring.  Is that it, perhaps?


Nope. I want to get rid of many hacks in rings/polynomial. In order to
do that I need the div operation to be correctly handled by the
coercion (or perhaps I missed something about the aim of coercion?).
Namely, if p is an element of GF(5)['x,y'] then (p/Integer(2)) should
be an element of GF(5)['x,y']. You can argue that this is what you get
in Sage

sage: R = GF(5)['x','y']
sage: (R.an_element() / 2).parent()
Multivariate Polynomial Ring in x, y over Finite Field of size 5

But the reason why is a bit of a hack that actually introduce many
bugs in other places:

sage: R = GF(5)['x,y']
sage: (R.one() / R.one()).parent()
Multivariate Polynomial Ring in x, y over Finite Field of size 5

the above should be an element of the fraction field! And you can
build more involved examples.

Vincent



--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] .one() vs .one_element()

[Jonas Jermann]

Hi

Just for your information:

When I implemented modular forms spaces (with module elements that
still have a multiplication/etc defined) I had to add both methods.
one() to allow to take the power 0 of an element
and one_element() to allow to take negative powers of elements.

I hope everything will still work after the modifications
(coercions can can become complicated, especially in the situation
described above where module elements are multiplied/etc).


Best
Jonas

On 30.01.2015 10:31, Vincent Delecroix wrote:

Hello,

It seems to me that we have aliases .one() and .one_element() on some
parents (idem with zero). Do we have a policy concerning:
  - which one should be as an alias of the other?
  - should we deprecate one of the usage? I remember that I already
discussed with Nicolas the fact that one_element might be confusing
because we also have an_element.

Concerning the situation in Sage:

The file sage/ring/ring.pyx defines .one_element(). It calls self(1)
and then caches the result in the attribute self._one_element. Idem
for zero_element in the attribute ._zero_element. Both attributes are
Cython attributes. Note that one() and .zero() are defined as aliases
in ring.pyx

Inside sage/categories/ I count 4 calls to .one_element() against 100
calls to .one(). Also magmas implements a cached .one() method and
monoids has a one_element() where it is explicitely written in the
documentation backward compatibility.

I propose to start the big cleaning by making zero/one the default in
rings/ring.pyx and add a deprecation to zero_element/one_element. Is
there any obstruction?

Vincent



--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] .one() vs .one_element()

[Jonas Jermann]

Hi Vincent,

Ok, I checked (with abstract space elements) and
everything seems to work fine! :-)

+1


Best
Jonas

On 30.01.2015 20:15, Vincent Delecroix wrote:

Hi Jonas,

All test pass within my branch. So at least nothing broken which is
doctested. If you are worried about more, you should test it with my
branch applied.

Note that the three files that are of your concern are modified

modular/modform_hecketriangle/abstract_ring.py  
modular/modform_hecketriangle/abstract_space.py
src/sage/modular/modform_hecketriangle/hecke_triangle_groups.py

Vincent

2015-01-30 19:51 UTC+01:00, Jonas Jermann jjerma...@gmail.com:

Hi

Just for your information:

When I implemented modular forms spaces (with module elements that
still have a multiplication/etc defined) I had to add both methods.
one() to allow to take the power 0 of an element
and one_element() to allow to take negative powers of elements.

I hope everything will still work after the modifications
(coercions can can become complicated, especially in the situation
described above where module elements are multiplied/etc).


Best
  Jonas

On 30.01.2015 10:31, Vincent Delecroix wrote:

Hello,

It seems to me that we have aliases .one() and .one_element() on some
parents (idem with zero). Do we have a policy concerning:
   - which one should be as an alias of the other?
   - should we deprecate one of the usage? I remember that I already
discussed with Nicolas the fact that one_element might be confusing
because we also have an_element.

Concerning the situation in Sage:

The file sage/ring/ring.pyx defines .one_element(). It calls self(1)
and then caches the result in the attribute self._one_element. Idem
for zero_element in the attribute ._zero_element. Both attributes are
Cython attributes. Note that one() and .zero() are defined as aliases
in ring.pyx

Inside sage/categories/ I count 4 calls to .one_element() against 100
calls to .one(). Also magmas implements a cached .one() method and
monoids has a one_element() where it is explicitely written in the
documentation backward compatibility.

I propose to start the big cleaning by making zero/one the default in
rings/ring.pyx and add a deprecation to zero_element/one_element. Is
there any obstruction?

Vincent



--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.





--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] help with QQbar conversion to complex number

[Jonas Jermann]

Hi

In particular: Try .simplify()!

In my case that produced an improvement factor 1000 in some cases.

Best
Jonas

On 24.11.2014 20:54, Ben Hutz wrote:

Thanks Vincent. I can give that a try. We did try to approximate earlier
with CC and the errors were compounding too much (we do a bunch more
stuff after this), but maybe approximating the roots with CIF will do a
better job.

It sounds like the recursion depth error is actually expected for
numbers like this,

(btw, type is defined in the example as 6, but it doesn't really matter)

On Monday, November 24, 2014 1:55:05 PM UTC-5, vdelecroix wrote:

Hi Ben,

You are dealing with complicated numbers, it is not surprising that
things like exactify or __cmp__ lead to maximum recursion errors.
If you want something faster than QQbar you can either:
  - do approximation earlier in the code
  - try to work with number fields

Note that your example can be simplified
{{{
z = polygen(ZZ)
f = z^2 + 3/4
g = f
for _ in range(5): g = f(g)
roots = (g-z).roots(QQbar, multiplicities=False)
}}}

Then instead of applying d I would suggest that you do the
approximation now
{{{
R = ComplexIntervalField(256)
approx_roots = [r.interval_exact(R) for r in roots]
}}}
and start your computation from there.

By the way, I was not able to go through your example since type is
not defined. I tried with type=7 and get quite accurate results (the
diameter was  10^-43).

Vincent

--
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
mailto:sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com
mailto:sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Should NaN be in RR?

[Jonas Jermann]

On 16.10.2014 23:09, Volker Braun wrote:

sage: RR('nan')
NaN

Its one of the possible elements of RR, but not ZZ.


sage: RR(NaN)*RR(infinity)
NaN
sage: RR(NaN)*infinity
-Infinity

Huh?


Regards
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Buildbot link on needs work tickets.

[Jonas Jermann]

Hi

On 04.10.2014 11:18, Ralf Stephan wrote:

On Saturday, October 4, 2014 12:09:19 AM UTC+2, Jonas Jermann wrote:

--
sage -t src/sage/crypto/mq/sr.py  # 5 doctests failed
sage -t src/sage/modular/modform/numerical.py  # 2 doctests failed
sage -t src/sage/rings/polynomial/multi_polynomial_sequence.py  # 9
doctests failed
sage -t src/sage/rings/polynomial/pbori.pyx  # Killed due to
segmentation fault
sage -t src/sage/rings/polynomial/polynomial_element.pyx  # 2 doctests
failed
sage -t src/sage/rings/real_double.pyx  # 2 doctests failed
--


Same with http://trac.sagemath.org/ticket/12455 so this
appears buildbot related. Many of recent buildbot failures
show these tests failing, although the pattern seems unclear:
http://build.sagedev.org/trac/one_line_per_build


It seems to be related to the (now closed) ticket #17071 resp. #17072:
http://trac.sagemath.org/ticket/17071


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Buildbot link on needs work tickets.

[Jonas Jermann]

Hi

Regarding (the) buildbot(s), for the ticket #16936 it says Failure
even though it builds fine for me and the doctests work fine.

shell_13 doctested failed:

--
sage -t src/sage/crypto/mq/sr.py  # 5 doctests failed
sage -t src/sage/modular/modform/numerical.py  # 2 doctests failed
sage -t src/sage/rings/polynomial/multi_polynomial_sequence.py  # 9 
doctests failed
sage -t src/sage/rings/polynomial/pbori.pyx  # Killed due to 
segmentation fault
sage -t src/sage/rings/polynomial/polynomial_element.pyx  # 2 doctests 
failed

sage -t src/sage/rings/real_double.pyx  # 2 doctests failed
--

Those are all unrelated to my ticket. It seems some bots do doctests
and some don't. In any case how do I fix my Failure status?


Best
Jonas

On 03.10.2014 17:12, Nils Bruin wrote:

Dear buildboteers,

The new buildbot interface is wonderful. However, on #17065 we ran into
an issue that needs work tickets do not display the buildbot link.
That's inconvenient in the following scenario:
  1. Author gets a ticket to a reasonable state and sets ticket to
needs review
  2. Buildbot finds errors, so Reviewer sets ticket back to needs work
  3. Buildbot log is now not easily accessible from ticket anymore, so
Author cannot see the failures any more.
The workaround is simple: don't set tickets back to needs work, but I
think the needs review/needs work status distinction is useful (it
signals to Author that Reviewer has looked at it, for one thing). Would
it be possible to somehow fix this?

Also, the cute coloured blob thing in the upper right that used to
indicate build status seems to not work any more. If it doesn't get
fixed it might be better to remove

--
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
mailto:sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com
mailto:sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] sign() and comparison in AA

[Jonas Jermann]

Hi

How can I do exact comparison of numbers in AA?
I noticed that this doesn't work very reliably:

el1 = AA((x^4 - 2238072*x^2 + 44133904).roots()[1][0])
el2 = (791264*AA(2*cos(pi/8))^2 - 463492).sqrt()
el1 == el2

^- This fails for me (resp. never stops)
[el1-el2 gives 0.?e-15]


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] sign() and comparison in AA

[Jonas Jermann]

Hi

I use AA(2*cos(pi/n)) for the default embedding in the corresponding
(totally real) NumberField (of which I later take a relative (real) 
quadratic extension for which I also try to find the correct

embedding). - Ticket #16936, #16976.

I choose AA as my default embedding field because it coerces nicely
into many fields (in particular into AA).

I do comparisons/signs in many places (e.g. for continued fraction
calculations). The sign should ideally be exact (-1, 0, 1).

The problem with comparison/signs is reoccuring and prevents / slows
down many calculations. :(

What would you suggest I do to get a fast exact sign/comparison?


Best
Jonas

On 17.09.2014 16:52, John Cremona wrote:

You are doing the right thing, but AA (and QQbar) are very slow at
testing equality -- and hence also at division since the denominator
must be tested for equality with 0.

In this case since el1.minpoly() and el2.minpoly() are the same, and
the roots in RR are very different:

sage: el1.minpoly()
x^4 - 2238072*x^2 + 44133904
sage: el2.minpoly()
x^4 - 2238072*x^2 + 44133904
sage: el2.minpoly().roots(RR)
[(-1496.01212569203, 1),
  (-4.44069616336440, 1),
  (4.44069616336440, 1),
  (1496.01212569203, 1)]

it is hard to believe that there is not a quicker way of doing the
test.  (It is also relevant that
sage: el1.minpoly().is_irreducible()
True

here, since in general during a computation in AA/QQbar, the
polynomials carried around are not factored.  i think.)  Also note
that

sage: el1.minpoly()(el2) ==0
True
!

John


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: sign() and comparison in AA

[Jonas Jermann]

Hi

On 17.09.2014 17:29, Marc Mezzarobba wrote:

Jonas Jermann wrote:

What would you suggest I do to get a fast exact sign/comparison?


Just a wild guess, but you may want to see if the patch at

http://trac.sagemath.org/ticket/15600

helps.


It doesn't (also note that the polynomials here have deg=4  8).

To me it seems that it might make sense to first make a exact + fast
equality check and treat that case very different (where and how
is unclear to me).

If not, we can work under the assumption that it isn't (and
probably/maybe use that to speed up calculations).

E.g. if the element is not 0 we could use a non-exact
approximation (RIF?) and keep increasing the precision/etc until we
are sure that the element is positive/negative.


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: sign() and comparison in AA

[Jonas Jermann]

Hi again

After a closer look it seems that almost all time is spent
in the calculation of el2._exact_field().pari_field()
which occurs in
  gen = left._exact_field().union(right._exact_field())
from line 7851 of qqbar.py.

One suggestion for a maybe faster algorithm to check equality:

1. Check if the minimal polynomials agree
2. Find non-overlapping intervals for the roots
3. Figure out the intervals of the corresponding two roots
   and compare.


Maybe a better alternative is to reduce the exact field:

At an appropriate place (e.g. immediately)
replace element._exact_field with the field given by
the minpoly of element.


3rd: Try to figure out why pari_field() is so slow...


Best
Jonas

On 17.09.2014 17:29, Marc Mezzarobba wrote:

Jonas Jermann wrote:

What would you suggest I do to get a fast exact sign/comparison?


Just a wild guess, but you may want to see if the patch at

http://trac.sagemath.org/ticket/15600

helps.



--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: sign() and comparison in AA

[Jonas Jermann]

On 17.09.2014 19:02, Jonas Jermann wrote:

Hi again

After a closer look it seems that almost all time is spent
in the calculation of el2._exact_field().pari_field()
which occurs in
   gen = left._exact_field().union(right._exact_field())
from line 7851 of qqbar.py.

One suggestion for a maybe faster algorithm to check equality:

1. Check if the minimal polynomials agree
2. Find non-overlapping intervals for the roots
3. Figure out the intervals of the corresponding two roots
and compare.


Maybe a better alternative is to reduce the exact field:

At an appropriate place (e.g. immediately)
replace element._exact_field with the field given by
the minpoly of element.


In short: Why not simplify elements before doing
non-trivial binary operations?

It might slow down some calculations but it would probably
speed up others by a factor like 10'000(?) since it will
probably avoid the strange pari_field() slowness..


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: sign() and comparison in AA

[Jonas Jermann]

Hi Erik

[sorry, the first mail was sent to you directly]

On 17.09.2014 19:21, Erik Massop wrote:
 On Wed, 17 Sep 2014 17:59:49 +0200
 It doesn't (also note that the polynomials here have deg=4  8).

 the polynomials?

sage: el2 = (791264*AA(2*cos(pi/8))^2 - 463492).sqrt()
sage: el2._exact_value()
[ something horrible involving a polynomial of degree 16 ]

Right.

 This is pretty fast though:
sage: x = var('x')
sage: el1 = AA((x^4 - 2238072*x^2 + 44133904).roots()[1][0])
sage: el3 = (791264*AA(2*cos(pi/8))^2 - 463492)
sage: el1  0
True
sage: el3  0
True
sage: el1^2 == el3
True
 Perhaps there is a way around the sqrt in your algorithm?

Note really but see below + my other mail.

 Actually this is interesting:
sage: el3 = (791264*AA(2*cos(pi/8))^2 - 463492)
sage: el2 = el3.sqrt()
sage: el2._descr
Root 1496.012125692029503? of x^2 - 2.238052280217585?e6
sage: el2.exactify()
sage: el2._descr
[ that horrible thing ]
 So in this case the old description would give a much more efficient
 comparison. Unfortunately, it's discarded...

The description looks nice but internally the exact field beeing
used is still the one with the polynomial of degree 16.

The problem occurs during the binary operation (sub).
Sage tries to find a common parent for that operation which
calls union for the exact_fields, which in turn calls pari_field()
which for el2 takes forever and produces a horrible^2
(actually worse than ^2) result. If el2 is simplified first
all (performance) issues are solved:

sage: el1 = AA((x^4 - 2238072*x^2 + 44133904).roots()[1][0])
sage: el2 = (791264*AA(2*cos(pi/8))^2 - 463492).sqrt()
sage: el2.simplify()
sage: el1 == el2

What about simplifying elements by default or for non-trivial
binary operations? It might slow down some calculations but
it would probably avoid the strange pari_field() calculations
(and speed up the calculation in this case by a huuuge factor).
Also in general it would probably speed up calculations of
complicated expressions in AA...


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: issues with pushout construction?

[Jonas Jermann]

Hi Robert

On 30.08.2014 07:48, Robert Bradshaw wrote:

I'm not sure (as mentioned the pushout construction is complex and
there are many cases). But yes, that might work:
Do a/several coercion check(s) _during_ pushout (during the while loop
starting at line 3210) if needed instead of only at the end.

So coercion_reversed=False (default) would mean that we assume that
the current base coerces into construction(base) and
coercion_reversed=False would mean that a coercion check should be
done.

If yes: Maybe something like force_coercion_check fits better?


That's an interesting suggestion.  I'll try thinking about it a bit more
to see if this is an improvement over coercion_reversed.


I think that coercion_reversed is the essential property here, as
dropping this construction is essentially applying the reverse
coercion, but checking for coercion allows one to see whether this
reverse coercion must be applied to find a common parent.


Ok, that explanation makes sense!

It still forces one to decompose functorial constructions
into coercion-compatible ones, meaning that there exists a coercion
from the base to functor(base), resp. coercion-reversed ones
(in the other direction).

Also: What if later functors rely on the result of the previous one?
If a coercion was reversed the next functor might fail...
So we will probably have one further assumption. Namely that
coercion reversed functors must appear only once and as the last
one (in any construction (tower) of a space).

Example:
Let CF = CuspForms, MF = ModularForms.
If CFRing(ZZ) = CFRingFunctor_coercion_reversed o MFRingFunctor (ZZ),
then pushout(RR, CFRing(ZZ)) would give MFRingFunctor(RR) (ok).

The above example might make sense, but what if you have
a whole bunch of spaces with complex relations (e.g. cuspidal,
holomorphic, weak, meromorphic, quasi/non-quasi, sub/non-sub).

I fear that in some situations it might be impossible/not practical
to find a simple construction mechanism. E.g. think about
pushout(QuasiCuspForms(ZZ), ModularForms(RR)).

See e.g. also sage.modular.modform_hecketriangle.functors.
I used a different approach by replacing the base ring
with BaseFacade(base ring) to distinguish the base ring
from other rings. There is only one FormsRingFunctor
with a parameter for the analytic type. The complexity is
moved to the merge function. The advantage is that (during
the pushout construction) the merge function has almost-complete
information of the situation and can decide accordingly.

In any case the suggested changes are still positive.


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] issues with pushout construction?

[Jonas Jermann]

Hi all

When I implemented Modular forms rings/spaces for Hecke triangle groups
I ran into some issues with pushout / functors / constructions
(correct me if I missunderstood something):

Apparently the pushout construction implicitely assumes that
there exists a coercion from the construction argument to the
construct:

There is supposed to be a coercion from A and B to C=pushout(A,B).
But if e.g. B is constructed from A without having a coercion from A
then the pushout will fail this (also see line 3217 of pushout.py).

So either one severely restricts (functorial) constructions to
coercion-compatible ones or the pushout construction fails
even though there might be a very obvious candidate for pushout(A,B).

Some examples that come to my mind:

- All kinds of projection / non-injective constructions

- A = some graded ring, B = some homogeneous component of A
  Adding elements of A and B should give an element of A

- A = some base ring, B = the ring of cusp forms over A
  Adding elements of A and B should give an element of
  the ring of modular forms over A, however if B is constructed
  by A, then the pushout construction will always return B
  to which A does not coerce.

I have found a solution for those issues with my implementation
(see sage.modular.modform_hecke_triangle.functors - BaseFacade)
but I consider it less elegant (put mildly). But it works!

I just mention this here because I felt like it might be something
worthy to discuss (unless I missunderstood something).


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: issues with pushout construction?

[Jonas Jermann]

Hi

On 27.08.2014 13:21, Simon King wrote:

Hi Jonas,

On 2014-08-27, Jonas Jermann jjerma...@gmail.com wrote:

There is supposed to be a coercion from A and B to C=pushout(A,B).
But if e.g. B is constructed from A without having a coercion from A
then the pushout will fail this (also see line 3217 of pushout.py).

So either one severely restricts (functorial) constructions to
coercion-compatible ones or the pushout construction fails
even though there might be a very obvious candidate for pushout(A,B).


Indeed, the pushout construction and the construction functors in
sage.categories.pushout are an important tool to find coercion candidates.
However, they are not supposed to be used for other categorial
pushout constructions.


I was talking/thinking about the implicit call of pushout when e.g.
adding two elements from different parents...


To avoid some misconceptions:


Some examples that come to my mind:

- All kinds of projection / non-injective constructions


It is not assumed that coercions are injective. In fact, a projection
(say, from a ring to a quotient ring) will usually become a coercion.


So if we add an element of a subspace with an element of the ambient
space we get the projection of the sum? I would argue this is not the
desired behavior in many situations.


- A = some graded ring, B = some homogeneous component of A
Adding elements of A and B should give an element of A


Here you have a coercion from B to A, and thus no construction functor
or pushout construction is involved.


Ok, it was a simplification. I just feel uncomfortable if a function
(pushout(A,B)) which is supposed to return a common parent of both
fails to do that. E.g. imagine an additional base change is involved,
I think then pushout construction will be involved and the issue
arises. Or are you sure that a situation in spirit like above never
occurs/arises?


- A = some base ring, B = the ring of cusp forms over A
Adding elements of A and B should give an element of
the ring of modular forms over A, however if B is constructed
by A, then the pushout construction will always return B
to which A does not coerce.


That's not my field of expertise, but it sounds like one shouldn't use a
sage.categories.pushout.ConstructionFunctor to describe the construction
of B by A. The construction may be functorial, but there is no
ConstructionFunctor...


What do you mean?


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: issues with pushout construction?

[Jonas Jermann]

Hi Peter

On 27.08.2014 13:03, Peter Bruin wrote:

Hi Jonas,


When I implemented Modular forms rings/spaces for Hecke triangle groups
I ran into some issues with pushout / functors / constructions
(correct me if I missunderstood something):

Apparently the pushout construction implicitely assumes that
there exists a coercion from the construction argument to the
construct:


Ticket #16507 should solve this (at least to some extent) in situations
where there is a coercion B - A instead of A - B.  (Here B is the
object resulting from a functorial construction applied to A; this can
be used if B is a submodule of A, for example.)  This won't address
things like (base ring, cusp forms) - (modular forms), though.


Nice! I missed this ticket.
This exactly addresses one of the issues I mentioned.
I hope it can handle all possible complications
(e.g. base changes, embeddings, etc).

What if there is no coercion in either direction?
E.g. (base_ring, cusp forms ring)

My solution was to use a Facade of the base ring instead of the
base ring itself and let it have an embedding into the base ring.
Because embeddings are checked at the very beginning of the pushout
construction (and only thanks to this) everything worked out.

The important part above was that the facade is _not_ constructed
from the base ring (otherwise we have again the same problem).

All in all the pushout construction is rather complicated (there
are many cases/situations) and when implementing new spaces
one probably (unfortunately) has to look at the source / specific
implementation of pushout in detail to ensure everything works
appropriately in all cases. :-(


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: issues with pushout construction?

[Jonas Jermann]

Hi Peter,

On 27.08.2014 14:01, Peter Bruin wrote:

Hi Jonas,


What if there is no coercion in either direction?
E.g. (base_ring, cusp forms ring)


Maybe #16507 would make this work too if the CuspForms construction were
implemented as a composition: ModularForms followed by CuspidalSubspace,
where CuspidalSubspace would be a special case of SubspaceFunctor (i.e.
with coercion_reversed=True in the terminology of #16507)?  Then
pushout() would remove the application of CuspidalSubspace when merging
the two constructions.


I still don't see how you would distinguish the base ring from a 
normal ring.


Also, how would a base change work with your modification?
pushout(RR, CuspidalSubSpace(ModularForms(ZZ))) resp.
pushout(Base(RR), CuspidalSubSpace(ModularForms(Base(ZZ or

If I understood it would do:

ZZ - ... -  RR - ModularForms(RR) (and stop) resp.
Base(ZZ) - ... -  Base(RR) - ModularForms(Base(RR)) (and stop)

But instead it should return CuspidalSubSpace(ModularForms(RR)).

What I mean is that in some cases the pushout construction should do
almost the same as the construction itself but with
coercion reversion the behavior would be completely different
(since the construction process stops early).

But maybe I missunderstood or this can still be solved in
some smart way...

I should also mention that in my case I have a whole bunch of
subspace constructions:

cuspidal, holomorphic, weakly holomorphic, meromorphic
Additional in each case modular or quasi modular and additional
subspaces of the ambient spaces...

In my case I used the above analytic properties as a parameter of the
functor and let merge decide how to merge the analytic properties...


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: issues with pushout construction?

[Jonas Jermann]

Hi again

I just realized that my example was maybe a bad one.
But imagine the same example for a space where the base ring
_does_ coerce into the space. A base-changed base ring would
then not coerce, so the pushout construction would be used
and it would return the wrong space, resp. my arguments
would make more sense there, no?


Best
Jonas

On 27.08.2014 14:27, Jonas Jermann wrote:

On 27.08.2014 14:01, Peter Bruin wrote:

What if there is no coercion in either direction?
E.g. (base_ring, cusp forms ring)


Maybe #16507 would make this work too if the CuspForms construction were
implemented as a composition: ModularForms followed by CuspidalSubspace,
where CuspidalSubspace would be a special case of SubspaceFunctor (i.e.
with coercion_reversed=True in the terminology of #16507)?  Then
pushout() would remove the application of CuspidalSubspace when merging
the two constructions.


I still don't see how you would distinguish the base ring from a
normal ring.

Also, how would a base change work with your modification?
pushout(RR, CuspidalSubSpace(ModularForms(ZZ))) resp.
pushout(Base(RR), CuspidalSubSpace(ModularForms(Base(ZZ or

If I understood it would do:

ZZ - ... -  RR - ModularForms(RR) (and stop) resp.
Base(ZZ) - ... -  Base(RR) - ModularForms(Base(RR)) (and stop)

But instead it should return CuspidalSubSpace(ModularForms(RR)).

What I mean is that in some cases the pushout construction should do
almost the same as the construction itself but with
coercion reversion the behavior would be completely different
(since the construction process stops early).

But maybe I missunderstood or this can still be solved in
some smart way...

I should also mention that in my case I have a whole bunch of
subspace constructions:

cuspidal, holomorphic, weakly holomorphic, meromorphic
Additional in each case modular or quasi modular and additional
subspaces of the ambient spaces...

In my case I used the above analytic properties as a parameter of the
functor and let merge decide how to merge the analytic properties...


Best
 Jonas


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: issues with pushout construction?

[Jonas Jermann]

Hi Simon

On 27.08.2014 14:46, Simon King wrote:

On 2014-08-27, Jonas Jermann jjerma...@gmail.com wrote:

I was talking/thinking about the implicit call of pushout when e.g.
adding two elements from different parents...


... which is exactly what coercion is about.

Hence, if your functorial construction does not yield a coercion from
the start object to the resulting object O, then don't use
ConstructionFunctor to describe the construction, and most importantly
do not let O.construction() return this non-coercing construction.

Put clearly: If O.construction() returns something that is not suitable
for sage.categories.pushout.pushout, then it is a bug.


Ok, you confirm what I thought: When using constructions it seems to be
a prerequisite that the construction argument coerces into the
constructed object. How would you then define the construction of
modular/cusp forms rings/spaces over some base ring if not by
a functor with argument base ring?

But as I mentioned I made everything work in my case, I e.g. based the 
construction on a Facade of the base ring to distinguish

the two but I don't consider this an elegant solution. :(


It is not assumed that coercions are injective. In fact, a projection
(say, from a ring to a quotient ring) will usually become a coercion.


So if we add an element of a subspace with an element of the ambient
space we get the projection of the sum? I would argue this is not the
desired behavior in many situations.


If you just have a subspace, then why do you think that an arbitrary
(non-canonical!) projection would suddenly come into play? Of course, if
something is constructed as a sub-structure, then the inclusion map is the
only candidate for a coercion. Note that a pushout does not occur in
this situation.


It does if you add the elements. Example adding a modular form and a 
cusp form (lets say over a different base ring so pushout is really 
called). Or modular forms of weight k inside the ring of modular forms, 
etc. Those are sub and not quotient and we want to be able to add them.



However, if you construct something as result of a particular projection
(i.e., if you don't have a *sub* space but a *quotient* space), then it is
desired to use this particular (and no other) projection as a coercion map.


Yes, that makes sense.


Ok, it was a simplification. I just feel uncomfortable if a function
(pushout(A,B)) which is supposed to return a common parent of both
fails to do that.


If pushout(A,B) returns a parent C so that not both A and B coerce into
C, then it's a bug.


Ok, good we agree on that then.
It is what happens currently for some parents, namely those
that violate the above mentioned prerequisite...


E.g. imagine an additional base change is involved,
I think then pushout construction will be involved


A base change is not dealt with by a construction functor, but by setting
the coercion explicitly. This occurs, for example, with the space of
symmetric functions. Here, you have one space without a particular choice
of basis, and then you have different realisations of the space, each with
a particular choice of a basis, and mutual coercions. However, no functorial
construction (hence, no pushout) is involved:

   sage: A = SymmetricFunctions(QQ); A
   Symmetric Functions over Rational Field
   sage: S = A.schur(); S
   Symmetric Functions over Rational Field in the Schur basis
   sage: W = A.witt(); W
   Symmetric Functions over Rational Field in the Witt basis
   sage: W.has_coerce_map_from(S)
   True
   sage: S.has_coerce_map_from(W)
   True
   sage: S.construction()
   sage: W.construction()
   sage: A.construction()


RR(1) + some element of a space whose construction is based on ZZ
^- This calls pushout(RR, constr(ZZ)) which should return constr(RR)
which is in essence an implicit base change. The code of pushout/etc 
seems to indicate that this is intended and I think it is used for

some/many(?) spaces.


That's not my field of expertise, but it sounds like one shouldn't use a
sage.categories.pushout.ConstructionFunctor to describe the construction
of B by A. The construction may be functorial, but there is no
ConstructionFunctor...


What do you mean?


Quite simply: Do not over-generalise. The pushout construction is a quite
interesting part of Sage's coercion system, but many (perhaps most) coercions
in real-life computations do not involve pushouts.


I needed to generalize it, otherwise some very basic operations just 
fail. :-( Also sage forces one to define constructions, otherwise common

parents won't be found. In any case, I have solved those issues for my
implementation. I just wanted to raise my concern about the
complex/seemingly contradictory behavior of pushout+constructions.

But if everything is as it should be then that's fine by me (I have
a working implementation).


Best
Jonas

--
You received this message because you are subscribed to the Google Groups 
sage-devel group.
To unsubscribe from this group and stop

Re: [sage-devel] Re: issues with pushout construction?

[Jonas Jermann]

On 27.08.2014 15:06, Peter Bruin wrote:

Hi Jonas,


I just realized that my example was maybe a bad one.  But imagine the
same example for a space where the base ring _does_ coerce into the
space. A base-changed base ring would then not coerce, so the pushout
construction would be used and it would return the wrong space,
resp. my arguments would make more sense there, no?


Do you mean something like the following?  Assume you have a
construction EvenSubspace() that applies to spaces of polynomials and
returns the subspace of all polynomials that only have even powers of x.
This of course includes constants.  Suppose you have a ring homomorphism
A - B and you want to do

pushout(B, EvenSubspace(PolynomialRing(A, 'x')))


Yes. I call this (implicit) base change where I mean base in the 
sense of base of construction (which in many cases starts as a ring).

This assumes that the base object coerces into the constructed object.


I guess my approach would indeed eliminate the application of
EvenSubspace() because it doesn't know that B still coerces into
EvenSubspace(PolynomialRing(B, 'x')).


1.1 + x^2 would e.g. fail resp. not lie in EvenSubSpace.


 If this is the case, the
criterion for eliminating a coercion-reversed construction step F
probably needs to be made more strict: if both of the original objects
still coerce into the result of applying F, then we do want to apply F.
Does that sound reasonable?


I'm not sure. I was hoping for a simple system where it is clear what
happens. But since this would probably involve a partial redesign
of the pushout construction all-together and since so many things
depend on the old system I don't see this happening any time soon. :(

Regarding your suggestion/fix:
I'm not sure (as mentioned the pushout construction is complex and
there are many cases). But yes, that might work:
Do a/several coercion check(s) _during_ pushout (during the while loop
starting at line 3210) if needed instead of only at the end.

So coercion_reversed=False (default) would mean that we assume that
the current base coerces into construction(base) and
coercion_reversed=False would mean that a coercion check should be
done.

If yes: Maybe something like force_coercion_check fits better?
Note: That would actually work in general (always doing a coercion
check) but for performance reasons it's nice to only do it when
forced...


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: flint revert_series

[Jonas Jermann]

Hi

On 22.07.2014 14:47, Jean-Pierre Flori wrote:

My point of view is let's make one step at a time or we'll just never
include anything in Sage.
So I think the little wrapper you submitted is a good inclusion.
For sure we should also implement all that Fredrik and you suggested,
but let's already include what you already did.


I added revert_series for flint over finite fields and I applied the
suggested corrections. So the ticket is ready for review again.


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: flint revert_series

[Jonas Jermann]

Hi

On 21.07.2014 13:10, Fredrik Johansson wrote:

On Mon, Jul 21, 2014 at 7:37 AM, Jonas Jermann jjerma...@gmail.com wrote:

I agree, but somehow the flint import details are slightly different.
I also saw a different name somewhere, reverse_series. So I was not
sure how to exactly import it for nmod. I would appreciate if someone
familiar with flint could do that (or leave it out for now).


You could use some other method in polynomial_zmod_flint.pyx as a
template; reverse() for example.

I guess you saw reverse_series in nmod_poly.pxd. This file is just
out of date and should be updated to match the nmod_poly.h in the
latest flint.


I added the zmod revert_series but somehow the result is wrong(?), even 
if I increase the precision. Attached is a patch against the current 
ticket with the failing doctest. Maybe revert_series does not exactly do 
what we/I expect for finite fields, it seems to drop the t^5 term over 
GF(5)?



Another idea (perhaps for a separate update) would be to add a sage
implementation of flint's algorithm for reversion over generic base
ring. This is Algorithm 1: Fast Lagrange inversion in
http://www.ams.org/journals/mcom/-000-00/S0025-5718-2014-02857-3/
(if you can't access it, http://arxiv.org/abs/1108.4772). The generic
code would be a little slower than flint's implementations over Z, Q and
Z/nZ, so you definitely want to special-case those. But in general, this
should be much faster than sage's current implementation for polynomials
of high degree.



I am not familiar with the details but I assume that the algorithm
heavily depends on the performance of power series operations like
multiplication or inversion. See e.g. fredrikj.net/math/rev.pdf


The fast reversion algorithm basically does fewer polynomial
multiplications than the naive algorithm (O(n^0.5) instead of O(n)),
so it's an improvement regardless of whether polynomial multiplication
is slow or fast.


That's very nice and only positive change. :)
It's an independent modification of the current ticket though, right?

I still feel the best long-term solution would be to use
flint for power series. That would give a huge performance boost.
But again, that's an independent question: The ticket could be applied 
even if flint was already used for power series.



Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
diff --git a/src/sage/libs/flint/nmod_poly.pxd b/src/sage/libs/flint/nmod_poly.pxd
index e99a228..3926a6c 100644
--- a/src/sage/libs/flint/nmod_poly.pxd
+++ b/src/sage/libs/flint/nmod_poly.pxd
@@ -68,6 +68,8 @@ cdef extern from flint/nmod_poly.h:
 cdef void nmod_poly_one(nmod_poly_t res)
 cdef void nmod_poly_truncate(nmod_poly_t poly, long len)
 cdef void nmod_poly_reverse(nmod_poly_t output, nmod_poly_t input, long m)
+cdef void nmod_poly_revert_series(nmod_poly_t output, nmod_poly_t intput, long m)
+
 cdef int nmod_poly_equal(nmod_poly_t a, nmod_poly_t b)
 
 # Powering
diff --git a/src/sage/rings/polynomial/polynomial_zmod_flint.pyx b/src/sage/rings/polynomial/polynomial_zmod_flint.pyx
index 1856be1..254501c 100644
--- a/src/sage/rings/polynomial/polynomial_zmod_flint.pyx
+++ b/src/sage/rings/polynomial/polynomial_zmod_flint.pyx
@@ -767,3 +767,39 @@ cdef class Polynomial_zmod_flint(Polynomial_template):
 else:
 nmod_poly_reverse(res.x, self.x, nmod_poly_length(self.x))
 return res
+
+def revert_series(self, n):
+r
+Return a polynomial `f` such that `f(self(x)) = self(f(x)) = x mod x^n`.
+
+EXAMPLES::
+
+sage: R.t =  GF(5)[]
+sage: f = t - t^3 + t^5
+sage: f.revert_series(5)  # todo: this fails (needs to be fixed)!
+t + t^3 + 2*t^5
+
+sage: f.revert_series(-1)
+Traceback (most recent call last):
+...
+ValueError: argument n must be a non-negative integer, got -1
+
+sage: g = - t^3 + t^5
+sage: g.revert_series(6)
+Traceback (most recent call last):
+...
+ValueError: self must have constant coefficient 0 and a unit for coefficient 1
+
+cdef Polynomial_zmod_flint res = self._new()
+cdef unsigned long m
+if n  0:
+raise ValueError(argument n must be a non-negative integer, got %s % n)
+m = n
+if not self[0].is_zero() or not self[1].is_unit():
+raise ValueError(self must have constant coefficient 0 and a unit for coefficient 1)
+
+sig_on()
+nmod_poly_revert_series(res.x, self.x, m)
+sig_off()
+
+return

Re: [sage-devel] Re: flint revert_series

[Jonas Jermann]

On 22.07.2014 14:42, Fredrik Johansson wrote: On Tue, Jul 22, 2014 at
 The reversion of t - t^3 + O(t^5) to length n = 5 should be t + t^3 +
 O(t^5). This is what I get when I call flint directly from a C
 program. Are you getting something different?

I meant to write revert_series(6) which didn't produce the t^5 term
with flint but did with sage's reversion.

 Note that the current implementation requires that 1, 2, ..., n-1 are
 invertible (this restriction is documented in the flint manual). So
 for polynomials over GF(5), n = 6 would be invalid input. You could
 insert some code that checks this and either raises an exception or
 computes over Z or Q and converts back.

Oh right. Thanks, I didn't realize that. That seems like a pretty 
serious restriction. :(


I added support for flint's revert_series with that restriction.


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: flint revert_series

[Jonas Jermann]

Hi Frederik

On 20.07.2014 15:20, Fredrik Johansson wrote:

There is also an nmod_poly_revert_series in flint for polynomials over
Z/nZ for word-size n. It would not hurt to wrap that function in the
same patch.


I agree, but somehow the flint import details are slightly different.
I also saw a different name somewhere, reverse_series. So I was not
sure how to exactly import it for nmod. I would appreciate if someone 
familiar with flint could do that (or leave it out for now).



Another idea (perhaps for a separate update) would be to add a sage
implementation of flint's algorithm for reversion over generic base
ring. This is Algorithm 1: Fast Lagrange inversion in
http://www.ams.org/journals/mcom/-000-00/S0025-5718-2014-02857-3/
(if you can't access it, http://arxiv.org/abs/1108.4772). The generic
code would be a little slower than flint's implementations over Z, Q and
Z/nZ, so you definitely want to special-case those. But in general, this
should be much faster than sage's current implementation for polynomials
of high degree.


I am not familiar with the details but I assume that the algorithm
heavily depends on the performance of power series operations like 
multiplication or inversion. See e.g. fredrikj.net/math/rev.pdf


Flint is quite fast for all of those and I think sage's power series 
implementation is not optimized at all (does it even support fast 
multiplication?).


The ideal solution would be to directly improve sage's power series 
implementation (e.g. using flint's code, which probably requires quite
a lot of work). In any case if you can implement the mentioned 
improvement above that would be great of course. :-)


I simply suggested a small, non-intrusive patch in the meantime which 
allows one to use flint. Also, the patch could be applied independent of 
the suggested improvement above.



Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] flint revert_series

[Jonas Jermann]

Hi all

Could someone familiar with flint/sage enable flint's
revert_series (for rational/integer polynomials)?

(Sorry if it was already implemented somewhere and I missed it).

Attached is a small, non-intrusive patch (done with help from IRC)
in that direction which simply adds series reversion for
integer and rational flint polynomials.

For those polynomials (resp. power series) flint is _much_
faster than the current implementation of power series reversion
(which is a big bottleneck for the modular forms code I currently
work on - u/jj/hecke_mf).

In my opinion this offers an acceptable and small compromise which
in particular doesn't (yet) require to implement power series using 
flint. For someone interested in using it for power series, simply 
convert the series to a (flint) polynomial, apply flint's revert_series 
and convert the result back to a power series.


It could of course also be used to replace the current power series
reversion over integers/rationals.


Best
Jonas

--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
diff --git a/src/sage/libs/flint/fmpq_poly.pxd b/src/sage/libs/flint/fmpq_poly.pxd
index 78c9581..10dbca6 100644
--- a/src/sage/libs/flint/fmpq_poly.pxd
+++ b/src/sage/libs/flint/fmpq_poly.pxd
@@ -92,6 +92,7 @@ cdef extern from flint/fmpq_poly.h:
 void fmpq_poly_get_slice(fmpq_poly_t, fmpq_poly_t, long, long)
 void fmpq_poly_truncate(fmpq_poly_t, unsigned long)
 void fmpq_poly_reverse(fmpq_poly_t, fmpq_poly_t, unsigned long)
+void fmpq_poly_revert_series(fmpq_poly_t, fmpq_poly_t, unsigned long)
 
 void fmpq_poly_set_array_mpq(fmpq_poly_t, mpq_t *, unsigned long)
 void fmpq_poly_from_string(fmpq_poly_t, char *)
diff --git a/src/sage/libs/flint/fmpz_poly.pxd b/src/sage/libs/flint/fmpz_poly.pxd
index 40cc231..9ff7b28 100644
--- a/src/sage/libs/flint/fmpz_poly.pxd
+++ b/src/sage/libs/flint/fmpz_poly.pxd
@@ -11,3 +11,5 @@ cdef class Fmpz_poly(SageObject):
 cdef extern from flint/fmpz_poly.h:
 cdef void fmpz_poly_reverse(fmpz_poly_t output, fmpz_poly_t input,
 unsigned long length)
+cdef void fmpz_poly_revert_series(fmpz_poly_t output, fmpz_poly_t input,
+unsigned long length)
diff --git a/src/sage/rings/polynomial/polynomial_integer_dense_flint.pyx b/src/sage/rings/polynomial/polynomial_integer_dense_flint.pyx
index 34b1380..aef1e40 100644
--- a/src/sage/rings/polynomial/polynomial_integer_dense_flint.pyx
+++ b/src/sage/rings/polynomial/polynomial_integer_dense_flint.pyx
@@ -41,7 +41,8 @@ from sage.structure.factorization import Factorization
 from sage.rings.fraction_field_element import FractionFieldElement
 from sage.rings.arith import lcm
 
-from sage.libs.flint.fmpz_poly cimport fmpz_poly_reverse
+from sage.libs.flint.fmpz_poly cimport fmpz_poly_reverse, fmpz_poly_revert_series
+
 from sage.libs.flint.ntl_interface cimport fmpz_poly_set_ZZX, fmpz_poly_get_ZZX
 from sage.libs.ntl.ntl_ZZX_decl cimport *, vec_pair_ZZX_long_c
 
@@ -1406,3 +1407,19 @@ cdef class Polynomial_integer_dense_flint(Polynomial):
 fmpz_poly_reverse(res.__poly, self.__poly,
 fmpz_poly_length(self.__poly))
 return res
+
+def revert_series(self, n):
+
+Return a polynomial f such that f(self(x)) = f(self(x)) = x mod x^n.
+
+
+cdef Polynomial_integer_dense_flint res = self._new()
+cdef unsigned long m   
+m = n
+if m != n:
+raise ValueError, argument n must be a non-negative integer, got %s%(n)
+if not self[0].is_zero() or not self[1].is_unit():   
+raise ValueError, self must have constant coefficient 0 and +1 or -1 as the coefficient for x^1
+
+fmpz_poly_revert_series(res.__poly, self.__poly, m)
+return res
diff --git a/src/sage/rings/polynomial/polynomial_rational_flint.pyx b/src/sage/rings/polynomial/polynomial_rational_flint.pyx
index 0c13ffe..f287aa0 100644
--- a/src/sage/rings/polynomial/polynomial_rational_flint.pyx
+++ b/src/sage/rings/polynomial/polynomial_rational_flint.pyx
@@ -614,6 +614,23 @@ cdef class Polynomial_rational_flint(Polynomial):
 if do_sig: sig_off()
 return res
 
+def revert_series(self, n):   
+
+Return a polynomial f such that f(self(x)) = f(self(x)) = x mod x^n.
+
+
+cdef Polynomial_rational_flint res = self._new()
+cdef unsigned long m   
+m = n
+if m != n:
+raise ValueError, argument n must be a non-negative integer, got %s%(n)
+if not self[0].is_zero() or not self[1].is_unit():
+raise ValueError, self must 

Re: [sage-devel] Re: flint revert_series

[Jonas Jermann]

Hi

On 19.07.2014 23:48, Jean-Pierre Flori wrote:

I can have a look next week.


Thanks!


Would you mind opening a ticket on trac for this?


http://trac.sagemath.org/ticket/16685


Best
Jonas


On Saturday, July 19, 2014 8:10:33 PM UTC+2, Jonas Jermann wrote:

Hi all

Could someone familiar with flint/sage enable flint's
revert_series (for rational/integer polynomials)?

(Sorry if it was already implemented somewhere and I missed it).

Attached is a small, non-intrusive patch (done with help from IRC)
in that direction which simply adds series reversion for
integer and rational flint polynomials.

For those polynomials (resp. power series) flint is _much_
faster than the current implementation of power series reversion
(which is a big bottleneck for the modular forms code I currently
work on - u/jj/hecke_mf).

In my opinion this offers an acceptable and small compromise which
in particular doesn't (yet) require to implement power series using
flint. For someone interested in using it for power series, simply
convert the series to a (flint) polynomial, apply flint's revert_series
and convert the result back to a power series.

It could of course also be used to replace the current power series
reversion over integers/rationals.


Best
  Jonas

--
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
mailto:sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com
mailto:sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.


--
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 http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.