_acb_poly_powsum_series_tree

With $L_k = \log(a+k)$, $w_k = q^k (a+k)^{-s}$ and $b_k = c - L_k$ for a suitable centre $c$, we have $\sum_k w_k e^{-L_k t} = e^{-ct} \sum_j p_j t^j / j!$, where the weighted power sums $p_j = \sum_k w_k b_k^j$ are the coefficients of the rational function $\sum_k w_k / (1 - b_k t) = P(t)/Q(t)$. The numerator and denominator are computed with a subproduct tree whose nodes are truncated to length len, followed by one power series division. When $n$, len and prec are all $\Theta(m)$, this costs $\tilde O(m^2)$ bit operations instead of $O(m^3)$.

The algorithm is numerically unstable, so the working precision is increased by the number of guard bits returned by _acb_poly_powsum_series_tree_guard_bits, which is chosen so that the output radii are comparable to those of the naive algorithm. The computation is done at the midpoints of $s$, $a$ and $q$, and the error propagated from inexact input is bounded separately term by term. It requires $\operatorname{Re}(a) > 0$ and $q$ bounded away from zero, and otherwise falls back to the naive algorithm. The tree is evaluated in parallel when flint_get_num_threads() is greater than one.

@misc{flint-doc-acb-poly-acb-poly-powsum-series-tree,
  author       = {{The FLINT team}},
  title        = {{\_acb\_poly\_powsum\_series\_tree (acb\_poly.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/acb_poly/_acb_poly_powsum_series_tree.html},
  note         = {Generated 2026-11-02}
}