Evaluating parametric holonomic sequences using rectangular splitting

DOI10.1145/2608628.2608629MaRDI QIDQ3452403zbMATH OpenOpenAlexFDO

Authors Fredrik Johansson

Publication date 11 November 2015

Published in Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.3741

zbMATH Keywords

fast arithmeticgamma functionhypergeometric functionslinearly recurrent sequencesnumerical evaluation

Mathematics Subject Classification ID

Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Numerical aspects of recurrence relations (65Q30) Symbolic computation and algebraic computation (68W30)

Abstract: We adapt the rectangular splitting technique of Paterson and Stockmeyer to the problem of evaluating terms in holonomic sequences that depend on a parameter. This approach allows computing the $n$-th term in a recurrent sequence of suitable type using $O(n^{1/2})$ "expensive" operations at the cost of an increased number of "cheap" operations. Rectangular splitting has little overhead and can perform better than either naive evaluation or asymptotically faster algorithms for ranges of $n$ encountered in applications. As an example, fast numerical evaluation of the gamma function is investigated. Our work generalizes two previous algorithms of Smith.

Recommendations

• Fast evaluation of holonomic functions
• Reduced complexity evaluation of hypergeometric functions
• Fast evaluation of holonomic functions near and in regular singularities
• scientific article; zbMATH DE number 1361301
• A Note on the Space Complexity of Fast D-Finite Function Evaluation

Cites work

• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Cylindrical algebraic decomposition using validated numerics
• Definability and decision problems in arithmetic
• scientific article; zbMATH DE number 1952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• On Computable Numbers, with an Application to the Entscheidungsproblem
• The Jordan Curve Theorem, Formally and Informally

Cited in

(6)

• Fast and Rigorous Arbitrary-Precision Computation of Gauss--Legendre Quadrature Nodes and Weights
• Short addition sequences for theta functions
• Computing hypergeometric functions rigorously
• Fast evaluation and root finding for polynomials with floating-point coefficients
• Fast evaluation and root finding for polynomials with floating-point coefficients
• The polynomial set associated with a fixed number of matrix-matrix multiplications

Describes a project that uses

Uses Software

• Jordan

This page was built for publication: Evaluating parametric holonomic sequences using rectangular splitting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452403)