## Week 4 Report(June 18 – 24) : Dynamic Programming

Note : If you’re viewing this on Planet SymPy and Latex looks weird, go to the WordPress site instead.

Prof. Sukumar came up with the following optimization idea :
Consider equation 10 in Chin et. al . The integral of the inner product of the gradient of $f(x)$ and ${x}_{0}$ need not be always re-calculated. This is because it might have been calculated before. Hence, the given polynomial can be broken up into a list of monomials with increasing degree. Over a certain facet, the integrals of the list of monomials can be calculated and stored for later use. Before calculation of a certain monomial we need to see if it’s gradient has  already calculated and hence available for re-use.
Then again, there’s another way to implement this idea of re-use. Given the degree of the input polynomial we know all the types of monomials which can possibly exist. For example, for max_degree = 2 the monomials are : $[1, x, y, x^2, xy, y^2]$.
All the monomial integrals over all facets can be calculated and stored in a list of lists. This would be very useful for one specific use-case, that is when there are many different polynomials with max degree less than or equal to a certain global maximum to be integrated over a given polytope.

I’m still working on implementing the first one. That’s cause the worst case time(when no or very few dictionary terms are re-used) turns out to much more expensive than the straightforward method. Maybe computing the standard deviation among monomial degrees would be a good way to understand which technique to use. Here is an example to show what I mean. If we have a monomial list : $[x^3, y^3, 3x^2y, 3xy^2]$ , then the dynamic programming technique becomes useless here since gradient of any term will have degree 2 and not belong in the list. Now, the corresponding list of degrees is : $[3, 3, 3, 3]$, and standard deviation is zero. Hence the normal technique is applicable here.

In reality, I’ll probably have to use another measure to make the judgement of dynamic vs. normal. Currently, I’m trying to fix a bug in the implementation of the first technique. After that, I’ll try out the second one.