GSoC 2018 Report Sidhant Nagpal: Discrete Transforms, Convolutions & Recurrences
This wiki page summarises the work I have done during GSoC 2018 for SymPy. The links to PRs are in chronological order under each header. For following the progress made during GSoC, see my blog for the weekly posts.
My name is Sidhant Nagpal and I have completed my third year of Bachelor's in Computer Science from University of Delhi at Netaji Subhas Institute of Technology.
My project involved writing a new discrete
module in SymPy to implement transforms & convolutions for finite sequences and add capabilities for recurrence evaluation. For further information, my proposal for the project can be referred.
I have implemented all that was planned plus a few additional things (discovering and fixing bugs). However, there is certainly room for improvement, and I will mention where the work could continue post GSoC.
-
sympy/sympy#14725: Add discrete module, and transforms sub-module including Fast Fourier Transform, Number Theoretic Transform, and include docstring, doctests, unit-tests.
-
sympy/sympy#14745: Add convolution sub-module including
convolution_fft
,convolution_ntt
and a general methodconvolution
for identifying the type of convolution and handling the cyclic convolution case, and include docstring, doctests, unit-tests. -
sympy/sympy#14765: Implement Walsh Hadamard Transform and include doctests, unit-tests, docstring for the same.
-
sympy/sympy#14783: Implement
convolution_fwht
and add support for keyworddyadic
in the generalconvolution
method, and include docstring, doctests, unit-tests. -
sympy/sympy#14816: Add a method
linrec
which allows evaluation of linear recurrences without obtaining closed form expressions, and include tests for the same. -
sympy/sympy#14853: Implement Möbius Transform using Yate's Dynamic Programming method while having
subset
keyword for flexibility of the implementation, and include docstring, doctests, unit-tests. -
sympy/sympy#14878: Implement subset convolution and include docstring, doctests, unit-tests.
-
sympy/sympy#14928: Add covering product in convolutions sub-module and include docstring, doctests, unit-tests.
-
sympy/sympy#14954: Add intersecting product in convolutions sub-module and include docstring, doctests, unit-tests.
-
sympy/sympy#14969: Improve Sphinx docs for SymPy, use plural module names -
convolutions
andrecurrences
, refine the documentation fordiscrete
module. -
sympy/sympy#14994: Add reStructuredText file for
discrete
module for inclusion in Sphinx docs, which can be referred here. -
sympy/sympy#15025: Refine
discrete
module to fix tests using floats instead of Rationals, adding warning about sequence size forfft
and other improvements.
-
sympy/sympy#14712: Add
.rewrite(exp)
capability for instances ofPow
and fix bugs insolvers
module. -
sympy/sympy#14907: Fix exception handling for factorial modulo and refine the signature for general
convolution
method. -
sympy/sympy-bot#18: Fix the issue of incorrect links being referred in wiki by explicitly specifying the links instead of using relative paths.
-
Adding a user-facing public method that internally calls
discrete.recurrences.linrec
and possibly extending it for different types of recurrences as well. -
Making methods
fft
andconvolution_fft
efficient for both symbolic and numeric variants, as some discussion and benchmarking has been done for it and there is some work done by Colin for implementing aComplexFloat
class in sympy/sympy#12192 which would be very helpful for the same.
This summer has been a great learning experience and has helped me get a good exposure of test-driven development. I plan to actively review the work that has went into this project and continue contributing to SymPy. I am grateful to my mentors, Kalevi and Aaron for reviewing my work, giving me valuable suggestions, and being readily available for discussions.