Simplify a summation to reduce computation time I am working on an optimization problem in which the following summation should be calculated in a computer program over a billion times. Therefore, I am looking for the possibility of somewhat simplifying this summation to reduce the computation time:
$$
    \sum_{n=1}^{m} a_n*e^{-b*n}
$$
where $a_n$ are known values and $b$ is a constant.
I found the following equation that may help my problem
$$
    \sum_{n=1}^{m} e^{-b*n} = \frac{1-e^{-b*m}}{e^b-1}
$$
 A: The expression is probably most efficiently treated as a polynomial in $e^{-b}$:
$$ \sum_{n=0}^m a_n e^{-bn} = f(e^{-b}) $$
where $f$ is the polynomial of degree (at most) $m$:
$$ f(x) = \sum_{n=0}^m a_n x^n $$
Commonly polynomials are evaluated by Horner's scheme.  Special polynomials admit faster evaluation by use of rational expressions, such as the case you mention of all coefficients $a_n=1$ (finite geometric series).
It's unclear whether the $a_n$ coefficients will be changing or static across the billion times you propose to evaluate the expression.  If they are static, some optimization of the evaluation scheme beyond Horner's scheme is likely to be possible, but this would involve preprocessing of the coefficients.  If they are changing from evaluation to evaluation ("experimental data"), then preprocessing will not be advantageous.
See also the previous MathOverflow Question, Fast evaluation of polynomials.

The arithmetic complexity of polynomial evaluation poses some difficult problems, in particular a tradeoff between faster operations and reliable precision.
In a 2010 report by G. Reynolds, Investigation of different methods of fast polynomial
evaluation, which as here deals largely with univariate polynomials, the author concludes:

This report finds that in terms of both performance and precision, the serial Horner’s form is the optimum polynomial evaluation method.

In that context the comparison was made to Estrin's scheme for polynomial evaluation.  Where Horner's scheme imposes a "pipeline" of multiply-and-add operations, Estrin's scheme affords parallel evaluation of a number of subexpressions.  Since GPU's are now widely considered as general purpose computing resources, such an approach may be helpful in obtaining speed-up factors by parallel computation, especially where the degree $m$ is fixed and some effort may be given to optimizing how the evaluation tree is mapped to specific floating-point units.
Nonetheless Reynolds finds it difficult to balance the computing load on a given number of processors, and this detracts from the benefit of Estrin's scheme.  Moreover the numerical precision was found to suffer when evaluating with high parallelism.
Perhaps a reasonable middle way is to simply evaluate the even and odd portions of a polynomial in parallel, exercising two processing units:
$$ f(x) = g(x^2) + x*h(x^2) $$
and using a single multiply-and-add to recombine those subexpressions.  Something of this sort is what Reynolds calls "Brute Force -- Optimized", and he reports good numerical precision with this.
Now let's consider what possible gain there can be in preprocessing the polynomial coefficients to produce a custom optimized scheme.  A nice lecture note by Jeff Erickson (2003) sets the stage:
(1) If we limit ourselves to evaluating with multiplies and adds/subtracts, then $m$ additions/subtractions are required to evaluate a general $m$ degree polynomial (with $m+1$ terms).  Ostrowski(1954)
(2) If no preprocessing is allowed, then the number $m$ of multiplies (achieved by Horner's scheme) is also optimal.  Pan(1966)
(3) If preprocessing is allowed, then a scheme can be found to evaluate an $m$ degree polynomial using at most $\lfloor m/2 \rfloor + 2$ multiplies and $m$ additions.  The interested Reader is referred to Knuth's ACP vol. II Seminumerical Algorithms, Sec. 4.6.4 (and esp. Thm. E) for details.
If we expect to improve upon this, one possibility is to employ rational expressions, i.e. to allow divisions as well in an evaluation scheme.  The special case of a finite geometric series:
$$ \sum_{n=0}^m x^n = \frac{x^{m+1} - 1}{x-1} $$
has already been noted.  Here continued fractions play an analogous role for rational expressions to what Horner's scheme plays for polynomials.
When a search for a compact rational expression is combined with hard requirements for numerical precision, the "preprocessing" problem begins to take on the outlines of approximating the polynomial by a rational function, rather than a problem of exact symbolic equivalence.  If the polynomial is to be evaluated several hundred times for varying $x=e^{-b}$ in some bounded interval (perhaps $x \in (0,1]$, as would be the case if $b\gt 0$), then it might make sense to compute a best rational approximation (Padé approximant) using perhaps the equivalent of a few dozen polynomial evaluations to get double precision accuracy in approximation.  Indeed if only the results of polynomial evaluations are known (and not the coefficients), then the Remez algorithm might be attractive.
Thinking of this as an approximation problem, rather than an exact symbolic equivalence, is reinforced by the origins of coefficients $a_n$ as "experimental data", with the consequent errors of measurement.  If we are fitting a model to experimental data, then the "black box" that produces approximations need not be overly restricted in its operations, provided they are smooth and robust.
