Concerning packing arborescences (edge disjoint spanning trees), I added a
more recent paper on the page of projects proposals. It improves the time
complexity, but I don't know how difficult it is to implement. Having a
proper implementation of Gabow's algorithm would already be a nice
contribution.
David.
On Tuesday, April 5, 2022 at 11:15:09 AM UTC+2 tcscrims wrote:
> Hi Pedro,
> The exterior algebra is a subclass of the Clifford algebra (as it is a
> special case), and the problem is the basis is indexed by subsets of {1,
> ..., n}, which is a bit wasteful in terms of memory and manipulations.
> These are much more compactly written as integers with n bits. So the first
> step would be to change the implementation to use these. One of the
> fundamental principles of that project would be to make the exterior
> algebras very fast over a variety of rings in order to compute quotients
> and modules. As mentioned in the description, another related project would
> be combine the polynomial ring implementation with the exterior algebra to
> compute natively graded-commutative algebras.
>
> Best,
> Travis
>
>
> On Tuesday, April 5, 2022 at 6:05:12 PM UTC+9 [email protected] wrote:
>
>> Hello everyone,
>>
>> I'm Pedro Orlando and I am currently doing a double degree between the
>> State University of Campinas (Unicamp), Brazil and Télécom Paris, France.
>> At Unicamp I was in the last year of my BSc in Applied Mathematics, and now
>> I'm specialising in Applied Algebra and Theoretical Computer Science at
>> Télécom Paris during the double degree.
>>
>> The Applied Maths syllabus at Unicamp is quite open-ended and, as such, I
>> dedicated about half of my graduation to pure mathematics, and the other
>> half to algorithmics.
>> At Télécom, I've had, most notably, courses dedicated to the
>> implementation of graph algorithms and even an entire semester dedicated to
>> using Sage for algebraic applications, and with it I gained some experience
>> with its uses.
>>
>> Albeit never having worked with open-source per se, I'm very passionate
>> about it. In terms of experience, however, I have worked for two years as a
>> full-stack developer using Python, C++ and other languages (SQL,
>> javascript, shellscript, ...), even acting as code maintainer for a while,
>> and thus I am quite accustomed to the git workflow of big projects; I have
>> even already started getting acquainted with your development flow by
>> making a small contribution to a documentation ticket #33271
>> <https://trac.sagemath.org/ticket/33271> in Sage.
>>
>> From the ideas list, the two topics which have interested me the most
>> were:
>> - Rewrite exterior algebra and implement Gröbner bases
>> - Edge connectivity and edge disjoint spanning trees in digraphs
>>
>> The first idea is very closely related to the subjects I've studied in
>> Applied Algebra, with special mention to Gröbner bases which were often
>> used during courses (I might need a refresher though). In this topic, I'd
>> love further clarification on ticket #32369
>> <https://trac.sagemath.org/ticket/32369> for rewriting exterior algebra
>> (namely, the starting point: is the problem in the ExteriorAlgebra class in
>> algebras/clifford_algebra.py ?). This project might require me to
>> understand Cython more deeply, as well as find out how one would go about
>> implementing the bonus "ambitious" goal, but I'm up for the task of
>> learning these!
>>
>> As for the second one, I've always been very interested in graph theory
>> and their algorithms, this being one of my favourite topics, and it seems
>> to be very well documented, discussed and explained in Sage's trac, even
>> containing a paper with the related algorithm, so I'm ready to dive
>> head-first into all of the discussions relating to this project. Should
>> this be of interest to anyone, I have a small project on GitHub
>> <https://github.com/scramblerdoodle/MITRO209_densest_subgraph>
>> implementing an algorithm for an approximation to the densest subgraph
>> problem in linear time.
>>
>> Cheers and all the best,
>> Pedro
>
>
--
You received this message because you are subscribed to the Google Groups
"sage-gsoc" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-gsoc/4243aa4a-7dc1-407d-b51c-bf986e661aaen%40googlegroups.com.
