Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Streamline methods for direct_sum and tensor_product throughout Oscar #3059

Open
HechtiDerLachs opened this issue Nov 30, 2023 · 36 comments
Open

Streamline methods for direct_sum and tensor_product throughout Oscar #3059

HechtiDerLachs opened this issue Nov 30, 2023 · 36 comments
Labels
enhancement New feature or request

Comments

@HechtiDerLachs
Copy link
Collaborator

As discussed yesterday with @fingolfin : At the moment it is not possible to write generic code which uses functions like direct_sum, tensor_product, or even hom. The reason is that, depending on the type of the objects considered, direct_sum will sometimes just return the object and in other cases a triple (S, inj, pr) consisting of the object S, the injections of the summands inj, and the projections pr. Currently we find for direct_sum:

  • ModuleFP -> only the object
  • FPModule -> object and maps
  • Lie Algebras -> ?
  • Abelian groups -> ?

Similar things happen for tensor_product which is supposed to return a pair (P, mult_map) consisting of the object and a multiplication map. Here we find

  • ModuleFP -> only the object
  • FPModule -> only the object
  • LieAlgebras -> ?
  • Abelian groups -> ?
  • polynomial rings -> ?

I came across this again in the work on hyper complexes #3021 and @fingolfin criticized my workarounds for not being too sustainable and no issue being raised from my side. Hence here comes the issue to keep track of such developments.
@HechtiDerLachs HechtiDerLachs added the enhancement New feature or request label Nov 30, 2023
@thofma
Copy link
Collaborator

thofma commented Nov 30, 2023 •
edited
Loading

We (@simonbrandhorst and @StevellM) had similar discussions for lattices, where also direct sum, direct products and "both" exist. In the end, we did the (in my opinion) right thing by disentangling and using proper mathematical language (thofma/Hecke.jl#985). The summary is

[...] The general idea is:

Those objects have finite direct sums and finite direct products which agree, and which are called biproducts. We leave as an interface to the user the following choices:

  • construct the biproduct as a direct_sum and only get as extra output the injection maps;
  • construct the biproduct as a direct_product and only get as extra output the projection maps;
  • construct the biproduct as a biproduct and return the injection maps as well as the projection maps.

P.S.: I am not a fan of :task, as you might have guessed.

@lgoettgens
Copy link
Member

I strongly dislike :task as it makes the code intrinsically type unstable. Thus, I would like a consistent way throughout Oscar.

LieAlgebras do not have any sums or products yet. LieAlgebraModule returns only the object in both cases.

@jankoboehm
Copy link
Contributor

I agree with @thofma, @simonbrandhorst and @StevellM in what we should get mathematically.
In fact for modules (ModuleFP) this is the case, we
construct the direct_sum and get in addition the injection maps,
construct direct_product and in addition the projection maps.

@HechtiDerLachs
Copy link
Collaborator Author

In fact for modules (ModuleFP) this is the case, we construct the direct_sum and get in addition the injection maps

But in my pr, line 98, it was still necessary to call it with :task=both to get the correct output. Similar here in line 255 for tensor products.

For vector spaces over a field (FPModule provided by AA) we do not get any multiplication map whatsoever. I had to implement that manually.

@jankoboehm
Copy link
Contributor

jankoboehm commented Nov 30, 2023 •
edited
Loading

I guess since you want both the projections and injections? But that is not what I would expect and also was suggested above (and is implemented for direct_sum and direct_product, for tensor_product we only give the module, which is more along the use cases, but we could switch the default).

@fieker
Copy link
Contributor

fieker commented Nov 30, 2023 via email

@fieker
Copy link
Contributor

fieker commented Nov 30, 2023 via email

@fieker
Copy link
Contributor

fieker commented Nov 30, 2023 via email

@HechtiDerLachs
Copy link
Collaborator Author

Sorry. Then I misunderstood your point first. So in my application I should have been aiming for biproduct instead. I can also change that.

@fieker
Copy link
Contributor

fieker commented Dec 1, 2023 via email

@lgoettgens
Copy link
Member

lgoettgens commented Dec 1, 2023 •
edited
Loading

On Thu, Nov 30, 2023 at 07:39:47AM -0800, Lars Göttgens wrote: I strongly dislike :task as it makes the code intrinsically type unstable. Thus, I would like a consistent way throughout Oscar. LieAlgebras do not have any sums or products yet. LieAlgebraModule returns only the object in both cases.

Lets do a discussion thie afternoon after the meeting. I had a long reply typed, but refrained from sending. This is getting off topic and in the wrong direction.

I am on a conference currently and unfortunately (with high probability) cannot attend the meeting and/or the discussion afterwards today.
Can you guys write the results of the discussion to this thread afterwards?

@thofma
Copy link
Collaborator

thofma commented Dec 1, 2023 •
edited
Loading

We (@fieker and @HechtiDerLachs and myself) met today and converged to the following proposed solution. We will have the following functions:

  • direct_product, returns an object and projections.
  • direct_sum, returns an object and injections.
  • biproduct, returns an object, injections and projections (not sure about the order of the maps?)
  • tensor_product, returns an object and "the" map.

Everything without :task. Not sure if we want an additional method, which just returns the object though.

@lgoettgens lgoettgens mentioned this issue Dec 5, 2023
Merged
@HechtiDerLachs
Copy link
Collaborator Author

For modules I took some first steps in #3021 .

@lgoettgens
Copy link
Member

We (@fieker and @HechtiDerLachs and myself) met today and converged to the following proposed solution. We will have the following functions:

  • direct_product, returns an object and projections.
  • direct_sum, returns an object and injections.
  • biproduct, returns an object, injections and projections (not sure about the order of the maps?)
  • tensor_product, returns an object and "the" map.

Everything without :task. Not sure if we want an additional method, which just returns the object though.

This is a nice and comprehensive list of functions and return values. But what should be the input? I can find 4 currently in use:

  1. direct_product(::SomeType, ::SomeType) (e.g. direct_product(::GrpGen, ::GrpGen))
  2. direct_product(::Vararg{SomeType}) (e.g. direct_product(::ZZLatWithIsom...))
  3. direct_product(::SomeType, Vararg{SomeType}) (e.g. direct_sum(::LieAlgebraModule, ::LieAlgebraModule...))
  4. direct_product(::Vector{SomeType}) (e.g. direct_product(::Vector{TorQuadModule})

I think that we should decide on a general way which of these should be there in general, which have to be implemented for each type, and which can be implemented generically by the other ones. All of this should be the same for all 4 functions discussed in this thread.
My only opinion right now: 2 is bad style as it creates ambiguities for the empty input, instead one should define 3. If we want to allow empty sums/products, then 4 is the only possibility.

@thofma
Copy link
Collaborator

thofma commented Dec 20, 2023 •
edited
Loading

Yes, 2) should be purged. I don't think 4) alone can deal with empty products. For direct products of $K$-algebras, I had to implement something like direct_product(K, algebras::Vector), because one needs to know the $K$ to construct the zero algebra. I would guess it is the same for LieAlgebraModule? Alternatively one could do ;init = zero_algebra(K) resp. ;init = zero_module(A), although this look a bit odd.

@fieker
Copy link
Contributor

fieker commented Dec 20, 2023 via email

@StevellM
Copy link
Member

I may have put a lot of bad varargs of type 2) when I implemented the methods for things related to lattices... I could take care of changing this to 3) if that is better (whenever I have the time). In general, I would be in favour of keeping both the varargs and vector option.

@thofma
Copy link
Collaborator

thofma commented Dec 20, 2023

I think we already fixed them for lattices and related constructions.

@lgoettgens lgoettgens mentioned this issue Dec 21, 2023
Merged
4 tasks
@lgoettgens lgoettgens mentioned this issue Jan 10, 2024
Open
@thofma thofma mentioned this issue Jan 19, 2024
Open
@lgoettgens
Copy link
Member

lgoettgens commented Jan 19, 2024 •
edited
Loading

Direct sums and direct products

Tensor products haven't been discussed, but deferred to a later point.

After todays meeting, a group of 6 people (@fieker, @ThomasBreuer, @thofma, @mjrodgers, @jankoboehm and me) discussed this again with some input from #349 and came to the following conclusion (not everyone was happy, but nobody objected):

minimal interface

  • direct_product(::Vector{T}) only returns an object; it can have kwargs (e.g. coefficient_ring for modules) to construct a suitable empty product. this function may throw for an empty vector.
  • canonical_injection(obj, int) and canonical_projection(obj, int) return the embedding of / projection into the ints component
  • AbstractAlgebra._number_of_direct_product_factors(obj) (unexported): If an object has been constructed as a direct product, how many factors have been used in this construction?

The following can then be implemented generically in terms of the above:

  • × (\times) as an alias to direct_product
  • ⊕ (\oplus) as an alias to direct_sum (see below for when direct_sum exists)
  • direct_product taking (::T, ::Vararg{T}) and calling the Vector version (don't allow zero-arg version)
  • direct_product_with_injections? only returns an object and something equivalent to canonical_injections(obj)
  • direct_product_with_projections? only returns an object and something equivalent to canonical_projections(obj)
  • direct_product_with_injections_and_projections? only returns an object, something equivalent to canonical_injections(obj), and something equivalent to canonical_projections(obj)
  • canonical_injections(obj) and canonical_projections(obj) return all of them as a vector (in the default just call the singular version a bunch of times)

open questions:

  • how to deal with direct sums that are not a coproduct / category theory nonsense?
    -> just add aliases for direct_sum_* to direct_product_* for your type, if mathematically sensible

ToDo-List:

  • the generic stuff gets implemented in AbstractAlgebra
  • afterwards replace all current implementations of direct_sum, direct_product, biproduct by the interface functions above (List of types to be added here)
  • adapt similar constructions (semidirect products, wreath products) (later...)

@StevellM
Copy link
Member

StevellM commented Jan 19, 2024 •
edited
Loading

I do not think that this will be a reasonable choice (currently and in the long run): indeed by definition direct sums and products come with the maps. But then it is not clear that someone can reconstruct these maps outside the constructors, i.e. without having to remember all the process. I had to implement such functions some time ago for lattice related objects.

How does this minimal interface deal with constructions for which one cannot reconstruct the canonical_(bla) after construction ? Should we necessarily use direct_sum_with_injections or direct_product_with_projections ? Or should we remember all the details of the construction ? So in the case where one cannot reconstruct the maps afterwards, we have somehow to always store them somewhere. But what if I do not want to keep the maps ?

EDIT: extra thought. What about sub ? Should it return always an object and we make an extra function sub_with_embedding ? This will bring extra inconsistency in my opinion.

@fieker
Copy link
Contributor

fieker commented Jan 19, 2024 via email

@StevellM
Copy link
Member

Unfortunately I do not have yet an example where this is not possible, but I know for sure that we do not want to store components in the construction. Sorry for the strong word, but this seems to be a very bad design decision in my opinion. I will explain why I think it is.

First of all, we should understand: what is wrong with returning the maps ? I do not see any explanation for this: worse, it seemed that the conversation was first converging to using the maps. So why being against returning the maps, now ? It is much more convenient, it does not remove the possibility of writing a canonical_* function and it is more consistent with other Oscar functions.

Indeed, such design will bring inconsistency within Oscar: a lot of functions in group theory for instance return a subgroup with an associated (canonical?) map. Why would direct_product behave differently ? I am not against having canonical_*: if one wants it, can implement it and is able to make a use of it, good for them. But in general it is not something we should expect the user to have to deal with. I guess if an object comes naturally, by definition, with a given set of data then this should be returned. Otherwise why don't we have polynomial_ring_with_indeterminates or subgroup_with_embedding ?

The idea of "storing the components and all choices on the product" does not seem to be optimal, and I would prefer to avoid this. In my opinion, we also use Oscar for heavy and long computations. If tomorrow one runs computations where one needs to take direct products of 10 to 100 objects which will not be used anymore, but for which one needs the maps right away, should we really store everything ? Then after 1 month of computations, running the same function thousands of times on different sets of 10 to 100 elements, one would have filled up their memory, and garbage collector will not be able to do its job (if I understood correctly how GC works). One will still have gazillions of global objects remembering several distinct old objects (components) each, "just in case". We cannot rely on this.
In general, having to remember data is not good for long and expensive computations. So I could understand the argument of "use direct_product_with_*", but this does not solve the overall issue: should this still save the components to reconstruct the map later ? and why should we make a separate method where one could only use , _ or [1] to get rid of the maps in the output ?

A more flexible solution, in my opinion, would be to keep the maps in the output, and the type(s) for which one wants (or needs?) to remember the construction, then they make it part of their constructor. I do not see why we should impose a more restricted usage.

This is why it seems unreasonable to me. At the end, we will replace three characters in our code, by storing more data and imposing to the user to reconstruct the maps by hand afterwards. I am not against the canonical_* if it is useful to some people, and I agree that direct_sum, direct_product and biproduct are not perfect names. However I do not support removing the maps from the output.

@mjrodgers
Copy link
Collaborator

mjrodgers commented Jan 22, 2024 via email •
edited
Loading

@simonbrandhorst
Copy link
Collaborator

How far reaching is this decision of do not return the maps, but give canoincal_ accessors?
Will it soon apply to all other constructs? e.g. to sub objects, kernels, cokernels tensor products etc.?
From my point of view the downside is that the user has to guess the names of canonical_.

@HechtiDerLachs
Copy link
Collaborator Author

worse, it seemed that the conversation was first converging to using the maps. So why being against returning the maps, now ?

While I am personally not opposed to also allow for the liberty of storing the maps and providing getters, I do agree with this statement of @StevellM . How come make this 180 degree turnaround just one month before the release of 1.0 after more than four years of conversion towards returning the maps? At least for someone who has not participated in the last meeting this seems rather bizarre.

As for the issues raised regarding garbage collection: I do agree that there can easily be memory management issues resulting from suboptimal programming. But I believe that if the programmer is aware of this, they can be resolved, e.g. by avoiding circular referencing or even using weak keys.

What raises doubts about the non-returning of the maps might be that not all parts of Oscar have data structures which are designed to also store additional information. While I am often in favor of introducing new data types for every step in the history of the creation of an object (like DirectSumModule or HomModule) and these data structures then also come with fields to store accompanying data, there might be instances where we only have one primitive data type as the workhorse (like e.g. the actual ModuleFP family). In the latter case, one would have to go via the attributes. But not for every data structure it might be favorable/possible to support attributes? I don't know, but I'm thinking of wrapper types which make stuff from external libraries available and I'm not sure how flexible we are there.

@StevellM
Copy link
Member

Also in your example of taking direct products that are only needed for a short time, the maps will be garbage collected with the objects once they are no longer in use, correct? The maps aren't saved in some global cache, they are attached to the object.

My example might be a bit confusing, sorry about that. I do want to remember the new direct product for probably several weeks in my long run computation, but I do not want to remember the components. Maybe, at the creation, I need the maps for other purpose. So if the constructor stores the components to reconstruct the maps later, my new object will remember those old components, which will not be garbage collected (even if they are definitely useless in my program).

@fingolfin
Copy link
Member

Here is why I am no fond of direct_sum and biproduct, at least for groups:

  1. users with a group theory background won't know it
  2. direct products of (non-abelian) groups are essentially never called "direct sum"
  3. they are not biproducts either (the coproducts in the category of groups are free product)
  4. yet they admit both natural (and useful) embeddings and canonical projections

In this sense a name like direct_product_with_injections_and_projections seems to me superior -- at least for groups. Of course it is inferior in other contexts (modules...) and other ways (it's OK with tab completion and an editor configured to auto-complete Julia code, but I dread having to type that -- OK, I'd actually never do that, I'd rather grep for it and then copy&paste ;-). But my understanding is that in a context where it makes sense to refer to direct_sum and biproduct, we would still allow that?

That said, if the decision was to just always call this biproduct, then I'd be accept that, too (designing a computer algebra system spanning multiple domains always requires TONs of compromises) -- but please let's not claim it is because of category theory.

Likewise, I do not find arguments of the form "direct_product should return maps because sub and quo do" compelling. Of course they are not completely without merit. But there are arguments in the other direction, too, and in the end we do what is pragmatic, and that can differ in different use cases. (@simonbrandhorst I did not attend the meeting on Friday as I was teaching, but I don't think wider ranging changes were decided. But as a long time GAP developer of course I'd prefer if sub and quo would just return an object, not a map ;-) but I do see arguments in both directions and have no interest in trying to change anything about these).

The current "standard" is the "task" argument, which is not particular elegant or nice, but at least it works. Of course it has the downside of not being type stable, but I'd like to see the real world code using them and where type stability matters (i.e. it has a "hot loop" that isn't optimized to the call to direct_product???). The main downside to me then is that it impedes analysis of the code and thus makes it harder to find other type instabilities that actually do affect performance. So getting rid of it in some way indeed would be preferable.

Whatever we decide, we need to decide it soon, and then implement it everywhere. And no "but my code is special so I'll do it differently" exceptions anymore.

And when I say "we decide" then of course what I really mean is that unless a miracle happens and a proposal is made that makes everybody happy, then at some point (perhaps by the end of the week?), @fieker needs to hand down an edict (after hearing all voices), as I don't think it's a good idea to keep this discussion going for a longer time.

@thofma
Copy link
Collaborator

thofma commented Jan 22, 2024 •
edited
Loading

The conclusion of the discussion on Friday was that we prefer to have groups behave exactly the same as the other objects (like modules, abelian groups, things from an abelian category), which prohibits us from using the mathematical useful notions of "direct = product = automatically with projections", "direct sum = coproduct = automatically with injections". Thus we are back to square one and have direct_product_with_* etc. (this is the same as the :task interface, but without the :task.)

The idea to have only the object and recover the maps is essentially independent of this. I also think this is a rather large change from the status quo. Before this was never mandatory, but always optional.

@HechtiDerLachs
Copy link
Collaborator Author

And when I say "we decide" then of course what I really mean is that unless a miracle happens and a proposal is made that makes everybody happy, then at some point (perhaps by the end of the week?), @fieker needs to hand down an edict (after hearing all voices), as I don't think it's a good idea to keep this discussion going for a longer time.

Agreed.

@StevellM
Copy link
Member

After discussion with @simonbrandhorst and @paemurru, the minimal interface and complementary functions proposed previously are fine.

Though, it would be convenient if we allow a keyword argument for those functions, like forget_structure (which is false by default). Developers (and users?) can change the value to decide not to remember all the components for the reasons I have mentioned before. In that case, the function(s) make the output object remembers its components and "where they fit" by default, to reconstruct the maps later, but we could also decide not to do this if one cares only about the final object, or just wants to use the map temporarily.

@paemurru
Copy link
Contributor

As for the issues raised regarding garbage collection: I do agree that there can easily be memory management issues resulting from suboptimal programming.

I think this is missing the point @StevellM was trying to make.

If you allow methods such as canonical_injection, then garbage collection will not be able to free the memory that was allocated to the original objects (the direct summands), thus creating a memory leak. @StevellM was saying that he has a use case where this memory leak would likely prevent him from using such a direct sum function.

If you instead return a triple containing the direct sum object, canonical injections and canonical projections, then there is no memory leak.

@jankoboehm jankoboehm mentioned this issue Jan 25, 2024
Closed
@fieker
Copy link
Contributor

fieker commented Jan 31, 2024 •
edited by lgoettgens
Loading

I can live with this proposal (#3059 (comment)). I don't have to like it.
Please go ahead.

@lgoettgens
Copy link
Member

I will create a list of types to be adapted and ping people who know stuff once the generic stuff is available from AbstractAlgebra

@lgoettgens
Copy link
Member

The meeting just decided that this is not viable until next week.

@fingolfin
Copy link
Member

Maybe @fieker can summarize here what the decision on this was (or point to a place where it can be read) and then we put it into the description of this issue (i.e. at the top).

And then we can tackle this after the Begehung.

@fingolfin fingolfin removed the triage label Jun 12, 2024
@fieker
Copy link
Contributor

fieker commented Jun 12, 2024

the summary is in #3059 (comment)
The only thing to change would be

  • a better name for _number_of_direct_factors as this function needs to be visible and usable
  • an option, in the creation, to not store anything: in this case the maps cannot be produced afterwards
  • a function is_direct_product to test/ verify if s.th. like the interface is available

@lgoettgens lgoettgens mentioned this issue Jun 28, 2024
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement New feature or request
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
10 participants
@fingolfin @jankoboehm @mjrodgers @fieker @thofma @lgoettgens @simonbrandhorst @StevellM @HechtiDerLachs @paemurru