flintlib
[wip] divconquer summation for d-finite series
As a small step toward #1881, I have started porting to plain FLINT a
small piece of ore_algebra.analytic.
It is still very much a work in progress (important pieces are missing, and what is there is far from final) but I would already appreciate feedback on the API and code style.
A few notes on specific points:
Module name: I went for acb_holonomic as it was one of the options listed in #1881 and I thought it better to keep acb_ode available for nonlinear equations. However, acb_holonomic may be a too specific since much of the code could be extended to support linear ODEs with analytic coefficients. Maybe rename to acb_lode?
Function and parameter names: I am bad at naming things, and I changed my mind several times regarding how some things should be called. Also, while I tried to adopt FLINT's conventions, I have my own idiosyncratic habits. Suggestions welcome!
Constants: Basically all acb for now. Much of the code could later be gr-alized to other fp/ball types, and some parts to more general coefficient rings.
Data layout: The divide-and-conquer summation code stores both the solution being computed and the corresponding residual in the same buffer. This seems like a natural thing to do when I started but may make some things more complicated than necessary in the end. OTOH I suppose it might be beneficial if the implementation is later adapted to work with packed fixed-precision floating-point numbers.
Mathematical conventions: Initial conditions are specified as Taylor coefficients as opposed to derivatives (e.g., $(a₀,a₁,a₂) = (0,0,1)$, not $(f(0),f'(0),f''(0)) = (0,0,2)$, for $f(x) = x²+O(x³)$). Series involving logs are expanded in terms of $x^n \log(x)^k/k!$, both on input (for specifying initial conditions) and on output. This simplifies some formulas, but really the main reason is that these are the conventions I am used to (and it makes comparison with my existing code easier).
Note that @rburing has an implementation of more or less the same algorithm at https://gitlab.inria.fr/ricardo-thomas.buring/d-finite-fun, but
- over generic rings,
- for nonsingular first-order systems (vs regular singular equations here),
- with a focus on computing truncated series (vs evaluating the sum).