Interests in implementation of matrix spaces over commutative semirings

[Henry Wu]

dear sage math communities:

Hi my name is Henry and is a current junior studying computational mathematics and statistics&machine learning at CMU. I found this project idea of "matrix spaces over commutative semirings" of sage math and is enthusiastic about moving forward with this project idea. 

I'm pretty familiar with python development, and am experienced in working with linear algebra and implementation of linear algebraic algorithms. I've been reading the guide and past conversations, and am currently acquainting myself with basic sagemath structures. I'm also a bit rusty on abstract algebra, and am catching up on those ends as well. 

I would love to learn more about the current state of implementation, and some suggestions on moving forward with a solid proposal. Besides basic intro to sagemath, could you kindly share some references as to the nature of the problem, some documents I should read, or some background knowledge to learn beforehand? I would greatly appreciate the opportunity to discuss this further at your convenience

Regards

Henry

[tcscrims]

Hi Henry,

   Thank you for your interest.

The short version is the matrix code is really complex and spread across multiple files, but there are many features of it that does not require all the commutative ring axioms. So the goal would be to figure out a way to refine things such that you can construct the MatrixSpace parent and matrices (with perhaps a special class) that only subtraction free operations are performed. Hence, the first thing to do is get familiar with the matrix code already in Sage and then figure out the best way to allow this input (one possibility is allowing methods to fail when they involve subtraction in a fundamental way).

Let us know if you have any additional questions.

Best,

Travis

[Henry Wu]

Hi Travis and other sage-math community members:

Thanks for your reply! I've been reading the related docs and codes, especially the matrix, matrix space, semiring codes the past few days (I see why you say it's complex now).  And I think I'm beginning to get the overall picture of the problem. I may come up with some update on that end hopefully in the next couple of days.

In the meanwhile, I notice that the GSOC application also requires some contribution to the code base, i.e. complete a PR on git etc. I've found one related to linear algebra and plan to get on with it. But how do you feel if I should prioritize on thinking about the overall proposal or contributing PR?

Regards

Henry

[tcscrims]

Hi Henry,

   I would prioritize the proposal, but doing the (hopefully small) PR should not take up a significant portion of time. Feel free to @tscrim me on the PR for a review.

Also, since you are studying computational mathematics, you might want to read again some of the other project ideas as they are more computationally focused, such as "Lie group actions on manifolds", the "Coordinate the graded commutative algebra and exterior algebra implementations and Gröbner bases" (mainly the Gröbner bases portion), or the "Zariski closures of finitely generated matrix groups" (but not limited to these). Of course, we would be happy with the matrix space project being completed, but it is more infrastructure/refactoring than about performing computations (efficiently). (In particular, representation theory is essentially translating algebraic structures into linear algebra.)

Let me know if you have any other questions.

Best,

Travis

[Henry Wu]

Hi Travis:

Thanks for your kind advice! I did spend some time studying the topics you afore mentioned, but for the moment I'd like to pursue the "commutative semiring" topic as it aligns with my interests the most currently. I'm not sure if one's allowed to put in 2 different proposals for the same organization. If permitted, I might look into the lie group on manifolds topic. 
So here's what I've accomplished in the past few days:

1. prepared the development platform (wsl on windows in my case) and set up sage locally on my machine

2. acquainted myself with more documentation and relevant codes in sage repo

3. quick review on linear algebra and abstract algebra

4. created my first PR on sage repo, though far from completion

And here's my current thinking on the project itself:

 To allow for linear algebra over commutative semirings, what we need is a new class under MatrixSpace that supports the operations, and a new matrix class in matrix. The allowed operations are limited to only matrix.mul, matrix.add, and scalar multiplications due to semiring properties. So, the outline of my project can break into 5 parts:

1. Create 2 new classes under MatrixSpace and Matrix. The valid （defined） operations are mainly mul, add, and scalar mul. My current thought on subtraction is just to raise an error when subtraction performed on known semiring.

2. Check for implementation of other properties & methods , especially those that may employ subtraction or additive inverses. e.g. "inverse" "determinant". Make sure related methods perform well under semirings, or raise errors when necessary.

3. Tropical semiring, a special class of semiring already defined in the sagemath repo, can serve as a "proof-of-concept" in early stages of the implementation and can be tested against the new classes. Other common semirings like boolean rings and NonNegativeIntegers (implemented too in sage already) can also serve as tests. 

4. Provide sagemath standard documentation on the newly implemented class. Add tests as well.

5. Possible future work: performance optimization, check for compatibility with other existing classes, etc.

This is a naive outline of the milestones/timeline for my project. Please let me know if I'm on the right track here or I'm missing significant information on some aspects.

Also, if I'm to discuss other details in my proposal, do I keep posting here on the public channel, or do I message you privately?

Regards

Henry

[tcscrims]

Hi Henry,

   Sorry for my delayed reply.

Sounds good. As I recall, GSoC allows you to submit at most 3 proposals in total. SageMath has no limit, but it probably would be best to spend your time focused on making one proposal very strong than submitting 2 weak proposal.

The project outline you have given looks very reasonable. It might also be good to find some research papers on this topic are out there and consider adding some of those constructions into your proposal. I would keep the subtraction in and let the semiring fail out if subtraction doesn't work (for example, it is partially defined for nonnegative integers).

When you're ready to share drafts of your proposals, please email me directly to discuss.

Best,

Travis