fredrikj.net / blog /

Arb 2.8.0 released

December 29, 2015

I've tagged Arb 2.8.0, just in time before the new year. There are important bugfixes, compatibility enhancements, and new features. I've already blogged about the Airy functions, the hypergeometric 2F1 function and computing Bell numbers. There's much more that I won't have time to write about in detail.

According to the changelog, at least eight people besides myself contributed to this release, which is a new record (apologies if I forgot to credit someone). Much activity was prompted by Arb becoming a standard package of both SageMath and the Julia computer algebra package Nemo. This meant that various screws had to be tightened and some new holes had to be drilled. Bill Hart notably took on the massive job of making the code compatible with 64-bit Windows (mainly by replacing all uses of long with FLINT's slong).

Changelog

• Compatibility and build system
  • Windows64 support (contributed by Bill Hart).
  • Fixed a bug that broke basic arithmetic on targets where FLINT uses fallback code instead of assembly code, such as PPC64 (contributed by Jeroen Demeyer).
  • Fixed configure to use EXTRA_SHARED_FLAGS/LDFLAGS, and other build system fixes (contributed by Tommy Hofmann, Bill Hart).
  • Added soname versioning (contributed by Julien Puydt).
  • Fixed test code on MinGW (contributed by Hrvoje Abraham).
  • Miscellaneous fixes to simplify interfacing Arb from Julia.
• Arithmetic and elementary functions
  • Fixed arf_get_d to handle underflow/overflow correctly and to support round-to-nearest.
  • Added more complex inverse hyperbolic functions (acb_asin, acb_acos, acb_asinh, acb_acosh, acb_atanh).
  • Added arb_contains_int and acb_contains_int for testing whether an interval contains any integer.
  • Added acb_quadratic_roots_fmpz.
  • Improved arb_sinh to use a more accurate formula for x < 0.
  • Added sinc function (arb_sinc) (contributed by Alex Griffing).
  • Fixed bug in arb_exp affecting convergence for huge input.
  • Faster implementation of arb_div_2expm1_ui.
  • Added mag_root, mag_geom_series.
  • Improved and added test code for arb_add_error functions.
  • Changed arb_pow and acb_pow to make pow(0,positive) = 0 instead of nan.
  • Improved acb_sqrt to return finite output for finite input straddling the branch cut.
  • Improved arb_set_interval_arf so that [inf,inf] = inf instead of an infinite interval.
  • Added arb_power_sum_vec for computing power sums using Bernoulli numbers.
  • Added computation of the Fujiwara root bound for acb_poly.
  • Added code to identify all the real roots of a real polynomial (acb_poly_validate_real_roots).
  • Added several convenient assignment functions, including arb_set_d, acb_set_d, acb_set_d_d, acb_set_fmpz_fmpz (contributed by Ricky Farr).
  • Added many accessor functions (_arb/acb_vec_entry_ptr, arb_get_mid/rad_arb, acb_real/imag_ptr, arb_mid/rad_ptr, acb_get_real/imag).
  • Added missing functions acb_add_si, acb_sub_si.
  • Renamed arb_root to arb_root_ui (keeping alias) and added acb_root_ui.
• Special functions
  • Implemented the Gauss hypergeometric function 2F1 and its regularized version.
  • Fixed two bugs in acb_hypgeom_pfq_series_direct discovered while implementing 2F1. In rare cases, these could lead to incorrect values for functions depending on parameter derivatives of hypergeometric series.
    • The first bug involved incorrect handling of negative integer parameters. The bug only affected 2F1 and higher functions; it did not affect correctness of any previously implemented functions that relied on acb_hypgeom_pfq_series_direct (such as Bessel Y and K functions of integer order).
    • The second bug involved a too small bound being computed for the sum of a geometric series. The geometric series bound is nearly tight for 2F1, and the incorrect version caused immediate test failures for that function. Theoretically, this bug affected correctness of some previously-implemented functions that relied on acb_hypgeom_pfq_series_direct (such as Bessel Y and K functions of integer order), but since the geometric bound is far from tight in those cases, those functions were still reliable in practice (no failing test case has been found).
  • Implemented Airy functions and their derivatives (acb_hypgeom_airy).
  • Implemented the confluent hypergeometric function 0F1 (acb_hypgeom_0f1).
  • Implemented associated Legendre functions P and Q.
  • Implemented Chebyshev, Jacobi, Gegenbauer, Laguerre, Hermite functions.
  • Implemented spherical harmonics.
  • Added function for computing Bessel J and Y functions simultaneously.
  • Added rising factorials for non-integer n (arb_rising, acb_rising).
  • Made rising factorials use gamma function for large integer n.
  • Faster algorithm for theta constants and Dedekind eta function at very high precision.
  • Fixed erf to give finite values instead of +/-inf for big imaginary input.
  • Improved acb_zeta (and arb_zeta) to automatically use fast code for integer zeta values.
  • Added double factorial (arb_doublefac_ui).
  • Added code for generating Hilbert class polynomials (acb_modular_hilbert_class_poly).
  • Added computation of Bell numbers (arb_bell_fmpz).
• Matrices
  • Added faster matrix squaring (arb/acb_mat_sqr) (contributed by Alex Griffing).
  • Added matrix trace (arb/acb_mat_trace) (contributed by Alex Griffing).
  • Added arb/acb_mat_set_round_fmpz_mat, acb_mat_set(_round)_arb_mat (contributed by Tommy Hofmann).
  • Added arb/acb_mat_transpose (contributed by Tommy Hofmann).
  • Added comparison methods arb/acb_mat_eq/ne (contributed by Tommy Hofmann).
• Other
  • Added complex_plot example program.
  • Added Airy functions to real_roots example program.
  • Other minor patches were contributed by Alexander Kobel, Marc Mezzarobba, Julien Puydt.
  • Removed obsolete file config.h.

What hasn't made it (yet)

A few nagging issues remain undone, including:

• Code for working with roots of integer polynomials (made some progress on this; will need more work to get it right).
• Smarter evaluation strategy for hypergeometric functions (just started; easy but tedious work).
• Patching some reported test failures on Windows 64-bit (believed to be bugs in the test code, not actual bugs in the library).
• Doing something about that annoying include path issue (sorry).

I try to keep the git master the best version at any time, so that new version numbers simply can be inserted at arbitrary, convenient times (release early, release often). Version 2.7.0 was tagged in July. Rather than delaying 2.8.0 any further, the items above will just have to wait another version number or two. Of course, those undone issues are just minor things. Here are some bigger development ideas, some of which I hope to work on in 2016:

• Arithmetic that is sensitive to the output accuracy. Currently, Arb will happily use 1000 bits of working precision if the precision is set to 1000 bits, even if the inputs only are accurate to 100 bits and the output only will be accurate to 100 bits. In this case, Arb could use 128 bits internally and still produce a result accurate to 100 bits, but much faster. This is a huge project, and needs to be done extremely carefully, but it can be done one function at a time. An optimistic estimate is that this could speed up the library for general use by a factor 1.5-2.
• Real and complex Taylor models, at least in one variable. Taylor models are a powerful approach to working with analytic functions, allowing one to compute function roots, optima, derivatives, integrals, solutions of differential equations (etc.) with high precision and rigorous error bounds. The advantages over the existing code in Arb (implemented only for a few such tasks) are that error bounds are computed more efficiently, and that the interface can be made more convenient. Extending higher transcendental functions to Taylor models is a research problem.
• Enhanced linear algebra, in particular numerically stable solution of linear systems based on a posteriori bounds. Eigenvalues would be a nice stretch goal, but I'm not a big user of them myself, nor too familiar with the algorithms.
• Rewriting some of the now-ancient gamma and zeta function code. This should be relatively easy.
• Support for evaluation of generic L-functions and D-finite functions. This is more or less a research problem (but there is significant prior work by Pascal Molin, Marc Mezzarobba, and others).
• Introducing squaring functions throughout, and maybe removing the "same input pointers same variable" semantics entirely.
• Multivariate polynomials and power series. I'm honestly not too keen on doing this in C, but a basic sparse multivariate polynomial type would be useful to have. This could also be done in Nemo and Sage.

In other news

• Andrew Booker and T.D. Browning have published a preprint titled Square-free values of reducible polynomials. The accompanying source code and computational data are available. They write: "We rely heavily throughout on Fredrik Johansson's excellent library arb for arbitrary precision interval arithmetic. Thus, we make no assumptions about round-off error, so that, modulo bugs in the code or computer hardware, our results are rigorous."
• Rémi Imbach, Guillaume Moroz and Marc Pouget (INRIA Nancy) have announced an opening for a master's thesis internship on "Root solver using subdivision and Fast Fourier Transform". They write: "the candidate will design and experiment new subdivision methods, and compare them with state-of-the-art approaches [Arb library or Sage]". This sounds quite interesting. Asymptotically fast methods tend to have poor numerical stability and substantial overhead, which makes high performance hard to achieve in practice. Research in this direction is certainly needed.
• Also check out arbcmath.h, a wrapper of Arb that provides double precision transcendental functions for use with the C99 double complex type.
• In November, I gave a talk for a general audience titled Taking precision to the limit (PDF slides). I attempted to hypnotize the audience by showing this animation:
• Another animation (made a few days later), showing how Arb uses interval arithmetic to isolate the zeros of the Riemann zeta function:
• Owen Maresh has made some nice plots of iterations of analytic function with Arb. I'm shamelessly copying them here:

fredrikj.net  |  Blog index  |  RSS feed  |  Follow me on Mastodon  |  Become a sponsor