CS Paper Radar

Parallel Integration over Simple Radical Extensions in Mixed Towers: Charlwood's Integrals

Sam Blake

cs.SC ·submitted 2026-09-22 03:23 UTC · v1

Abstract

We evaluate a SymPy implementation of the parallel Risch-Norman method using Charlwood's 2008 suite of 50 challenging indefinite integrals. The system automatically builds integrand towers, verifies answers by differentiation, and returns correct, verified integrals for 49 problems with zero errors. The single failure, $\int\arcsin(x\sqrt{1-x^2})\,dx$, is proven non-elementary using a holomorphic-remainder certificate, though limited by an unverified completeness hypothesis on a genus-three curve. Part II's degree bounds successfully reduce classical ansatz sizes by two-thirds without impacting running time. The paper details algorithmic mechanisms like $S'$-units, Pell units, and residue computing in tower coordinates. Compared to mature implementations, this untuned SymPy prototype is slower than FriCAS (by a factor of six on the median integral) but more accurate than AXIOM (which returned three wrong answers). Profiling pinpoints performance bottlenecks in nonlinear norm searches and nested number fields, outlining clear targets for optimisation.

Closest papers

Nearest neighbours by meaning across the whole index.

Parallel Integration over Simple Radical Extensions

cs.SC ·2026-08-30 ·Sam Blake
theory similarity 0.64
Abstract

The parallel Risch (Risch--Norman) method is a fast heuristic for computing elementary integrals over towers of transcendental extensions. Its justification rests on two structural facts about the integral: a bound on its denominator and a description of the logarithms that can occur. Both are known for purely logarithmic towers (Davenport--Trager) and, in the form of a structure theorem, for arbitrary derivations on multivariate rational function fields (Bronstein). We extend both facts to a simple radical extension $L=K(y)$, $y^m=q$, of such a field. The key observations are that the integral closure of $F[t_1,\dots,t_n]$ in $L$ has an explicit basis, so that all factorisation can remain in a polynomial ring, and that the derivation has a well-defined pole order $δ_P\in\{0,1,e_P\}$ at every height-one prime $P$, so that pole orders of derivatives shift by $δ_P$. The denominator of the integral then has the same Hermite-type shape as in the transcendental case, while the admissible logands are precisely the $S$-units of the integral closure for an explicit finite set $S$ of primes; the latter can be larger than the set generated by irreducible polynomials, as the unit $x+\sqrt{x^2+1}$ shows. For $n=1$ we relate these $S$-units to torsion in the Jacobian and, for $m=2$, to the polynomial Pell equation, obtaining a complete description of the logarithmic part in genus~0. We describe the resulting algorithm and give examples.

0.46

Parallel Integration over Simple Radical Extensions III: Antiderivatives in Terms of Special Functions

cs.SC ·2026-10-03 ·Sam Blake
theory similarity 0.62
Abstract

We extend the parallel integration method for mixed towers of Part~II from elementary antiderivatives to antiderivatives in special functions. The class covered is the incomplete gamma function $Γ(s,\cdot)$ at rational $s$, which contains $\Ei$, $\li$, $\Si$, $\Ci$, $\erf$ and the Fresnel integrals, together with the elliptic integrals $F$, $E$, $Π$. Each special function enters through a \emph{kernel}: a known element of the tower whose antiderivative is that function. It is either fixed by residues or added as one more column of the single linear system, and no Risch differential equation is solved. We prove where kernels can have poles; the $\erf$ kernels live in the sub-critical window of radical towers. The denominator theory, degree bounds and certificates of Part~II carry over, and new criteria decide most places that Part~II leaves to a guess. Elliptic integrals are carried by the radical, and a non-torsion residue divisor becomes a third-kind term. We prove that special functions are introduced only when necessary. Elementary answers are returned unchanged, and in strict mode a special function comes with a certificate that the integrand has no elementary integral. When no complete answer is found, a partial answer with a reduced remainder is returned. All examples are computed by a SymPy implementation and verified by differentiation.

0.35

Exposing SIMD Parallelism in SQIsign: An AVX-512 Implementation

cs.CR ·2026-08-14 ·Weize Wang, Chutong Wang, Yu Wu, Qifan Xue, Jieyu Zheng +1 more
similarity 0.60
Abstract

Modern isogeny-based cryptosystems spend much of their running time in finite-field, elliptic-curve, and higher-dimensional isogeny arithmetic. Exploiting SIMD parallelism is nontrivial: routines such as Montgomery ladders contain loop-carried dependencies, while point, pairing, and theta-coordinate formulas expose only irregular fine-grained parallelism. We show that substantial SIMD parallelism can be recovered by reorganizing the arithmetic dependency graphs of higher-level primitives rather than vectorizing field multiplication in isolation. We develop an end-to-end AVX-512IFMA implementation of SQIsign in which data remain in a radix-$2^{51}$ vector representation across most of the curve-side computation. Our redesign includes projective xDBLADD schedules, batched point doubling in several coordinate systems, a vectorized biscalar ladder, fused cubical-arithmetic pairing steps, and batched one- and two-dimensional isogeny evaluation. Relative to the reference C implementation, we achieve end-to-end speedups of $1.76\times$, $1.71\times$, and $3.18\times$ for key generation, signing, and verification at NIST level~I; combined with Qlapoti, key-generation and signing speedups rise to $2.90\times$ and $2.69\times$. We further apply the same backend and methodology to CORAL, a recent isogeny group action for post-quantum non-interactive key exchange based on two-dimensional $2$-isogenies. Across five parameter sets, this yields $1.28$--$1.40\times$ speedups for key generation and $1.92$--$2.46\times$ for shared-key computation. These results provide cross-scheme evidence that algorithm-level SIMD scheduling is a reusable optimization dimension for higher-dimensional isogeny cryptography.

0.04

Performance Evaluation of an Adaptive Quadrature and a Double Exponential Formula Using Arbitrary-Precision Floating-Point Arithmetic

cs.PF math.NA ·2026-08-13 ·Tomonori Kouya
similarity 0.56
Abstract

Using arbitrary-precision arithmetic provided by the GNU Multiple Precision Floating-Point Reliable Library, we implement AQE11D---that is, Ninomiya's adaptive 9-point Newton--Cotes rule extended with a sequence of higher-order rules---and Takahasi and Moris' double exponential (DE) formula. We evaluate them for Kahaner's 21 test problems. For both absolute tolerances $10^{-50}$ and $10^{-100}$, AQE11D attains target accuracy on all 21 problems; however, for strong endpoint singularity such as $1/\sqrt{x}$, it requires about $5.4\times10^{7}$ function evaluations at $10^{-100}$, roughly $7\times10^{4}$ times as many as the DE formula. The formula converges on 18 problems at both tolerances, demonstrating its strength against endpoint singularities but also its failure, as it stands, on problems with a singularity inside the integration interval.

0.04

Parallel Integration over Simple Radical Extensions II: Mixed Towers

cs.SC ·2026-09-12 ·Sam Blake
theory similarity 0.56
Abstract

In Part I we extended the structure theorems underlying the Risch--Norman (parallel Risch) method to a simple radical extension $L=K(y)$, $y^m=q$, of a differential field $K=F(t_1,\dots,t_n)$ closed under the derivation. Here we remove the closure hypothesis: the radical may occupy any position in the tower, so that the derivatives of the generators above it involve $y$ --- the setting of Bronstein's algorithm for mixed elementary functions. The working ring is $\cA=\cO[t_{j+1},\dots,t_n]$, the integral closure of $F[t_1,\dots,t_n]$ in $L$: a Krull domain, free over the polynomial ring on Trager's basis, so that all factorisation remains in a unique factorisation domain. The denominator of the derivation is no longer an element but a divisor $\fd_D$ on $\cA$, and the valuation lemma takes the unified form $v_P(Dg)=v_P(g)-(1+v_P(\fd_D))$ at normal height-one primes, subsuming the shifts $\{1,e_P\}$ of Part I; the proof localises and requires no cancellation analysis. Stability of the class group and the unit group, $\Cl(\cA)\cong\Cl(\cO)$ and $\cA^*=\cO^*$, splits the admissible logands into $S$-units of $\cO$ --- computed by the machinery of Part I --- and irreducible polynomials moving in the upper variables, whose residues must be constants. We prove degree bounds in the top variable and describe the resulting algorithm, which --- unlike the classical parallel method, whose failure proves nothing --- returns certificates of non-elementarity in two situations: a residue outside the constant field, and, when every bound in force is proved, a residue-free remainder that the linear system shows to be non-exact.

0.27

Faster PMNS Multi-precision Multiplications Using Truncated Montgomery Technique

cs.CR ·2026-10-07 ·Laurent-Stéphane Didier, Alexy Dutois-Ruiz, Jean-Marc Robert
similarity 0.53
Abstract · 21 pages, one figure

The Polynomial Modular Number Systems (PMNS) aim to represent elements of fields or rings of large characteristics using polynomials satisfying bounds on some parameters (degree, absolute values of the coefficients). Those PMNS, while some conditions are fulfilled, using convenient parameters and implementation features, allow some speed-ups in cryptographic computations. Recent works (Meloni \emph{et al.} \cite{MeloniPV25}) propose better speed-ups by improving the parameter generation of the system, and by using multi-precision polynomial coefficients, i.e. coefficients stored using several machine words. In this work, we first present PMNS schoolbook software implementation better in some context than the Toeplitz state-of-the-art counterpart of \cite{MeloniPV25}, taking advantage of smaller memory cost by being free to choose a smaller $n$ parameter, minimizing at the same time the complexity of the multiplication. This implementation for 4096 bit modulo size shows element size smaller by 11\% and 20 \% speed-up. We thus present a new improvement on the PMNS, applying to the \textsl{internal reduction} an approach similar to the truncated Montgomery reduction technique presented by Didier \emph{et al.} in \cite{DidierEGR24}. In the context of software implementations using \texttt{AVX512} instruction set extension, and modulo size up to 8192 bits, this new approach allows speed-ups up to 15\% in modular multiplication computation, in comparison with conventional approaches.

0.26

Geometric Function Atlas: certified computing for geometric function theory in Python

cs.MS ·2026-09-07 ·Kishan Gurumurthy, Pushparaj Devadiga, Prasanna Devadiga, Arya Suneesh, Asha Sebastian
code/data similarity 0.53
Abstract

We describe geometric-function-atlas, our open-source Python package for the sharp extremal problems of geometric function theory. We organise it around a catalogue of thirty-nine Ma--Minda starlike generators. From this catalogue we compute exact Taylor coefficients, closed-form Fekete--Szegő constants, exact coefficients of the Ma--Minda extremal function, and admissibility screens. Our verifier answers membership questions for normalised polynomials at three levels of evidence: a floating-point grid screen, an exact sufficient condition decided in rational arithmetic, and a certified interval enclosure at the worst screened point. Every answer names the level at which we obtained it. We ship a checksummed artifact snapshot with three hundred and six coefficient certificates and seven hundred and two directed inclusion radii. Eight reviewed radius lanes carry certificates whose proof chains we replay symbolically, and we re-execute every coefficient certificate through our exact Schur-parameter machinery on request. We emit all results through one versioned envelope that records the method, the evidence status, the assumptions, and the artifact identifiers. Two optional laboratories apply the same discipline to cryptographic S-box metrics and to image-quality metrics. We present our design, state as propositions what each tier establishes, follow one radius lane from screen to replayed certificate, report measured timings, and place our package among symbolic-algebra, rigorous-numerics, and mathematical-database software. We release geometric-function-atlas under the MIT licence on the Python Package Index and at https://github.com/Prasanna28Devadiga/geometric-function-atlas.

0.59

Lord of the Precision, the Two Floats: Double-Word Arithmetic for Complex Numbers

cs.MS ·2026-11-05 ·František Stloukal, Fabienne Jézéquel
code/data similarity 0.51
Abstract · 46 pages, 8 figures, 3 tables

Datacenter GPUs increasingly favour low-precision floating-point formats, offering higher throughput than FP64. Double-word (DW) arithmetic represents numbers as unevaluated sums of two floating-point values, providing higher accuracy. We present the first error analysis of complex DW multiplication and division. Both operations reduce to sums of two DW products, combined using one of three DW addition algorithms: accurate, sloppy, or Madd. Normalising DW products ensures nonoverlapping components, but omitting this step reduces the number of arithmetic operations. We bound the resulting overlap and prove that Madd retains a relative error bound of $3u^2+O(u^3)$ for overlapping inputs, where $u$ is the unit roundoff. For all variants, we establish relative error bounds of the form $(ακ+β)u^2+O(u^3)$, where $κ$ is the condition number of the sum of products. Our analysis shows that the less expensive sloppy addition suffices. We implement these variants in CompleXDW, an open-source C++ library for CPUs and GPUs. In the high-energy physics code MadGraph7, FP32-based DW arithmetic achieves up to 2.9x and 2.1x higher throughput than FP64 on NVIDIA L40S and AMD Radeon Pro W7900 GPUs, respectively, while losing approximately 1.4 correct significant digits.

0.39