6
$\begingroup$

Given a function $\sum_{i=-N}^N{c_i x^i}$:

$f(x) \equiv \sum_{i=-N}^N{c_i x^i}$ where $c_i$ is an integer; $0 \le c_i \le a$ for some $a$.

The constant $c_0$ is desired, and we start with only $f(x)$ and $N$. $N$ is $\Theta(2^{b})$ for some $b$.

Can you clarify?

First, we start with a closed form of a function. The function itself is similar to a generating function, so that the function description is usually more concise than a list of all of its coefficients, yet it describes all of the coefficients. Some examples are

$\frac{1-x^{100}}{1-x} = 1 + x + x^2 + ... + x^{99}$

$\frac{ 1 - (n+1)x^n + nx^{n+1} }{ (x-1)^2 } = 1 + 2x + 3x^2 + ... + (n+1)x^n$

The problem seems to be that this coefficient is in the middle of a list of positive and negative coefficients. In the two examples above, the coefficient c_0 can be easily extracted. However, this is not so when there are negative coefficients. For example, take the functions above and divide by x^m to get a function that contains some negative coefficients.

What is known about the general form of $f(x)$?

The function $f(x)$ is a rational function:

$f(x) = P(x)/Q(x)$

where $P(x)$ and $Q(x)$ are polynomials.

Here's a little insight into how $f(x)$ is calculated. I use a standard rational function:

$g(x) = (x^s(x^t-1)) / ((x-1)(x^u+1))$

I then multiply $g(x)$ by $g(y)$, and $g(y)$ is of the same form of $g(x)$, but in another variable. I then possibly subtract this from a function of one coefficients:

$h(xy) = (1-(x y)^v) / (1-x y)$

I then use another variable function similar to $g(x)$, say $g(z)$, and multiply again. Possibly subtract again. Repeat this until the function I want is constructed. Then reassign variables like so (to either positive or negative exponents):

$y \mapsto \displaystyle x^{\pm 2^N}$

$z \mapsto \displaystyle (x^{\pm 2^N})*(x^{\pm 2^N})$

and so on. This is how the function is created, without going into detail.

How fast can this computation be performed?

So far, I've seen that Bruno Salvy's webpage hosts a "gfun" package that solves this in O(N).

I'm attempting to write a more efficient algorithm than this, so I'm hoping that it's possible to do better. I imagine that a bounds related to the length of the function description may be possible...

$\endgroup$
  • $\begingroup$ Are all $c_i$ apart from $c_0$ known? The question is unclear. $\endgroup$ – Dave Clarke Sep 28 '10 at 19:57
  • $\begingroup$ they are unknown - we have only a function like \frac{1-x^{10}}{1-x} - in which case f(x) \equiv 1 + x + x^2 + ... x^9 $\endgroup$ – Matt Groff Sep 28 '10 at 20:08
  • $\begingroup$ How is the problem read in? Do you not need to read in c_1 ... c_n, which already takes linear time? $\endgroup$ – Lev Reyzin Sep 28 '10 at 20:12
  • $\begingroup$ We read in the function. We DO NOT have the representation of c_{-N}...c_N. We have a function that is probably smaller in total size. Again, \frac{1-x^{M}}{1-x} is a function that gives a total of M c_i's that are all 1. However, it is possibly smaller than O(M). The size of the function can be assumed to be O(l), where l represents the length of the function description, and usually l<N. $\endgroup$ – Matt Groff Sep 28 '10 at 20:20
  • $\begingroup$ Matt, it's a good idea to improve your question to reflect these comments. Also, there's no need to write the function both in ASCII and in latex. $\endgroup$ – Dave Clarke Sep 28 '10 at 20:24
4
$\begingroup$

So far, I've seen that Bruno Salvy's webpage hosts a "gfun" package that solves this in O(N). I'm attempting to write a more efficient algorithm than this, so I'm hoping that it's possible to do better. I imagine that a bounds related to the length of the function description may be possible...

There are different measures of polynomial sparseness in the literature and you haven't been very clear on which one you might mean. However, your optimism is likely not well founded.

Take (x-2) / x^32. It's almost maximally sparse by any reasonable measure, but the coefficients in its Laurent series grow exponentially fast. If multiplication is unit cost you can still use the binary exponentiation method to keep up with the exponential growth in sublinear time in the total degree of the series, but the example suggests that things aren't rosy. This is an area littered with hardness results for division and related problems, at least in realistic models of computation where multiplication isn't constant time.

Jacques Carette is an expert in this area, so let's hope he posts a definitive answer.

$\endgroup$
  • $\begingroup$ I was lucky enough to have Jacques Carette personally email me and suggest reading up on Bruno Salvy and implement using "gfun". However, I forgot to ask him if the results were known to be optimal - but it sounds like I can safely assume that they are indeed optimal. Thanks so much for the mention! As for the polynomial sparseness, I'll try to come up with a better description in the question. $\endgroup$ – Matt Groff Sep 29 '10 at 3:02
  • $\begingroup$ @Matt: Regarding sparseness, one measure which is natural for computer science but perhaps less so for mathematics is "straight-line complexity", which is the size of a straight-line program to generate the polynomial in terms of the addition and multiplication by constants and indeterminates. $\endgroup$ – Per Vognsen Sep 29 '10 at 3:15
2
$\begingroup$

The extended comments after the question indicate that $f$ is a "black box", $N$ is known, and the coefficients $c_i$ are all integers. If in addition we have a bound on the sizes of the coefficients, say $|c_i| \le q$ for all $i$, then all $2N+1$ coefficients can be read off the value of

$$(2q+1)^N f(2q+1) = c_{-N} + c_{1-N}(2q+1) + \cdots + c_0(2q+1)^N + \cdots + c_N(2q+1)^{2N}$$

by looking at its base-$2q+1$ expansion. The middle term, $c_0$, can then be computed in $O(1)$ time. This old trick might be impracticable if $q$ or $N$ are at all sizable but perhaps it will inspire some practical $o(N)$ solutions.

$\endgroup$
  • $\begingroup$ We do have a bound on the coefficients. N is known to be quite large, but there may be a workaround... As for q, I believe it is much smaller. I'm giving this more thought... $\endgroup$ – Matt Groff Sep 30 '10 at 17:04
  • $\begingroup$ @Matt: Based on your updated description, why don't you compute $x^N f(x)$ in base $2q+1$ throughout? You can even carry them out modulo $(2q+1)^{N+1}$. $\endgroup$ – whuber Oct 1 '10 at 16:17
  • $\begingroup$ That sounds interesting... I'm considering it. $\endgroup$ – Matt Groff Oct 1 '10 at 19:02
1
$\begingroup$

Warning: I haven't used complex analysis much so this answer may be wrong.

Suppose you can write $Q(x) = x^c \bar Q(x)$ where $\bar Q(x)$ is a polynomial that's non-zero at 0 and $c$ is a non-negative integer. It follows that the "residue" you're looking for is the $c^{th}$ term in the power series for $P(x)$ divided by $\bar Q(0)$. If $Q$ is written in a form that allows easy factorization (e.g. as a product of small polynomials) you can determine $c$ and $\bar Q(0)$ easily without expanding them. Computing the $c^{th}$ term in the power series of $P$ can be done relatively quickly if $c$ is small.

Another possibly helpful tool is that the $i^{th}$ derivative of a polynomial evaluated at zero is precisely the $i^{th}$ coefficient times $i!$. It may be that $P$ or $Q$ are easier to differentiate (symbolically) than expand.

$\endgroup$
  • $\begingroup$ I believe that we can easily obtain the factorization of $Q$, even though the polynomials will possibly be large. Computing the power series $P$ may be worthwhile. As for the derivative, I've found the function difficult to differentiate. $\endgroup$ – Matt Groff Sep 30 '10 at 17:09
  • $\begingroup$ If you're going to be using residues, first you have to divide P(z)/Q(z) by z, because the residue is the coefficient of the -1 power. Unless P is a multiple of z, you don't even have to consider it: the residue of P/(zQ) at zero equals P(0) times the residue of 1/(zQ). After taking out any common power of z from P and Q, you may as well assume Q(z) = z^k(1 + q_1 z + ...). Thus you're looking for the k-1st coefficient of the last term. But note (once again) that P/Q cannot be expressed as a finite Laurent series (i.e., N is infinite). $\endgroup$ – whuber Sep 30 '10 at 18:44
0
$\begingroup$

I am not allowed to comment yet, so sorry for posting this in an answer. If someone can move it, please do so.

I have some questions:

1) What does gfun do for $N=\infty$? Do you want to find residues of functions like that?

2) Do you need a precise expression? There are approaches that give you reasonable asymptotics, for example Cauchy's integral formula together with the saddle-point method. I don't know how efficiently the involved integrals can be calculated, though.

$\endgroup$
  • $\begingroup$ I'm really concerned with finite functions. I don't need a precise expression, I'm just interested in the possibility of something faster than O(n) $\endgroup$ – Matt Groff Sep 28 '10 at 22:14
0
$\begingroup$

I'm providing a second answer because a later edit of the question has changed it considerably and this thought will not fit into the space of just one or two comments.

Because $g$ is described as a rational function, both $s$ and $u$ must be positive integers. Notice that

$$g(x) = x^s(x^t-1)/((x-1)(x^u+1))$$

$$= x^s \left(1 + x + \cdots + x^{t-1} \right) \left(1 - x^u + x^{2u} + \cdots + (-1)^j x^{j u} \cdots \right).$$

(If I misinterpreted the definition of $g$, which was ambiguously parenthesized, the analysis only gets simpler because we multiply, rather than divide, by $1 + x^u$.)

When multiplied out, this becomes a Taylor series expanded around $x = 0$ with lowest term $x^s$. Similarly,

$$h(xy) = (1-(x y)^v)/(1-x y) = 1 + x y + (x y)^2 + \cdots + (x y)^{v-1}$$

is a Taylor series (actually, a polynomial) with lowest term 1. Therefore any series of multiplications, subtractions, and substitutions of positive powers of $x$ for $y$ will produce a Taylor series: there will be no negative powers of $x$ in the result.

All you have to do, then, is track the constant term by performing all calculations modulo $x$ as you go. Not only does this greatly simplify the computation of $f$, it gives you the constant term $c_0$ immediately.

$\endgroup$
  • $\begingroup$ Did you consider the subtraction and variable reassignment? You're correct that the functions initially start with all positive coefficients, but then I reassign variables. My description may contain an error, because the actual process is more complicated, but I end up with coefficients for both positive and negative powers, I can assure you. $\endgroup$ – Matt Groff Sep 30 '10 at 21:38
  • $\begingroup$ @Matt: Yes. The variable reassignments only increase the powers of x; the subtraction (like addition) cannot create new powers. The sign of the coefficients is immaterial; what matters are the signs of the exponents. As far as I can see, you have no negative exponents. You must be doing something in addition to the operations you describe if you are winding up with negative exponents. But how do you know that? $\endgroup$ – whuber Sep 30 '10 at 22:10
  • $\begingroup$ I'm Very sorry. I copied my variable reassignments incorrectly. The variables are possibly reassigned to negative exponents. The method I use requires them, and I don't know a workaround. $\endgroup$ – Matt Groff Sep 30 '10 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.