GSoC 2018: Numerical Evaluation of Linear Recurrences

[Sidhant Nagpal]

Hi, I am Sidhant Nagpal, a second year undergraduate student pursuing a degree in Computer Engineering at Netaji Subhas Institute of Technology, India. 

I will be a GSoC applicant this year. 

I would like to propose an idea for SymPy - "Numerical Evaluation of Linear Homogeneous Recurrences with constant coefficients" that I wish to work on.

As it is difficult to obtain closed form expressions of these type of recurrences for higher order (k), 

support can be added to evaluate them for arbitrary values of n (possibly in a field).

For example: consider recurrence of order k=1000,

f(n) = f(n-999) + f(n-1000), for large n, with given initial conditions f(i) for i < 999.

I would love some feedback for the same. 

I am relatively new to SymPy, but am familiarising myself with it actively.

I have a strong Mathematics and Competitive Programming Background (in C++ and Python). 

Here is my LinkedIn Profile.

Thanks.

[Sidhant Nagpal]

Additional Note:     

Implementing this would require knowledge of Number Theoretic Transform to solve it optimally in O(k*lg(k)*lg(k) + k*lg(k)*lg(n)) for prime fields.     

Although there is a simpler sub-optimal solution which can solve this in O(k*k*lg(n)).     

Generalising for other fields will be more involved though.    

[Sidhant Nagpal]

References to Topics:

Cayley Hamilton Theorem & Evaluation of Homgeneous Linear Recurrences

Convolution & Transformation Modules

Query:

Can I start describing my project details on GSoC 2018 Proposal Page - SymPy Wiki?

[Jason Moore]

Yes, you can create a wiki page for your proposal and start writing the proposal there.

moorepants.info
+01 530-601-9791

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscribe@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/ec064e2e-b20f-4e5b-9304-f2c5b9ada771%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Chris Smith]

Interesting that you should mention this. See the recent thread here where I ask if there is a better way to compute such things (at least to a novice it appears that we are talking about the same thing).

[Sidhant Nagpal]

Interesting that you should mention this. See the recent thread here where I ask if there is a better way to compute such things (at least to a novice it appears that we are talking about the same thing).

Yes, indeed it is related. 

In fact the thread you mentioned, actually just explicitly defines the recurrence by giving the rational generating function (=Q(x)/P(x)) of the sequence. This can be calculated using the approach, that I have proposed. 

Just expand the denominator to be of the form P(x) = 1 - a1x - a2x^2 - ..., where coefficients of powers of x encode the coefficients of the recurrence and powers define the dependent term of the recurrence, Q(x) obviously encodes the initial values of the recurrence, and hence it converts to this problem.

[Sidhant Nagpal]

I have started a [wiki page](https://github.com/sidhantnagpal/gsoc/wiki/GSoC-2018-Application-Sidhant-Nagpal:-Transforms,-Convolution-&-Linear-Recurrence-Evaluation) describing the details of my project. It would be great if I can get feedback for the same.

Thanks.