FLINT3.7.0-dev
/

_acb_poly_powsum_series_tree

Synopsis#include <flint/acb_poly.h>
void _acb_poly_powsum_series_tree(acb_ptr z, const acb_t s, const acb_t a, const acb_t q, slong n, slong len, slong prec)source

Sets {z, len} to S(s, a, q, n) using a transposed multipoint evaluation, in \tilde O(\max(n, \mathit{len})) arithmetic operations instead of O(n \cdot \mathit{len}).

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.

Guides#

Cite this page

The FLINT team, “_acb_poly_powsum_series_tree (acb_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/acb_poly/_acb_poly_powsum_series_tree.html (generated 2026-10-20).