Example of an UFD in Sage for which is_unit is significantly slower than is_one

[Martin R]

Dear all,

for testing purposes I am in need of an UFD in Sage for which is_unit is significantly slower than is_one.  Note that, unfortunately, quotient rings do not seem supported currently.

Background: my pull request https://github.com/sagemath/sage/pull/38924 provides a critical speedup for several computations. Originally, I did this to make my functional equations solver usable, but it also affects completely unrelated code.  For example,

sage: P.<x,y>=ProjectiveSpace(QQbar, 1) 

sage: E=EllipticCurve([1, 2]) 

sage: f=P.Lattes_map(E, 2) 

sage: f.Lattes_to_curve(check_lattes=true)

gets a speedup from 14 seconds down to 8 seconds.

The pull requests optimises a gcd computation in generic (i.e., non-libsingular) polynomial rings.  One difference is, that when computing the content of a polynomial, I am checking for is_unit(), rather than is_one().

In all rings I could construct, there is not a huge difference in timings for the two methods.  But I would like to make sure that I am not missing anything, especially since we still do not have any performance regression tests.

Best wishes,

Martin

[Marc Mezzarobba]

'Martin R' via sage-devel wrote:
> for testing purposes I am in need of an UFD in Sage for which is_unit
> is significantly slower than is_one.

Matrices?

--
Marc

[Marc Mezzarobba]

Marc Mezzarobba wrote:
>> for testing purposes I am in need of an UFD in Sage for which is_unit
>> is significantly slower than is_one.
>
> Matrices?

Woops, I read “a ring” insteand of “an ufd”...

--
Marc

[Nils Bruin]

Quadratic rings perhaps? A fair number of those are UFD:

sage: K.<a>=NumberField(x^2-3)
sage: O=K.ring_of_integers()
sage: b=O(a-2)
sage: %timeit b.is_unit()
664 ns ± 4.24 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
sage: %timeit b.is_one()
55.8 ns ± 0.214 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

[Martin R]

Great, thank you! This - almost - provides a performance test:
```

sage: K.<a>=NumberField(x^2-3)
sage: O=K.ring_of_integers()
sage: b=O(a-2)

sage: R.<z> = O[]
sage: f = O(2*a + 4)*z^2
sage: f.gcd(f+1)
...
NotImplementedError: Maximal Order generated by a in Number Field in a with defining polynomial x^2 - 3 does not provide a gcd implementation for
univariate polynomials
sage: O._refine_category_(UniqueFactorizationDomains())
sage: f.gcd(f+1)
...
File ~/sage/src/sage/rings/polynomial/polynomial_element.pyx:5373, in sage.rings.polynomial.polynomial_element.Polynomial.pseudo_quo_rem()
5371 diffdeg = R.degree() - B.degree()
5372 Q = d*Q + self._parent(c).shift(diffdeg)
-> 5373 R = d*R - c*B.shift(diffdeg)
5374 e -= 1
5375
...
TypeError: unsupported operand parent(s) for *: 'Number Field in a with defining polynomial x^2 - 3' and 'Univariate Polynomial Ring in z over Maximal
Order generated by a in Number Field in a with defining polynomial x^2 - 3'

```

:-(

Martin

[Nils Bruin]

On Thursday, 12 December 2024 at 12:39:46 UTC-8 axio...@yahoo.de wrote:

Great, thank you! This - almost - provides a performance test:

Yes, you would need to convince sage that this is indeed a euclidean ring (I think for this one the usual norm actually is a euclidean norm). I don't think that simply being a UFD will do it for you.

[Martin R]

This does not look right, does it?

sage: K.<a> = NumberField(x^2-3)

sage: O = K.ring_of_integers()
sage: c = O(2*a + 4)
sage: isinstance(O, Field)
False
sage: isinstance(c, FieldElement)
True

Martin

[Dima Pasechnik]

On Fri, Dec 13, 2024 at 1:38 PM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> This does not look right, does it?
>
> sage: K.<a> = NumberField(x^2-3)
> sage: O = K.ring_of_integers()
> sage: c = O(2*a + 4)
> sage: isinstance(O, Field)
> False
> sage: isinstance(c, FieldElement)
> True

c is an element of K, by construction.

>
> Martin
> On Thursday, 12 December 2024 at 23:35:40 UTC+1 Nils Bruin wrote:
>>
>> On Thursday, 12 December 2024 at 12:39:46 UTC-8 axio...@yahoo.de wrote:
>>
>> Great, thank you! This - almost - provides a performance test:
>>
>>
>> Yes, you would need to convince sage that this is indeed a euclidean ring (I think for this one the usual norm actually is a euclidean norm). I don't think that simply being a UFD will do it for you.
>

> --
> 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+...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/35043e34-7915-4c54-9c74-29521c3762e1n%40googlegroups.com.

[David Roe]

On Fri, Dec 13, 2024 at 2:38 PM 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:

This does not look right, does it?

sage: K.<a> = NumberField(x^2-3)

sage: O = K.ring_of_integers()
sage: c = O(2*a + 4)
sage: isinstance(O, Field)
False
sage: isinstance(c, FieldElement)
True

It's not ideal, but OrderElement_quadratic inherits from NumberFieldElement_quadratic because there's a lot of common functionality, which eventually inherits from FieldElement.  It's basically a consequence of Cython not supporting multiple inheritance.

David

Martin

On Thursday, 12 December 2024 at 23:35:40 UTC+1 Nils Bruin wrote:

On Thursday, 12 December 2024 at 12:39:46 UTC-8 axio...@yahoo.de wrote:

Great, thank you! This - almost - provides a performance test:

Yes, you would need to convince sage that this is indeed a euclidean ring (I think for this one the usual norm actually is a euclidean norm). I don't think that simply being a UFD will do it for you.

--

[Martin R]

Well, only if the ring of integers is just a subset of K.

Essentially, that means that we cannot really compute with O - eg., compute the gcd of two polynomials over O.

Martin

[Dima Pasechnik]

On Fri, Dec 13, 2024 at 3:04 PM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> Well, only if the ring of integers is just a subset of K.
>
> Essentially, that means that we cannot really compute with O - eg., compute the gcd of two polynomials over O.

polynomials over rings are tricky.

sage: P.<t>=O[]
sage: c*t^2-2
(2*a + 4)*t^2 - 2
sage: (c*t^2-2).gcd(2*t+2)
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)

...
NotImplementedError: Maximal Order generated by a in Number Field in a
with defining polynomial x^2 - 3 does not provide a gcd implementation
for univariate polynomials



>

> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/a8ab4860-50d3-49e8-8e9c-896bc41e350en%40googlegroups.com.