Unify matrix space implementations, possibly get rid of them

[fingolfin]

We have lots of concrete MatSpace subtypes. They all do basically the exact same thing, just for different base types. Some perform input validation, some don't. A few actually a little bit of extra data (the modulus of the basering).

Looking at it, I don't see why we can't use a single concrete parametric type? Let's say it is called Nemo.MatrixSpace{elemT, T} <: AbstractAlgebra.MatSpace{elemT}. Then this would get rid of a lot of code duplication, and automatically ensure some consistency. We can still implement ring specific extensions, e.g. ZZMatrixSpace has a constructor that takes no ring, so that would still work if we wanted to -- although I don't really see a need for that, you should construct it via matrix_space(ZZ,r,c).

E.g.

function (a::FpMatrixSpace)()
  z = FpMatrix(nrows(a), ncols(a), a.n)
  z.base_ring = a.base_ring
  return z
end

could become

function (a::MatrixSpace{FpFieldElem, FpField})()
  z = FpMatrix(nrows(a), ncols(a), a.base_ring n)
  z.base_ring = a.base_ring
  return z
end

While some could even be made fully generic, e.g.:

function (a::FpMatrixSpace)(b::IntegerUnion)
   M = a()  # zero
   for i in 1:min(nrows(a), ncols(a))
      M[i, i] = base_ring(a)(b)
   end
   return M
end

could become

function (a::MatrixSpace)(b::IntegerUnion)
   M = a()  # zero matrix
   R = base_ring(a)
   for i in 1:min(nrows(a), ncols(a))
      M[i, i] = R(b)
   end
   return M
end

We might be able to use even more generic methods if we add a matrix_type method which maps a MatrixSpace type or instance to a concrete matrix type... Then we could have methods like this:

function (a::MatrixSpace{elemT, ringT)(arr::AbstractMatrix{elemT}) where {elemT, ringT}
  _check_dim(nrows(a), ncols(a), arr)
  return matrix(base_ring(a), arr)
end

While at it, we could also use WeakKeyIdDict from oscar-system/Oscar.jl#1872 to improve those caches, like const GaloisFmpzMatID = Dict{Tuple{FpField, Int, Int}, FpMatrixSpace}() which currently seem to be sources of leaks?

This would also resolve #1317

[thofma]

Regarding caching, Nemo is not using WeakValueDict from AbstractAlgebra so far. This would solve the "problem". (I don't consider this is a bug or a leak. It is the behaviour one gets by using the caching.)

[fingolfin]

I was not concerned about the value of the dict (i.e. the matrix space) staying around so much as the key (which includes the ring) staying around. Hence WeakKeyIdDict (not WeakValueDict). But now that I think about it, I realize that may not help, because the matrix space also has a reference to the ring... sigh

Anyway: those dicts means that once you create a matrix space, neither it nor the underlying ring will ever be garbage collected. It's not hard to think of badly written function that creates a fresh ring, then a matrix space over that ring, just to get a matrix. Each call to that function will now leak one ring plus one matrix space.

That seems like a bug to me, because there is no way to flush those caches safely (at least in the current implementation: if I just empty! those dicts, we violate other invariants, as the next time someone asks for a matrix space for the same ring, a new one will be created, which won't be equal to the previous one, etc.).

Now that I think about it, wouldn't a simple solution for this be to get rid of these caches by having the new unified type I proposed be a struct, not a mutable struct. I.e.:

struct MyMatrixSpace{elemT, ringT} <: MatSpace{elemT}
  base_ring::ringT
  nrows::Int
  ncols::Int

  function MyMatrixSpace(R::T, r::Int, c::Int, cached::Bool = true) where T
    # cached is ignored, and just there for backwards compatibility
    (r < 0 || c < 0) && throw(error_dim_negative)
    return new{elem_type(T), T}(R, r, c)
  end
end

Any downsides I am overlooking?

[fingolfin]

As Markus Kurtz (sorry, I don't have the GitHub name handy) pointed out to me, a lot of the things I propose above could already now be done inside AbstractAlgebra, for MatSpace itself: I.e. this should work, I think?

function (a::MatSpace)(b::IntegerUnion)
   R = base_ring(a)
   return a(R(b))
end

function (a::MatSpace{T})(b::T) where T
   M = a()  # zero matrix
   R = base_ring(a)
   for i in 1:min(nrows(a), ncols(a))
      @inbounds M[i, i] = b
   end
   return M
end

[fingolfin]

Random vaguely related observation: many identity_matrix methods (maybe not those which ccall dedicated helpers) could be replaced by a single generic implementation, like this one from fq_default_mat:

function identity_matrix(R::FqField, n::Int)
   z = zero_matrix(R, n, n)
   for i in 1:n
      z[i, i] = one(R)
   end
   return z
end

possibly tweaked to

function identity_matrix(R::FqField, n::Int)
   z = zero_matrix(R, n, n)
   b = one(R)
   for i in 1:n
      @inbounds z[i, i] = b
   end
   return z
end

[thofma]

I was not concerned about the value of the dict (i.e. the matrix space) staying around so much as the key (which includes the ring) staying around. Hence WeakKeyIdDict (not WeakValueDict). But now that I think about it, I realize that may not help, because the matrix space also has a reference to the ring... sigh

It seems this is a problem with all things that we are caching? Almost all cached objects have a reference to the "previous" object. Maybe we need a dictionary with weak keys and values?

We could fix the matrix spaces and make them immutable, but the underlying problem will persist.