Interest in Functionalities for Krylov methods over exact fields

[Pawani Agarwal]

Hello,

I am Pawani, a 4th year student at BITS Goa pursuing a dual degree in MSc Mathematics and BE Computer Science.

I have been contributing to SageMath for sometime now and I have also created PRs (#39528 and #39472), though they haven't been reviewed. This has given me a bit of familiarity with the codebase and I am also exploring deeper into it.

For this project I have already started reading up on the fundamental concepts, including minimal polynomials, Krylov subspaces, and their applications in kernel and co-kernel computations over K[x] modules.  

I am very excited about this project and would love to contribute actively. Please let me know if there are any other specific directions or initial tasks I should focus on. Looking forward to your guidance!  

Best regards,  
Pawani Agarwal

The information contained in this electronic communication is intended solely for the individual(s) or entity to which it is addressed. It may contain proprietary, confidential and/or legally privileged information. Any review, retransmission, dissemination, printing, copying or other use of, or taking any action in reliance on the contents of this information by person(s) or entities other than the intended recipient is strictly prohibited and may be unlawful. If you have received this communication in error, please notify us by responding to this email or telephone and immediately and permanently delete all copies of this message and any attachments from your system(s). The contents of this message do not necessarily represent the views or policies of BITS Pilani.

[Yujin Zhao]

Hello, 

My name is Yujin Zhao, studying BSc Mathematics in University College London for 2nd year.

It is my first time to contribute open-souce code. But I have done two coding projects in school, which are Well-Formed-Formulas and Prisoners Dilemma, attacked with this email.

My schedule and plan are in the personal statement, please have a read.

I am happy to start my first step as a code contributer here. Please let me know if you need more details and information, thanks.

Best wishes,

Yujin Zhao

[Nicholas Bell]

Hello,

I'm Nicholas, currently in my 1st year pursuing a Master of Computer Science at Sorbonne Université. I'm new to contributing to SageMath but have a little prior experience in open source contribution (development of a small plugin for RuneLite). I also have 1.5 years professional experience in mainly backend web development. I have a keen interest in mathematics, having obtained my BSc with a double major in mathematics and computer science. Recently I've tried my hand at a bugfix for SageMath (#39774), which has not yet been reviewed, but has given me some familiarity with the structure of the codebase, as well as the standards required for contribution.

My current master's project involves the use of minimal polynomials to perform an attack on classic Oil and Vinegar signature schemes, so I have some recent experience working with these. Specifically in preparation for this project, I've done some reading on Krylov subspaces, Wiedemann's algorithm for finding the characteristic polynomial of a sparse matrix, and Keller-Gehrig's algorithm for dense matrices.

I would be thrilled at the opportunity to contribute to SageMath in a way both meaningful to the codebase and relevant to my studies.

Thanks for your consideration,
Nicholas Bell

[Vincent Neiger]

Dear Pawani Agarwal,

Thank you for your interest in this project. Thank you also for your first contributions to Sagemath. Recall the short description gives ideas for the project and you, the potential contributor, are expected to turn the ideas into a detailed proposal.

Best regards,

Vincent Neiger

[Vincent Neiger]

Dear Yujin Zhao,

Thank you for your interest in this project. If you have not done this already, it would be valuable for your application that you show some familiarity with SageMath, e.g. by submitting one (or a few) pull requests that solve easy issues; if possible somehow related to this project you are interested in. Here are some notes that can help to improve the proposal. The project you propose is not much more detailed than the one already proposed (some generic steps are added, like testing/documentation/reading/...) and at the same time some of the few added things seem too ambitious for a 12-week project (parallelisation?). The timeline is too compartmentalized: e.g. a whole part is dedicated to tests/documentation whereas tests will need to be carried out all along.

Best regards,

Vincent Neiger

[Vincent Neiger]

Dear Nicholas Bell,
Thank you for your interest in this project. Thank you also for your first contributions to Sagemath. I see that your PR concerned a tricky technical modification, and is currently discussed in the corresponding issue; if time permits, it would be valuable for your submission to make another PR tackling some simpler issue that would also ideally be connected to this project. Recall that the short description gives an idea for the project, and the next step is that you, the potential contributor, are expected to turn this idea into a full, detailed proposal.
Best regards,
Vincent Neiger

[Pawani Agarwal]

Hello Vincent,

I have sent you my proposal directly though I am not sure if you have received it. Please do let me know if it will be possible for you to provide a feedback and also if I need to send my proposal here.

[Vincent Neiger]

Dear Pawani Agarwal,

I have quickly reviewed your proposal --- please note that I might not have time to do it again before deadline. It is well organized and complete, yet on the core of the project, a large part of the detailed project (basically all of Task 1) concerns things that are unrelated to exact fields. The suggested idea of project was about exact computations (e.g. over finite fields, over the rationals, ...). It is absolutely fine if you propose another project, but I think you should then stick to it and define it clearly. For the moment, your project mixes both aspects and it makes it both difficult to understand and too ambitious for 3 months. Your Task 2 is vague on what problems/algorithms it will tackle: what are "block Krylov sequences for a structured subspace", and what "structured matrix-vector products" do you have in mind? Your Task 3 seems to target a method indeed relevant for the exact case (unlike Task 1).

Best regards,

    Vincent Neiger

[Pawani Agarwal]

Hello Vincent,

Thank you for the feedback. Sorry I didn't take into account exact fields while writing about Task-1, but I am also a bit confused since I am also exploring Krylov subspaces for the first time only. When I searched to do so for exact fields, what I understood was that after building up the block-krylov subspace I could use rank-revealing decompositions such as QR/SVD modified for exact linear algebra to extract kernel or we could first orthogonalise it using projections and then use QR to extract kernel. Other method was directly solving the system Av=0. I did see that Arnoldi and other methods are used generally though not sure about exact linear algebra.

One more I can think of that after finding the characteristic polynomial using Keller-Gehrig's algorithm, I can from there find kernel, cokernel and the invariant factors. Though I will admit I am not sure about this.

Can you please just check if I am thinking I am in the right direction. If yes, I will incorporate this into my proposal.