Use lazy attribute for _Karatsuba_threshold

[jdemeyer]

This avoids a nasty import at startup of matrix.matrix_space in polynomial rings.

I'm adding a dependency on #24947 which is technically not needed, but it makes it easier to merge things in #24742.

Depends on #24947

Component: misc

Author: Jeroen Demeyer

Branch/Commit: f14395c

Reviewer: Marc Mezzarobba

Issue created by migration from https://trac.sagemath.org/ticket/24945

[jdemeyer]

Branch: u/jdemeyer/avoid_importing_matrices_in_polynomial_rings

[jdemeyer]

New commits:

0b4bdd8

Avoid importing matrices in polynomial rings

[jdemeyer]

Commit: 0b4bdd8

[mezzarobba]

comment:3

LGTM, but what about making the (default, since there is a method to override it...) threshold an attribute of the base ring instead?

[videlec]

comment:4

Why is there a need for a try/except here!?

[jdemeyer]

comment:5

Replying to @videlec:

Why is there a need for a try/except here!?

Because this is happening at Sage startup time. So sage.all.MatrixSpace may not exist yet.

[videlec]

comment:6

Replying to @jdemeyer:

Replying to @videlec:

Why is there a need for a try/except here!?

Because this is happening at Sage startup time. So sage.all.MatrixSpace may not exist yet.

This is very bad. I am very much in favor of something like Marc suggested

try:
   threshold = base_ring._karatsuba_threshold
except AttributeError:
    threshold = 0

that would not depend on some startup effect.

[jdemeyer]

comment:7

Hmm, adding that to all possible base rings seems strange. I would much rather do it depending on the element class. For example, generic polynomials would not use Karatsuba, but polynomials over ZZ would.

[jdemeyer]

comment:8

I'm thinking of something like

        # element class determines default Karatsuba threshold
        self._Karatsuba_threshold = self.Element._default_karatsuba_threshold(base_ring)

[mezzarobba]

comment:9

Replying to @jdemeyer:

Hmm, adding that to all possible base rings seems strange. I would much rather do it depending on the element class. For example, generic polynomials would not use Karatsuba, but polynomials over ZZ would.

As far as I understand, the goal is not to decide whether to use Karatsuba, but when the generic multiplication code should switch from the schoolbook algorithm to Karatsuba. This depends on the base ring (or its element class): basically, the more expensive multiplication is compared to addition, the lower the threshold should be. And yes, I guess most base rings wouldn't need to override the default value.

[jdemeyer]

comment:10

But we have really a lot of possible base rings in Sage. Should they all get a _default_karatsuba_threshold() method?

[jdemeyer]

comment:11

A different solution is to use a lazy_attribute instead for _Karatsuba_threshold. That might solve the startup problem.

[mezzarobba]

comment:12

Replying to @jdemeyer:

But we have really a lot of possible base rings in Sage. Should they all get a _default_karatsuba_threshold() method?

I don't know. Would it be a problem to have such a method (or a simple attribute) either in the category of rings or even in Parent?

[jdemeyer]

Dependencies: #24947

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

447b4e5	Properly fix signature of Matrix_gfpn_dense.__init__
f14395c	Use a lazy_attribute for _Karatsuba_threshold

[sagetrac-git]

Changed commit from 0b4bdd8 to f14395c

[jdemeyer]

comment:15

I went with the simple solution of using a lazy_attribute.

[mezzarobba]

Reviewer: Marc Mezzarobba

[vbraun]

Changed branch from u/jdemeyer/avoid_importing_matrices_in_polynomial_rings to f14395c