[sympy] Re: GSoC 2018: Numerical Evaluation of Linear Recurrences

[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.

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sympy@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/5d68f5e5-81a7-4ee0-a8e1-0dfc59f046eb%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[sympy] Re: GSoC 2018: Numerical Evaluation of Linear Recurrences

[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.

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sympy@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/81e6a162-2763-4842-b807-862128e63714%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[sympy] Re: GSoC 2018: Numerical Evaluation of Linear Recurrences

[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).

On Thursday, February 15, 2018 at 7:54:55 AM UTC-6, Sidhant Nagpal wrote:
>
> 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.
>

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sympy@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/9a946ec4-a781-4bec-903f-be9460ee66c7%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [sympy] Re: GSoC 2018: Numerical Evaluation of Linear Recurrences

[Jason Moore]

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

moorepants.info
+01 530-601-9791

On Mon, Feb 19, 2018 at 7:10 AM, Sidhant Nagpal 
wrote:

> *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
> ?
>
> --
> 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+unsubscr...@googlegroups.com.
> To post to this group, send email to sympy@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.
>

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sympy@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/CAP7f1AgGe6WgPWF3jLmo43y7zH%3DmM7WYKHR_0zbuVc%2BNp6e0Lg%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[sympy] Re: GSoC 2018: Numerical Evaluation of Linear Recurrences

[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 
?

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sympy@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.

[sympy] Re: GSoC 2018: Numerical Evaluation of Linear Recurrences

[Sidhant Nagpal]

*Reference to Related Topics:*
Cayley Hamilton Theorem & Evaluation of Homogeneous Linear Recurrences 

Convolution and Transformation Modules 


*Query:*
Can I start describing my project for the GSoC 2018 Proposal on SymPy Wiki 
Pages ?

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sympy@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/7702adf7-b4dc-4c45-a209-4d0ae7aefc37%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[sympy] Re: GSoC 2018: Numerical Evaluation of Linear Recurrences

[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.

On Thursday, February 15, 2018 at 7:24:55 PM UTC+5:30, Sidhant Nagpal wrote:
>
> 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.
>

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sympy@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/b38460a3-a9b3-4953-a542-6b62e121115e%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.