GSoC 2012 : Ideas : Expression Manipulation and Sparse Matrix representation

[Ashwini Oruganti]

Hi,

I am a sophomore undergraduate Computer Science and Engineering student. I've done a substantial amount of Mathematics in high school, and so far in my university (Differential Calculus, Integral Calculus, Linear Algebra, Probability Theory) and am pretty comfortable learning new concepts. My Open Source contribution so far has been a few patches in Evolution[1] [2] [3] and a few bugs (yakuake [4] , Sugarlabs [5]).

I would like to work on SymPy this summer and take it up as my GSoC project. I went through the ideas page and was thinking over the implementation of Step-by-step Expression Manipulation, and I felt it could be implemented the way we do dry runs manually, e.g. for higher order derivatives, display the result of fdiff() (i.e. 1st order derivative) at each step. This would also help avoid code-duplication in cases where SymPy works in the way we would too by hand. "show_steps" could be implemented as a separate function where, when called by the user, it could be made it operation-specific. 

And as to what the output should look like, the readability part is easy, what's tricky is the usability part. We could store each step in an object (auto-name each step as step1. step2, etc) that when called, can print the operations occurring in that step and then the user could use it as he/she finds fit.

Please do let me know your take on this, and if its feasible to implement. 

I also had a few ideas about the implementation of sparse matrix representation for Matrix, in the linear algebra module.  I think we can use a combination of both Dense & Sparse storage. We can create a list of indices that holds the zero elements and modify other Matrix operations to first see if the element is in this list, if so, then treat it as a zero, else continue as before ( and refer to the Dense storage value); probably implement this as a test_sparse() function and add it to the existing matrix operations.

It's mentioned in the wiki that this project was partially worked upon by a previous GSoC student. Given a reference, I could probably complete it further.

I would love to get more inputs on the above ideas, and discuss the same. 

Regards,

Ashwini Oruganti

[1] https://bugzilla.gnome.org/show_bug.cgi?id=593449

[2] https://bugzilla.gnome.org/show_bug.cgi?id=593444

[3] https://bugzilla.gnome.org/show_bug.cgi?id=593450

[4] https://bugs.kde.org/show_bug.cgi?id=294051

[5] http://bugs.sugarlabs.org/ticket/3362

[Aaron Meurer]

Hi.

On Sun, Mar 18, 2012 at 9:23 AM, Ashwini Oruganti
<ashwini....@gmail.com> wrote:
> Hi,
>
> I am a sophomore undergraduate Computer Science and Engineering student.
> I've done a substantial amount of Mathematics in high school, and so far in
> my university (Differential Calculus, Integral Calculus, Linear Algebra,
> Probability Theory) and am pretty comfortable learning new concepts. My Open
> Source contribution so far has been a few patches in Evolution[1] [2] [3]
> and a few bugs (yakuake [4] , Sugarlabs [5]).
>
> I would like to work on SymPy this summer and take it up as my GSoC project.
> I went through the ideas page and was thinking over the implementation of
> Step-by-step Expression Manipulation, and I felt it could be implemented the
> way we do dry runs manually, e.g. for higher order derivatives, display the
> result of fdiff() (i.e. 1st order derivative) at each step. This would also
> help avoid code-duplication in cases where SymPy works in the way we would
> too by hand. "show_steps" could be implemented as a separate function where,
> when called by the user, it could be made it operation-specific.
>
> And as to what the output should look like, the readability part is easy,
> what's tricky is the usability part. We could store each step in an object
> (auto-name each step as step1. step2, etc) that when called, can print the
> operations occurring in that step and then the user could use it as he/she
> finds fit.

Ideally, the way we store this information and the way we print it
should be completely separate code (the way we print it could just be
implemented as part of the printing system). As you said, the more
important part is to have it in a usable form. Here are a few things
to think about:

- We may want to do different degrees of steps. If I compute
diff(x*sin(x), x, x), I may want this as two first order derivatives
as you said, or I may want to break it up further and show the product
rule and rules for the derivative of x and sin(x) shown.

- Different steps may apply. For example, if you have something that
does integrals, you could compute Integral(sin(x)*exp(x), x) using
integration by parts in two different ways. Clearly the user should
be able to pick u and dv to be whatever he wants (even if it doesn't
work), but there should be smart defaults as well.

- You should be able to apply steps to an expression. This was
discussed in another thread on this mailing list about this topic.

- Printing is important. You need to have a good way to visualize
what is going on, or it will be useless.

Aaron Meurer

>
> Please do let me know your take on this, and if its feasible to implement.
>
> I also had a few ideas about the implementation of sparse matrix
> representation for Matrix, in the linear algebra module.  I think we can use
> a combination of both Dense & Sparse storage. We can create a list of
> indices that holds the zero elements and modify other Matrix operations to
> first see if the element is in this list, if so, then treat it as a zero,
> else continue as before ( and refer to the Dense storage value); probably
> implement this as a test_sparse() function and add it to the existing matrix
> operations.
> It's mentioned in the wiki that this project was partially worked upon by a
> previous GSoC student. Given a reference, I could probably complete it
> further.

The unmerged work from that project is here:
https://github.com/sympy/sympy/pulls/sherjilozair

>
> I would love to get more inputs on the above ideas, and discuss the same.
>
> Regards,
> Ashwini Oruganti
>
> [1] https://bugzilla.gnome.org/show_bug.cgi?id=593449
> [2] https://bugzilla.gnome.org/show_bug.cgi?id=593444
> [3] https://bugzilla.gnome.org/show_bug.cgi?id=593450
> [4] https://bugs.kde.org/show_bug.cgi?id=294051
> [5] http://bugs.sugarlabs.org/ticket/3362
>

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to
> sympy+un...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/sympy?hl=en.

[snkta...@gmail.com]

Hi,

What is the plan to extend this un-merged work, are we required to
implement all the dense functions in the same sense as the sparse
functions ? That'll be fun :-)

Also, in the proposal there is a point which says: "Rewrite the
Matrices module to be more like the polys module, i.e., allow Matrix
to use the polys ground types ... ", what is the type of functionality
being expected here ?

Cheers
--Sanket

[Ashwini Oruganti]

Hi,

On Mon, Mar 19, 2012 at 7:36 AM, Aaron Meurer <asme...@gmail.com> wrote:

Yes, ideally that should be the case. We could use a method that takes in this information and prints it for us.

 

 As you said, the more
important part is to have it in a usable form.  Here are a few things
to think about:

- We may want to do different degrees of steps.  If I compute
diff(x*sin(x), x, x), I may want this as two first order derivatives
as you said, or I may want to break it up further and show the product
rule and rules for the derivative of x and sin(x) shown. 

- Different steps may apply.  For example, if you have something that
does integrals, you could compute Integral(sin(x)*exp(x), x) using
integration by parts in two different ways.  Clearly the user should
be able to pick u and dv to be whatever he wants (even if it doesn't
work), but there should be smart defaults as well.

Well, for that, we could use a flag to store which function is being used to compute the answer ( in this case, e.g:  two first order derivatives or a product rule) and use this flag to determine how show_steps() (I'm temporarily naming the function as show_steps() for the sake of discussion) proceeds to generate the step-wise solution.

Also, note that if we don't be careful, many ambiguities might occur here, (e.g. taking ( f(x)/ g(x) ) as ( (f(x) . (1/g(x)) )  in case of differentiation, and hence whether to use product rule or quotient rule), when the final answer will be the same but the procedure might differ. To resolve this, we could ask the user which solution he would want to see. Or, we could just keep a smart default, as you mentioned below. 

- You should be able to apply steps to an expression. This was
discussed in another thread on this mailing list about this topic.

I'll look for the thread and see how I can implement this.

 

- Printing is important.  You need to have a good way to visualize
what is going on, or it will be useless.

Yes, I'm working on it. The problem is generalization. Same answer can be arrived at using different solutions, hence the different implementation of the print method. I think I could start with basic algebraic computations and then keep adding to it more operations, that way we could break up the issue into parts and tackle them one-by-one. Suggestions regarding which functions to implement first are welcome.

Regards,

Ashwini Oruganti

[Aaron Meurer]

On Mon, Mar 19, 2012 at 1:16 AM, Ashwini Oruganti

When you say "ask the user," how do you envision that? How will you
implement the framework so that the UI and the work itself are
sufficiently separated?

>>
>>
>> - You should be able to apply steps to an expression. This was
>> discussed in another thread on this mailing list about this topic.
>
>
> I'll look for the thread and see how I can implement this.
>
>>
>>
>> - Printing is important.  You need to have a good way to visualize
>> what is going on, or it will be useless.
>
>
> Yes, I'm working on it. The problem is generalization. Same answer can be
> arrived at using different solutions, hence the different implementation of
> the print method. I think I could start with basic algebraic computations
> and then keep adding to it more operations, that way we could break up the
> issue into parts and tackle them one-by-one. Suggestions regarding which
> functions to implement first are welcome.

You could start off with something simple, but complex should enough
so that you can see if the functionality really works.
Differentiation is perhaps a good idea. It's simple enough that you
can easily verify the answer, but complex enough that the same
expression can branch off and be done in different ways.
Differentiation also has the advantage that any rule that can be
applied will lead you to the same answer. You can compute the
derivative of x**2 by using the power rule, or by applying the product
rule to x and x, or even the product rule to 1 and x**2, for example.
Contrast this with integration, where this is not true.

The important thing is to implement a good framework for the system.
Adding new rules to the system should be easy. If it's not, then you
don't have a good framework. If it is, then you can spend a short
amount of time to add many new rules. So you should concern yourself
more with how it will be implemented rather than what specifically
will be implemented at the start (though the what is important too,
because you want to make sure you are general enough to handle all the
cases).

By the way, if you have access to a TI89, take a look at the
downloadable program from Texas Instruments called "Symbolic Math
Guide". It has a very nice framework for something along the lines of
what we're discussing here.

Aaron Meurer

[Ashwini Oruganti]

Hi, 

I have worked out a possible implementation for the framework. Here's the basic design:

I'm dividing the complete framework into 2 parts:

1. The main algorithm to work out step-wise expression manipulation
2. The User Interface

Here's a short description of how I plan to implement each of these:

1. We can design a data structure (say, DS1) that has two components : 

•   a list of ways in which the operation under  can be performed, and 
•    the algorithm to compute a step in each of the ways listed (e.g., in case of differention, this will contain (or link to) the implementation of product rule, quotient rule, fdiff(), etc )

2. The UI can implemented in the form of a few methods and a data structure (DS2) that contains (or links to) the printing mechanism for a given operation's step.

The design can work in the following manner:

1. Once an operation is performed, the UI asks the user if he wants the step-wise solution to be printed. If yes, go to Step 2, else exit the UI.
2. Determine the operation that is to be performed and map this through a method to the list in the DS1 that contains the possible ways to solve it. Return this list to the UI.
3. Ask the user which way he wants to follow to generate the step-wise solution. Store this in DS2. 
4. DS2 uses this information and sends it to DS1 to generate each step (We can design another DS3 here that stores a step - for its usability) and send the step stored in DS3 to a printing mechanism. Return control to the UI
5. Ask the user if he wants to generate the next step. If yes, repeat Step 4. If no, exit.

This is the basic design that I came up with. Please comment. 

Regards,

Ashwini Oruganti

[Sergiu Ivanov]

Hello,

On Tue, Mar 20, 2012 at 7:16 PM, Ashwini Oruganti
<ashwini....@gmail.com> wrote:
>
> The design can work in the following manner:
>
> Once an operation is performed, the UI asks the user if he wants the
> step-wise solution to be printed. If yes, go to Step 2, else exit the UI.
> Determine the operation that is to be performed and map this through a
> method to the list in the DS1 that contains the possible ways to solve it.
> Return this list to the UI.
> Ask the user which way he wants to follow to generate the step-wise
> solution. Store this in DS2.
> DS2 uses this information and sends it to DS1 to generate each step (We can
> design another DS3 here that stores a step - for its usability) and send the
> step stored in DS3 to a printing mechanism. Return control to the UI
> Ask the user if he wants to generate the next step. If yes, repeat Step 4.
> If no, exit.

You may wish to consider going a step backwards, so that the user can
explore different possibilities of transforming an expression.

Ideally, whichever route the user chooses, the *final* result should
be the same. However, the user may be interested in some
*intermediate* result, in which case choosing different ways of
transforming a formula at a certain step makes a difference.

Sergiu

[Ashwini Oruganti]

On Wed, Mar 21, 2012 at 12:10 AM, Sergiu Ivanov <unlimite...@gmail.com> wrote:

Hello,

On Tue, Mar 20, 2012 at 7:16 PM, Ashwini Oruganti
<ashwini....@gmail.com> wrote:
>
> The design can work in the following manner:
>
> Once an operation is performed, the UI asks the user if he wants the
> step-wise solution to be printed. If yes, go to Step 2, else exit the UI.
> Determine the operation that is to be performed and map this through a
> method to the list in the DS1 that contains the possible ways to solve it.
> Return this list to the UI.
> Ask the user which way he wants to follow to generate the step-wise
> solution. Store this in DS2.
> DS2 uses this information and sends it to DS1 to generate each step (We can
> design another DS3 here that stores a step - for its usability) and send the
> step stored in DS3 to a printing mechanism. Return control to the UI
> Ask the user if he wants to generate the next step. If yes, repeat Step 4.
> If no, exit.

You may wish to consider going a step backwards, so that the user can
explore different possibilities of transforming an expression.

Noted. In fact, I think we can add the possible transformations in DS1 and map to this by DS3 as per the user's choice.

 

Ideally, whichever route the user chooses, the *final* result should
be the same.  However, the user may be interested in some
*intermediate* result, in which case choosing different ways of
transforming a formula at a certain step makes a difference.

Yes, that's my topmost priority, the final result _must_ remain the same. And yes, I am planning to implement the usability of intermediate results, as mentioned, in my design. :)

Regards,

Ashwini Oruganti

[Sergiu Ivanov]

On Tue, Mar 20, 2012 at 8:53 PM, Ashwini Oruganti
<ashwini....@gmail.com> wrote:
>
> On Wed, Mar 21, 2012 at 12:10 AM, Sergiu Ivanov <unlimite...@gmail.com>
> wrote:
>>
>> You may wish to consider going a step backwards, so that the user can
>> explore different possibilities of transforming an expression.
>
> Noted. In fact, I think we can add the possible transformations in DS1 and
> map to this by DS3 as per the user's choice.

It eventually sounds like the Memento design pattern is applicable
(and that's exactly what you are saying).

>> Ideally, whichever route the user chooses, the *final* result should
>> be the same.  However, the user may be interested in some
>> *intermediate* result, in which case choosing different ways of
>> transforming a formula at a certain step makes a difference.
>>
>
> Yes, that's my topmost priority, the final result _must_ remain the same.
> And yes, I am planning to implement the usability of intermediate results,
> as mentioned, in my design. :)

Great :-) Looking forward to seeing it work; I like to tinker with
step-by-step execution :-)

Sergiu

[Ashwini Oruganti]

Thanks Sergiu. 

So, can I proceed to put all this together in a proposal and go ahead with my application? Is this good enough a proposal to work on during the summer with GSoC?

If there are any more ideas/inputs, please do put them forth, I'd be happy to discuss it further. :-)

Sergiu

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To post to this group, send email to sy...@googlegroups.com.
To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sympy?hl=en.

Also, my pull request is here [1].

Regards,

Ashwini Oruganti

 

[1] https://github.com/sympy/sympy/pull/1165

[Sergiu Ivanov]

On Fri, Mar 23, 2012 at 5:01 PM, Ashwini Oruganti
<ashwini....@gmail.com> wrote:
>
> On Wed, Mar 21, 2012 at 1:07 AM, Sergiu Ivanov <unlimite...@gmail.com>
> wrote:
>
> So, can I proceed to put all this together in a proposal and go ahead with
> my application? Is this good enough a proposal to work on during the summer
> with GSoC?

To me, it looks like it's worth starting to write the proposal. [0]
suggests that you put the draft of your proposal on the wiki, so that
people could help you with it.

However, note that I'm offering my advice to the extent of my
knowledge; to get a more official opinion you should wait for Aaron or
other project members to voice.

> If there are any more ideas/inputs, please do put them forth, I'd be happy
> to discuss it further. :-)

I think we will all be able to provide additional input once we see
the draft of the proposal. I vote for the wiki because non-mentors
will be able to contribute as well :-)

Sergiu

[0] https://github.com/sympy/sympy/wiki/GSoC-2012-Application-Template

[Aaron Meurer]

On Fri, Mar 23, 2012 at 1:24 PM, Sergiu Ivanov
<unlimite...@gmail.com> wrote:
> On Fri, Mar 23, 2012 at 5:01 PM, Ashwini Oruganti
> <ashwini....@gmail.com> wrote:
>>
>> On Wed, Mar 21, 2012 at 1:07 AM, Sergiu Ivanov <unlimite...@gmail.com>
>> wrote:
>>
>> So, can I proceed to put all this together in a proposal and go ahead with
>> my application? Is this good enough a proposal to work on during the summer
>> with GSoC?
>
> To me, it looks like it's worth starting to write the proposal.  [0]
> suggests that you put the draft of your proposal on the wiki, so that
> people could help you with it.

Yeah, go ahead and start drafting it. It will be easier to give feed
back once it is in a nice proposal form.

Aaron Meurer

>
> However, note that I'm offering my advice to the extent of my
> knowledge; to get a more official opinion you should wait for Aaron or
> other project members to voice.
>
>> If there are any more ideas/inputs, please do put them forth, I'd be happy
>> to discuss it further. :-)
>
> I think we will all be able to provide additional input once we see
> the draft of the proposal.  I vote for the wiki because non-mentors
> will be able to contribute as well :-)
>
> Sergiu
>
> [0] https://github.com/sympy/sympy/wiki/GSoC-2012-Application-Template
>

[Ashwini Oruganti]

On Tue, Mar 27, 2012 at 3:15 AM, Aaron Meurer <asme...@gmail.com> wrote:

On Fri, Mar 23, 2012 at 1:24 PM, Sergiu Ivanov
<unlimite...@gmail.com> wrote:
> On Fri, Mar 23, 2012 at 5:01 PM, Ashwini Oruganti
> <ashwini....@gmail.com> wrote:
>>
>> On Wed, Mar 21, 2012 at 1:07 AM, Sergiu Ivanov <unlimite...@gmail.com>
>> wrote:
>>
>> So, can I proceed to put all this together in a proposal and go ahead with
>> my application? Is this good enough a proposal to work on during the summer
>> with GSoC?
>
> To me, it looks like it's worth starting to write the proposal.  [0]
> suggests that you put the draft of your proposal on the wiki, so that
> people could help you with it.

Yeah, go ahead and start drafting it.  It will be easier to give feed
back once it is in a nice proposal form.

Aaron Meurer

I created a draft of my proposal at [1].

Since this is the first time I'm applying to GSoC, I'm a little confused about dividing my work into parts and making a timeline and schedule. Can someone please give me some pointers to do the same?

Please review and give feedback. 

Thanks and regards,

Ashwini Oruganti

[1] https://github.com/sympy/sympy/wiki/GSoC-2012-Application-Ashwini-Oruganti:-Step-by-Step-Expression-Manipulation