@inproceedings{10.1145/3373207.3404060,
    Abstract = {In 1977, Strassen invented a famous baby-step / giant-step algorithm that computes the factorial N! in arithmetic complexity quasi-linear in [EQUATION]. In 1988, the Chudnovsky brothers generalized Strassen's algorithm to the computation of the N-th term of any holonomic sequence in the same arithmetic complexity. We design q-analogues of these algorithms. We first extend Strassen's algorithm to the computation of the q-factorial of N, then Chudnovskys' algorithm to the computation of the N-th term of any q-holonomic sequence. Both algorithms work in arithmetic complexity quasi-linear in [EQUATION]. We describe various algorithmic consequences, including the acceleration of polynomial and rational solving of linear q-differential equations, and the fast evaluation of large classes of polynomials, including a family recently considered by Nogneng and Schost.},
    Address = {New York, NY, USA},
    Author = {Bostan, Alin},
    BookTitle = {Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation},
    File = {Computing the N-th term of a q-holonomic sequence - Bostan20-arxiv - a - d.pdf},
    ISBN = {9781450371001},
    Keywords = {q-factorial, algorithms, q-holonomic sequences, complexity},
    Location = {Kalamata, Greece},
    Pages = {46--53},
    Publisher = {Association for Computing Machinery},
    Series = {ISSAC '20},
    Title = {Computing the N-Th Term of a q-Holonomic Sequence},
    URL = {https://doi.org/10.1145/3373207.3404060},
    Year = {2020},
    bdsk-url-1 = {https://doi.org/10.1145/3373207.3404060},
    date-added = {2020-09-29 22:43:38 +0200},
    date-modified = {2020-09-29 22:43:38 +0200},
    numpages = {8},
    doi = {10.1145/3373207.3404060}
}

@inproceedings{10.1145/3373207.3404060, Abstract = {In 1977, Strassen invented a famous baby-step / giant-step algorithm that computes the factorial N! in arithmetic complexity quasi-linear in [EQUATION]. In 1988, the Chudnovsky brothers generalized Strassen's algorithm to the computation of the N-th term of any holonomic sequence in the same arithmetic complexity. We design q-analogues of these algorithms. We first extend Strassen's algorithm to the computation of the q-factorial of N, then Chudnovskys' algorithm to the computation of the N-th term of any q-holonomic sequence. Both algorithms work in arithmetic complexity quasi-linear in [EQUATION]. We describe various algorithmic consequences, including the acceleration of polynomial and rational solving of linear q-differential equations, and the fast evaluation of large classes of polynomials, including a family recently considered by Nogneng and Schost.}, Address = {New York, NY, USA}, Author = {Bostan, Alin}, BookTitle = {Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation}, File = {Computing the N-th term of a q-holonomic sequence - Bostan20-arxiv - a - d.pdf}, ISBN = {9781450371001}, Keywords = {q-factorial, algorithms, q-holonomic sequences, complexity}, Location = {Kalamata, Greece}, Pages = {46--53}, Publisher = {Association for Computing Machinery}, Series = {ISSAC '20}, Title = {Computing the N-Th Term of a q-Holonomic Sequence}, URL = {https://doi.org/10.1145/3373207.3404060}, Year = {2020}, bdsk-url-1 = {https://doi.org/10.1145/3373207.3404060}, date-added = {2020-09-29 22:43:38 +0200}, date-modified = {2020-09-29 22:43:38 +0200}, numpages = {8}, doi = {10.1145/3373207.3404060} }