Acb theta v2

[j-kieffer]

This is a thorough rewrite of the acb_theta module.

The major changes are the following:

• introduce context structures in the context of summation algorithms and rewrote the main worker function. This is to allow the next item, and to prevent NaNs when inverting complex numbers at very low precisions.
• compute exponentials, ellipsoid centers, etc. only once when computing low-precision approximation for the duplication formulas. This should improve performances slightly and decrease the threshold between acb_theta_all and acb_modular_theta.
• support several vectors z in the quasi-linear algorithms, using the simplest possible duplication formulas for each of them. This should drastically improve the efficiency of the "dimension-lowering" strategy.
• simplify the management of error bounds by assuming the inputs to be exact and reduced in key internal functions.
• in the g=1 case, rely on acb_modular_theta_sum instead of acb_modular_theta. This is to allow acb_modular_theta to possibly point to acb_theta_all in the future.
• make an automatic choice of algorithms in the main user functions between summation and duplication.
• remove some macros, make some internal functions static in the C files, and write a separate header acb_theta_types.h to lighten the user interface a bit.
• update documentation.

I mark this as a draft pull request because there are still some todos during the coming week, including:

• profile the code to make the best possible choices and acb_theta_ql_nb_steps and demonstrate performance gains compared to the previous version.
• implement the fact that odd theta constants are known to be zero in acb_theta_ql_setup.
• change some function names that don't match their section (acb_theta_sum_bounds, acb_theta_agm_distances,...)
• check code coverage and valgrind.
• use acb_theta_sum_bounds to avoid NaN results only in acb_theta_all and acb_theta_00.
• possibly use quasi-linear algorithms in acb_theta_00 and acb_theta_jet_00 as well.
• look at commits that happened on all files since the last workshop and implement them on the new files.
• get feedback from workshop participants.

[albinahlback]

Cool, I'm looking forward to next week!

[fredrik-johansson]

I guess you've seen from the CI that the complex_plot example program needs updating.

In fact, is it worth breaking the existing interface of acb_theta_all? I think this function has already been wrapped outside of FLINT. Maybe create a new function with the extra nb parameter and make acb_theta_all a wrapper for that?

[j-kieffer]

I guess you've seen from the CI that the complex_plot example program needs updating.

In fact, is it worth breaking the existing interface of acb_theta_all? I think this function has already been wrapped outside of FLINT. Maybe create a new function with the extra nb parameter and make acb_theta_all a wrapper for that?

My current idea would be to indeed break the interface, even if it's already been wrapped once or twice. (If we make a simpler user-facing function with less arguments, then I would also drop the argument sqr from acb_theta_all, which would also break things, or even merge it with acb_theta_jet_all.) Unless you think breaking the interface is too much trouble?

[edgarcosta]

The wrapper in python-fint could be easily adapted: https://github.com/flintlib/python-flint/blob/main/src/flint/types/acb_theta.pyx

[j-kieffer]

All right, I'm marking the PR as ready for review ! I finished implementing the todos from my first message (except that acb_theta_types.h doesn't exist anymore.) Additionally, I have rewritten a fair number of functions to reduce code duplication to a minimum. Note that there are 1.2k lines less now than in the current acb_theta module in FLINT, while the running time of the example program in the documentation (g=2, prec=10000) was reduced from .1s to 7-8ms.

[albinahlback]

Hello Jean, and sorry for the delay! Is there anything specific that you'd like to have feedback on?

[j-kieffer]

Hello Jean, and sorry for the delay! Is there anything specific that you'd like to have feedback on?

No worries at all. I think the main questions I have are: do you think the interface looks OK? And is the documentation clear enough to follow what's going on?

[albinahlback]

Do you think the interface looks OK?

Yes, I think it looks very good.

And is the documentation clear enough to follow what's going on?

Yes, I think the documentation is very good! I've not looked everything into super much detail, but I think the naming scheme and descriptions looks good so far!

[albinahlback]

After you feel like you've addressed everything, could you squash your commits? Something like 1 to 5 commits, depending on how separate the commits can be made and how much it makes sense to split them.

(I guess you already know how to write commit messages, but here's how:

Squash the you've selected into one commit, and make the title of the commit short but descriptive and written in imperative. Its description will probably be long in your case, and should be a detailed overview. This makes it easier for people to backtrack history, changes etc.)‘

[albinahlback]

Can you make it more clear, or direct me on how to compute theta functions for specific $(a, b)$ (or how to obtain them from acb_theta_all)?

[j-kieffer]

Can you make it more clear, or direct me on how to compute theta functions for specific ( a , b ) (or how to obtain them from acb_theta_all)?

There are two possibilities:

• either call acb_theta_all and get the corresponding entry. Assuming $a = (a_1,\ldots,a_g)$ and $b = (b_1,\ldots,b_g)$, the index in the output vector is $i = b_g + 2b_{g-1} + \cdots + 2^{g-1}b_1 + 2^g(a_g + 2 a_{g-1} + \cdots + 2^{g-1}a_1)$.
• call acb_theta_jet with ord = all = sqr = 0 to get $\theta_{0,0}(z + \tau a/2 + b/2, \tau)$, and then multiply by $\exp(\pi i a^T (z + \tfrac b2) + \pi i a^T\tau a/4)$.

The second option will be more efficient. Do you I should write a direct interface (also allowing for partial derivatives of an individual $\theta_{a,b}$) ? It wouldn't be too much work.

[albinahlback]

I think it would make sense to have both. If the user is only interested in one specific tuple, then perhaps a wrapper for acb_theta_jet with this stuff you mention. Apart from this, I suppose it would be good to have an index function that takes the tuples $a$ and $b$, and returns the corresponding index for the output vector in acb_theta_all.

And I believe these features should be present in the main section so that it is clear when reading the section "Main user functions". Does this sound reasonable?

[fredrik-johansson]

This PR looks fine to me assuming that the exp_inv issue is fixed and that the commits are squashed.

[j-kieffer]

Hi @fredrik-johansson and @albinahlback , sorry for the delay as well. I tried to squash the older commits, down to 13 now. Do you think I should squash them more ? Also do you think the commit messages respect your guidelines ? I mostly concatenated the older commit messages, but I can add more details if needed.

[j-kieffer]

By the way, how should I squash commits that happened before a merge, say from https://github.com/flintlib/flint/pull/2182/commits/c45276fe08cd6a49067ec10425d75b35ffad776c to https://github.com/flintlib/flint/pull/2182/commits/9437e73a3fea13557962a41cff2c98cb5f9b7de2 ? git rebase forces me to solve the merge conflicts again, which feels wrong.

[fredrik-johansson]

Commits look fine.