Skip to content

Conversation

@j-kieffer
Copy link
Contributor

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
Copy link
Collaborator

Cool, I'm looking forward to next week!

@fredrik-johansson
Copy link
Collaborator

fredrik-johansson commented Jan 27, 2025

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
Copy link
Contributor Author

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
Copy link
Member

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
Copy link
Contributor Author

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.

@j-kieffer j-kieffer marked this pull request as ready for review February 13, 2025 15:27
@albinahlback
Copy link
Collaborator

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

@j-kieffer
Copy link
Contributor Author

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
Copy link
Collaborator

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
Copy link
Collaborator

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
Copy link
Collaborator

albinahlback commented Apr 2, 2025

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
Copy link
Contributor Author

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
Copy link
Collaborator

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
Copy link
Collaborator

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

@j-kieffer j-kieffer force-pushed the acb_theta-v2 branch 11 times, most recently from 9d3413f to dc9872c Compare May 19, 2025 09:10
@j-kieffer j-kieffer force-pushed the acb_theta-v2 branch 2 times, most recently from 9231093 to 0b29084 Compare May 19, 2025 09:27
j-kieffer added 15 commits May 19, 2025 11:29
- Reorganize header file, introduce theta_ctx structure
- Add basic functions for acb_theta_ctx_t
- Write tests and check ctx_set_tau and set_z
- Add tests for ctx_set_t and ctx_dupl
- New function sum_work to replace naive_worker
- Write sum_worker functions
- Keep theta_sum functions for later (without ctx argument)
- Add exp_2zs in ctx structure and modify functions accordingly
- Write t-sum_00
- Write function sum_a0
- Expose ctx_shift_z for easier testing
- Write and test sum_0b
- Fix signs in sum_all, faster tests
- Write and test sum_jet_00; write sum_jet_all
…ions accordingly

- Big rewrite of context functions
- Rewrite tests for context functions
- Rewrite tests for theta_sum functions
…l_notransform; rework context functions accordingly

- Attempt at ql_setup; add copy functions for contexts
- Write and test copy functions
- Attempt at ql_exact and ql_steps
- Change sum_a0 to sum_a0_tilde; test ql_setup and ql_steps
- Attempt at ql_split
- Add u in ctx_z for g = 1; test ql_lower_dim
- Attempt at ql_exact; remove sqr argument
- Attempt at ql_all_new
- Add duplication in ql_all_new
- Add errors in ql_all_new; fix bug in test
- Write test for ql_exact, todo: check all cases reached
- Add pattern as argument to ql_exact
- Always start with zero vector in ql_exact_lower_dim
- Allow all=1 in several functions and tests; fix old bug in ctx_z_shift_a0
- Fix bug in ql_steps for all=1
- Correct bug in ql_exact, smarter error bounds, test ql_all_new
- Rename ql_all_new -> all_notransform; fix bug in ql_setup
- Write and test main functions without transforms
…ns ql_a0 and ql_all

- Attempt at theta_00
- Attempt at new functions
- Fix bug in ql_all_sum (sqr=1); test all_new
- Add tests for main functions
- Test jet-00; use jet_all_notransform in g2_sextic_g5
- Replace old functions acb_theta_all and _jet_all by new ones
- Separate acb_theta_types.h
- Remove old ql_all functions
- Remove old ql_a0 functions
…including tests

- Remove g2_jet_naive_1, jet_naive_fixed_ab
- Cheaper t-g2_sextic
- Rewrite t-sum_jet_all from t-jet_naive_all
- Rewrite t-jet_all using sum_jet_all
- Use sum_jet_all in t-jet_error_bounds
- Remove t-jet_00_notransform, tested through jet_one_notransform
- Use sum_jet_all in t-sum_jet_00
- Remove old jet_naive functions
- Use sum_all_tilde in t-sum_a0_tilde
- Remove old naive_fixed functions
- Remove t-00_notransform, tested through one_notransform
- Use sum_0b in t-sum_00; remove old naive_00
- Use all_notransform in t-all
- Use modular_theta in t-sum_all_tilde
- Use sum_all_tilde in t-jet_ql_bounds
- Remove old naive_all
- Remove t-sum_0b, tested through sum_all_tilde
- Use sum_a0_tilde in t-agm_mul
- Move sum_worker type to acb_theta_types.h
- Remove old naive_worker, naive_0b
- Use new function reduce_tau in theta_00, theta_all, jet_00, jet_all
- Use new function reduce_z in theta_00, theta_all (no dots!), jet_00, jet_all
- Simpler t-jet_00 and t-jet_all
- No signs in sum_jet_all

Remove old naive_reduce; use reduced vectors in t-..._radius directly
…ep from ctx_z_set to ql_lowerdim

- Make jet_finite_diff static in jet_all_notransform
- Make summation workers static
- Remove most accessors for eld_t's
- Remove siegel_transform_z
- Replace siegel_yinv by siegel_cho_yinv
- Use siegel_cho_yinv everywhere
- Remove siegel_cho, siegel_yinv
- Make char_get_a static in sum_jet_all
- Remove char_get_slong
- Make dist functions static in dist_a0
- Replace dist_a0 by agm_distances
- Rename dist_addprec -> agm_addprec
- Make transform_sqrtdet static in transform_kappa
- Add nb in randtest_vec_reduced
- Use siegel_randtest_compact in t-ql_exact
- Sample compact/reduced tau, z where appropriate
- No reduction in ctx_z_set
- Remove ctx_r
- Add reduction in ql_lower_dim
- Correct bug in ctx_z_add_real
- Do not modify c in ctx_z_shift_a0
- Remove multiplications by c (always 1)
- Remove c, z in ctx_z
- Remove macro ctx_v
- Remove ctx_z_copy, ctx_choinv, ctx_y
- Make agm_hadamard static in agm_mul
- Remove macro eld_coord
- Make jet_ql_radius static in jet_all_notransform
- Remove tau from ctx_tau
- Rename naive_term -> sum_term
- Make ctx_tau_copy static in ql_setup
- Make ctx_tau_overlaps static in test
- Do not include fmpz_mat.h in header
- Rename transform_kappa -> siegel_kappa
- Use less macros for ctx_tau
- Remove macros for exp_tau
- Add g in ctx_tau, remove macro
- Remove macros ctx_is_real, ctx_exp_z, ctx_uinv, ctx_u
- Rename naive_radius->sum_radius
- Rename jet_ql_bounds -> sum_bound
- Use new function char_table
- Add argument ab in char_table
- Rename transform_char -> char_table
- Rename transform_proj -> char_shuffle
- Add flag allow_shift in ctx_tau
- Restore all tests
- Avoid some nans
- Document new main functions
- Document new acb_siegel functions
- Document new acb_theta_eld functions
- Document new ctx functions
- Move theoretical stuff together
- Add a word on precision
- Reorganize header
- Document new ql functions
- Rewrite intro
- Reorder tests
- Reorganize and document tests; remove prints
… accordingly

- agm_distances -> eld_distances
- agm_addprec -> sum_addprec
- sum_bound -> local_bound
- Odd theta constants are zero in ql_setup; write profiling code for ql_exact
- Add cst argument to nb_steps
- New parameters for g=1
- More useful profiling, better siegel_randtest_compact, more info in ql_nb_steps
- Adjust nb_steps for g=2
- More logical version of ql_nb_steps; test more precisions when profiling
- Write profiling program for ql_setup which showed we need a different sum_a0_tilde
- Write a comprehensive acb_theta_sum
- Allow shifts and use Cholesky in ctx_tau_t for g=1
- Replace sum_all_tilde, sum_a0_tilde, sum_0b, sum_00 by sum everywhere
- Manipulate all context fields for g=1; do not compute exp_z in shift_a0; remove fields exp_tau_a_div_2 and exp_tau_a_div_2_inv
- Reduced vectors in t-shift_a0; use lbound instead of midref in sum_addprec
- No warning in sum_0x
- Avoid infinite inverses in shift_a0
- Rewrite ql_setup for clarity, use accurate number of guard bits
- Profile acb_theta_sum; add some guard bits when manipulating contexts in ql_setup
- Add guard bits in acb_theta_sum; allow more points in ellipsoids
- Tighter sum_radius
- Fix precision in sum_radius
- Less stringent randtest_compact (cf p-sum in genus 10)
- Correct expensive precision bug in agm_mul_tight, remove agm_mul_tight_g1 for less multiplications
- Refactor code in ql_exact, use void output
- Expose rough pattern in ql_nb_steps; expose ql_steps_input_sum for use in test code
- Better ql_nb_steps to take previous improvements into account
- Correct precision bug in acb_theta_sum; write sum_jet for more code factorization
- Fix error bounds in sum_jet, remove sum_jet_00
- Avoid do-while loops in all_notransform; better precision management in sum_jet; remove sum_jet_all
- Make ql_steps static in ql_exact; expose agm_mul_all_tight
- Make ql_steps_input_sum static in ql_exact
- More efficient jet_notransform functions
- Test jet_notransform_ql, fix bugs
- Write profile code for jet_notransform_ql showing precision bugs
- Fix precision bug in jet_ql_notransform, remove argument pattern
…sts:

- Separate all_a and all_b in sum_jet
- Test jet_notransform_ql with all = 0
- Write and test acb_theta_jet_notransform
- Remove 00_notransform and one_notransform
- Remove jet_00_notransform and jet_one_notransform
- Remove jet_all_notransform
- Rename jet_notransform_ql to ql_jet_fd; expose ql_jet; use jet_notransform in all_notransform
- Rename jet_error -> ql_jet_error
- Merge jet_00 and jet_all as acb_theta_jet
- More efficient jet_exp_qf for ord = 0
- Allow sqr parameter in jet_notransform
- Merge all_notransform into jet_notransform
- Allow sqr parameter in acb_theta_jet; call acb_theta_jet in acb_theta_all
- Remove acb_theta_00, fix missing include
- Restore previous signature for acb_theta_all
- Rename local_bound -> ql_local_bound; do not use in g2_sextic_chi5
- Allow sqr parameter in siegel_kappa, stronger test
- Use siegel_kappa in siegel_kappa2
- Allow all as parameter in agm_mul
- Allow all as parameter in agm_mul_tight; fix normalization conventions
- Expose ctx_tau_overlaps
- Allow lead parameter in g2_covariants and g2_transvectant
- Fix missing includes in tests; remove t-g2_sextic_chi5
- Merge g2_psi4, psi6, chi10, chi12 as g2_even_weight
- Remove macro COV_NB
- Remove g2_sextic
- Remove tests and make static/inline functions for char_is_even/goepel/syzygous
- Make char_dot_acb static in jet_notransform
- Fix bugs in acb_theta_jet, t-agm_mul_tight
- Strengten all tests by disallowing NaNs and infinities
- Accelerate t-agm_mul
- Fix bug in ql_setup for hard step, all = 1, k = 0; use less roots for hard step, all = 0, k = 0
- Fix output of ql_local_bound that caused ql_jet_fd to fail
- Take possible divisions by chi5=0 into account in g2 tests
- Try to improve code coverage
- Stronger test for agm_mul_tight showing that error cannot be smaller
- Test all_a and all_b in t-sum
- Write t-reduce_z; further comments on code coverage
- Remove nb argument in sum_work
- Expose sum_sqr_pow, mutualize in sum and sum_jet
- Put types back in main header, expose eld_box
- Make shift-a0 static in sum
- More inline functions, introduce char_bit
- Mutualize code in sum_jet
- Update doc for tests, profiling code, example of usage
- Restore section "Main user functions"
@j-kieffer
Copy link
Contributor Author

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
Copy link
Contributor Author

j-kieffer commented May 19, 2025

By the way, how should I squash commits that happened before a merge, say from c45276f to 9437e73 ? git rebase forces me to solve the merge conflicts again, which feels wrong.

@fredrik-johansson
Copy link
Collaborator

Commits look fine.

@fredrik-johansson fredrik-johansson merged commit 48b01ee into flintlib:main May 21, 2025
13 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants