Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications

DOI10.1016/j.jsc.2022.07.008OpenAlexW4287401422MaRDI QIDQ2674000

Sergey Yurkevich, Alin Bostan

Publication date: 22 September 2022

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-03084680

zbMATH Keywords

complexityalgorithmspolynomial evaluation\(q\)-factorial\(q\)-holonomic sequences

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Enumerative combinatorics (05Axx)

Related Items

Fast norm computation in smooth-degree abelian number fields

Uses Software

• qMultiSum
• qZeil
• qGeneratingFunctions

Cites Work

• Even faster integer multiplication
• Irreducibility of \(q\)-difference operators and the knot \(7_{4}\)
• Algorithmic determination of \(q\)-power series for \(q\)-holonomic functions
• The degree of a \(q\)-holonomic sequence is a quadratic quasi-polynomial
• A fast approach to creative telescoping
• An algorithmic proof theory for hypergeometric (ordinary and ``\(q\)) multisum/integral identities
• Partition bijections, a survey
• A Mathematica package for \(q\)-holonomic sequences and power series
• q-Catalan numbers
• Lower bounds for polynomials with algebraic coefficients
• A holonomic systems approach to special functions identities
• On fast multiplication of polynomials over arbitrary algebras
• On \(q\)- difference functional equations
• Some results on computational complexity
• Fast multiplication of polynomials over fields of characteristic 2
• Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
• Rational solutions of linear difference and \(q\)-differential equations with polynomial coefficients
• On Zeilberger's algorithm and its \(q\)-analogue
• A direct algorithm to compute rational solutions of first order linear \(q\)-difference systems
• An algorithm for computing a standard form for second-order linear \(q\)-difference equations
• \(q\)-hypergeometric solutions of \(q\)-difference equations
• Algebraic solutions of differential equations (p-curvature and the Hodge filtration)
• \texttt{qMultiSum} -- a package for proving \(q\)-hypergeometric multiple summation identities
• Arithmetic theory of \(q\)-difference equations. The \(q\)-analogue of Grothendieck-Katz's conjecture on \(p\)-curvatures
• Weyl closure of a linear differential operator
• The colored HOMFLYPT function is q-holonomic
• Rogers-Ramanujan functions, modular functions, and computer algebra
• Congruences modulo cyclotomic polynomials and algebraic independence for \(q\)-series
• Desingularization in the \(q\)-Weyl algebra
• Rook placements and Jordan forms of upper-triangular nilpotent matrices
• Padé approximants for the q-elementary functions
• Analytic theory of linear \(q\)-difference equations
• The middle product algorithm. I: Speeding up the division and square root of power series
• On the number of solutions to the equation \(X^ 2=0\) in triangular matrices over a finite field
• The number of solutions of \(X^ 2 = 0\) in triangular matrices over \(GF(q)\)
• On the Melvin-Morton-Rozansky conjecture
• Algorithms for \(q\)-hypergeometric summation in computer algebra
• Counting representations of quivers over finite fields
• An extension of Zeilberger's fast algorithm to general holonomic functions
• A diagrammatic approach to the AJ conjecture
• New fifth and seventh order mock theta function identities
• Quantum knot invariants
• Polynomial evaluation and interpolation on special sets of points
• The colored Jones function is \(q\)-holonomic
• A survey of \(q\)-holonomic functions
• Counting points on hyperelliptic curves in average polynomial time
• Cycle classes on the moduli of \(K3\) surfaces in positive characteristic
• On the Diophantine approximation of values of functions satisfying certain linear q-difference equations
• Fast multiplication of large numbers
• Partition identities
• Computing differential Galois groups of second-order linear \(q\)-difference equations
• A Fast Algorithm for Computing the P-curvature
• Modern Computer Algebra
• Fast algorithms for differential equations in positive characteristic
• A Comprehensive Treatment of q-Calculus
• Low complexity algorithms for linear recurrences
• Computing theta functions in quasi-linear time in genus two and above
• Computation of the Similarity Class of the p-Curvature
• Elliptic Modular Forms and Their Applications
• Automatic Classification of Restricted Lattice Walks
• A search for Wilson primes
• q-Catalan Identities
• A fast algorithm for computing the characteristic polynomial of the p-curvature
• Powers of tensors and fast matrix multiplication
• Hypergeometric Orthogonal Polynomials and Their q-Analogues
• Faster Integer Multiplication
• The Fifth and Seventh Order Mock Theta Functions
• A Noncommutative Generalization and q-Analog of the Lagrange Inversion Formula
• Convex polyominoes and algebraic languages
• A general theory of identities of the Rogers-Ramanujan type
• On the Number of Additions to Compute Specific Polynomials
• Polynomials with 0-1 Coefficients That are Hard to Evaluate
• Linear 𝑞-difference equations
• On the evaluation of some sparse polynomials
• Computing Jacobi’s theta in quasi-linear time
• Canonical<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>q</mml:mi></mml:math>-deformations in arithmetic geometry
• Polynomials with Rational Coefficients Which are Hard to Compute
• On q-Deformed Real Numbers
• Intrinsic Approach to Galois Theory of 𝑞-Difference Equations
• Simple Forms and Rational Solutions of Pseudo-Linear Systems
• Computing the N-th term of a q-holonomic sequence
• An Efficient Formula for Linear Recurrences
• -DEFORMED RATIONALS AND -CONTINUED FRACTIONS
• Twisting q-holonomic sequences by complex roots of unity
• Fast algorithms for polynomial solutions of linear differential equations
• Some finite generalizations of Euler's pentagonal number theorem
• Properties ofq-holonomic functions
• Deterministic methods to find primes
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Some Orthogonal q‐Polynomials
• An Algorithm for Evaluation of Remote Terms in A Linear Recurrence Sequence
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
• Über die höheren Heineschen Reihen und eine einheitliche Theorie der sogenannten speziellen Funktionen
• A Short Proof of an Identity of Euler
• The Linear q-Difference Equation of the Second Order
• Faster computation of isogenies of large prime degree
• A new method to obtain lower bounds for polynomial evaluation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item