similar/map_coeffs/map_entries desired behaviour

[wbhart]

After carefully analysing the expected behaviour of similar in Julia, we reached the following conclusions:

• In Julia, similar effectively takes three arguments, 1) a "kind" of matrix, e.g. sparse or dense, etc. 2) an element type, 3) dimensions, the last two of which are optional, and it creates another matrix of the same "kind" (if possible) with the given type and dimensions.

• In Julia, similar exists to remove the overhead of initialising arrays, since it has the notion of uninitialised values, and can detect when heap allocated objects are uninitialised, and since in any case it can save writing zeroes even for non heap allocated objects.

• the broad assumption is that in Julia a matrix is a kind of array, and therefore being treated as a container of elements with indexing.

Now it makes some kind of sense to implement similar for AbstractAlgebra matrices, especially since they have Julia arrays underlying them. (It probably also makes sense for generic dense univariate polynomials. But that is not particularly relevant here.)

But in Nemo, there is no way to create an uninitialised matrix. This would have to be supported in Flint (which it is not), and in any case, if others want to use our matrix interface, we cannot demand that they rewrite all their code to support uninitialised entries in their matrix types.

For this reason, similar with three arguments (or even just the first two arguments) is pointless for Nemo and other similar libraries, and it is just adding to the interface burden to demand that it be implemented.

Therefore, the behaviour we would like is the following:

• similar will always try to create the same "kind" of matrix. In particular, if you start with a generic AbstractAlgebra matrix, it will also return one. As we have separated the discussion about change_base_ring by not making it depend on similar, this does not lead to problems. The semantics of similar are the Julia semantics. We should not try to change this.

• in the case of a library like Flint, similar will not be implemented. This means it will only be in the optional part of the interface. Generic code can still call it though, as it will fall back to calling zero, which is required to be implemented by Nemo, for example.

• map_entries will be implemented in terms of similar......

Ok, clearly this doesn't work. Back to the drawing board.

[rfourquet]

To expand on that, and according to what we discussed: the only use case for similar taking a base ring was map. But as it's now clarified that 1) similar must return a "similar" kind of matrix and 2) map must choose the best output matrix type, similar is not the right tool for implementing map.

I will then implement the following, unless upcoming discussion reaches different conclusions:

• Remove the "change base ring" functionality from similar. Someone might still have found it useful in some cases, but it complicates the interface for no obvious benefit; this someone will then have to pay the price for getting the desired functionality.
• Make similar optional in the interface, by defaulting to zero: in the oscar ecosystem, matrix types supporting unitialized slots are the exceptions, so the burden to specialize a method (similar) will be on them (instead of asking other matrix types to specialize zero, which would be needed to not zero-initialize twice).
• We have the following method in the required interface for matrices: (S::MyMatSpace{T})(A::Array{T, 2}) where T. We can then support a (relatively inefficient) fallback for zero, which therefore doesn't have to be in the required interface: zero(A) = parent(A)(fill(zero(eltype(A)), nrows(A), ncols(A))).

[wbhart]

Not that I mind too much, but zero has different semantics to similar. I'm not too sure similar should fall back to zero any more.

I honestly think similar is only useful for AbstractAlgebra for Julia compatibility and not much else.

I'm reluctant to make it a required part of the interface, lest people use it, which would probably result in breakage

On Mon, Oct 28, 2019, 11:20 AM Rafael Fourquet notifications@github.com wrote:

To expand on that, and according to what we discussed: the only use case for similar taking a base ring was map. But as it's now clarified that 1) similar must return a "similar" kind of matrix and 2) map must choose the best output matrix type, similar is not the right tool for implementing map.

I will then implement the following, unless upcoming discussion reaches different conclusions:

• Remove the "change base ring" functionality from similar. Someone might still have found it useful in some cases, but it complicates the interface for no obvious benefit; this someone will then have to pay the price for getting the desired functionality.
• Make similar optional in the interface, by defaulting to zero: in the oscar ecosystem, matrix types supporting unitialized slots are the exceptions, so the burden to specialize a method (similar) will be on them (instead of asking other matrix types to specialize zero, which would be needed to not zero-initialize twice).
• We have the following method in the required interface for matrices: (S::MyMatSpace{T})(A::Array{T, 2}) where T. We can then support a (relatively inefficient) fallback for zero, which therefore doesn't have to be in the required interface: zero(A) = parent(A)(fill(zero(eltype(A)), nrows(A), ncols(A))).

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/Nemocas/AbstractAlgebra.jl/issues/515?email_source=notifications&email_token=AAB3HJQAJIAJS7CONVRIR6LQQ24HDA5CNFSM4JEUXER2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOECMME4I#issuecomment-546882161, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAB3HJVJX5PMAV7GVM72KATQQ24HDANCNFSM4JEUXERQ .

[rfourquet]

I'm reluctant to make it a required part of the interface

He, we settled on making it "optional" ! But do you mean that you want to keep it undocumented? and use it only internally for AbstractAlgebra generic matrices?

I don't mind too much, but still prefer to have it offcial, I don't think having a line saying something like "similar(a) gives a matrix with same type/ring as a with potentially unitialized entries (defaults to zero(a))" is a big deal. I don't like keeping power away from the user. If as a newcomer I wanted to implement a matrix algorithm, I would defintely end up finding out about similar in "Matrix.jl", and would use it even if not documented. The need for a similar-lile function won't go away.

[tthsqe12]

It can be documented. It just can't be used in Generic code if it is optional (since it may not be implemented for things that need to use generic code).

[wbhart]

That was me, not @tthsqe12. He left me logged in as him.

[rfourquet]

It can be documented. It just can't be used in Generic code if it is optional (since it may not be implemented for things that need to use generic code).

The point of similar is to be used in generic code, in particular in the "Matrix.jl" file. If it can be used only on Generic.MatElem, them it won't be used, no-one wants to write algorithm against a specific type.

We had agreed that similar is optional, falling back to zero. What is the drawback of that?

[wbhart]

It's just that we decided similar should give a matrix of the same kind. zero should not do this. So I don't see how one can fall back to the other.

[rfourquet]

It's just that we decided similar should give a matrix of the same kind. zero should not do this

zero should definitely give a matrix of the same kind, when the matrix is passed as an argument. zero(x) is meant to return an additive identity for (the type of) x, so at the very least it must be of the same type as x, and in our case, have the same parent.

We need something like similar to implement -x, 2x, x+x etc. Given a matrix, we must be able to create a matrix of the same type and ring, whose entries don't matter, because we will fill up every slot. So zero looks like a good candidate as a fallback for similar.

But we indeed also need a function which chooses the best matrix given a ring R (for e.g. change_base_ring, map_coeffs etc.). The current way would be zero_matrix(R, n, m), which we could also spell as zeros(R, n, m). There is no interface for requesing unitialized entries currently (AFAICT), but I can think of matrix(R, n, m, undef) for example (which, like for similar, would fall back to zero_matrix).

[wbhart]

It looks like I misunderstood the zero you were talking about here. Indeed, zero(M) where M is a matrix will always give a matrix of the same type. And I am fine with using similar to implement -x, 2x, x+x etc.

The rest I have no opinion on just yet and look forward to figuring it out with you next week.

[wbhart]

This was all implemented, and we all seem to be happily using the functionality, so I'm closing the issue which was mainly still open for documentation purposes. It's now all documented in the docs, so no further need for the ticket.