3
$\begingroup$

I am interested in the sum of a Hadamard product of generating functions.

If we are given $n$ functions, where $0 < i \leq n$, of the form:

$$f_i(x_i) = \sum_{j=0}^m{c_{i,j} x_i^j}.$$

The hadamard product is defined as:

$$g(x) = \sum_{j=0}^m{( \prod_{i=0}^n {c_{i,j}})x^j}.$$

It's essentially the same as going through all the generating functions simultaneously and multiplying all the $j$th coefficients together to obtain a new coefficient.

Some given information

I have polynomials; I think of them as finite length generating functions. I know that all of the coefficients are natural numbers. I'd like the sum of the resulting coefficients.

There's a trick. Calculating the Hadamard product generates an extremely complicated expression. I would like to avoid dealing with this expression explicitly, if possible.

I want to know ways that I could do this.

  • 0
    *What* has a finite length? The power series of a rational function does not terminate; only polynomials have terminating power series expansions.2010-10-23
  • 0
    An additional note: Differentiation and integration may prove tricky because I'm working with extremely large powers of x. Any suggestions are greatly appreciated!2010-10-23
  • 0
    I'm sorry - I have a polynomials - they're incomplete "generating functions". I'd still like to sum the (product of coefficients)2010-10-23
  • 1
    I have read through many of your questions on this project and I still have no idea what it is you want to do. What format do you have your sequences stored as? What is it about this format that makes a direct computation difficult? Why don't you switch formats?2010-10-23
  • 0
    I'm playing around with NP complete problems. I'm experimenting with numerical techniques to see if I can come up with competitive methods this way. Unfortunately, I can't seem to come up with better formats and formulations.2010-10-23
  • 0
    So specifically you have the following expression: $c_{0,0}*c_{1,0}*...*c_{n,0} \space + \space c_{0,1}*...*c_{n,1} \space + ... + \space c_{0,m} * ... * c_{n,m}$ and you would like to evaluate it with fewer than $(m+1)n$ multiplies and $m$ adds?2011-09-20
  • 0
    Don't know if this will help but, the Hadamard product of two rational functions is rational (Theorem 2.4 of "Lectures on Generating Functions" by S. K. Lando, AMS publication stml-23).2011-09-20

0 Answers 0