Effective bounds for P-recursive sequences

Marc Mezzarobba; Bruno Salvy

doi:10.1016/j.jsc.2010.06.024

Effective bounds for P-recursive sequences

Marc Mezzarobba
, Bruno Salvy

INRIA Rocquencourt

Research output: Contribution to journal › Article › peer-review

25 Citations (Scopus)

Abstract

We describe an algorithm that takes as input a complex sequence (u_n) given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound (v_n) such that {box drawings light vertical}u_n{box drawings light vertical}≤vn for all n. Generically, the bound is tight, in the sense that its asymptotic behaviour matches that of u_n. We discuss applications to the evaluation of power series with guaranteed precision.

Original language	English
Pages (from-to)	1075-1096
Number of pages	22
Journal	Journal of Symbolic Computation
Volume	45
Issue number	10
DOIs	https://doi.org/10.1016/j.jsc.2010.06.024
Publication status	Published - 1 Oct 2010
Externally published	Yes

Keywords

Algorithm
Bounds
Cauchy-Kovalevskaya majorant
Certified evaluation
Holonomic functions

Access to Document

10.1016/j.jsc.2010.06.024

Cite this

@article{20ed7e03b4094ec1b49bf6125569de6b,

title = "Effective bounds for P-recursive sequences",

abstract = "We describe an algorithm that takes as input a complex sequence (un) given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound (vn) such that \{box drawings light vertical\}un\{box drawings light vertical\}≤vn for all n. Generically, the bound is tight, in the sense that its asymptotic behaviour matches that of un. We discuss applications to the evaluation of power series with guaranteed precision.",

keywords = "Algorithm, Bounds, Cauchy-Kovalevskaya majorant, Certified evaluation, Holonomic functions",

author = "Marc Mezzarobba and Bruno Salvy",

year = "2010",

month = oct,

day = "1",

doi = "10.1016/j.jsc.2010.06.024",

language = "English",

volume = "45",

pages = "1075--1096",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Academic Press",

number = "10",

}

TY - JOUR

T1 - Effective bounds for P-recursive sequences

AU - Mezzarobba, Marc

AU - Salvy, Bruno

PY - 2010/10/1

Y1 - 2010/10/1

N2 - We describe an algorithm that takes as input a complex sequence (un) given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound (vn) such that {box drawings light vertical}un{box drawings light vertical}≤vn for all n. Generically, the bound is tight, in the sense that its asymptotic behaviour matches that of un. We discuss applications to the evaluation of power series with guaranteed precision.

AB - We describe an algorithm that takes as input a complex sequence (un) given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound (vn) such that {box drawings light vertical}un{box drawings light vertical}≤vn for all n. Generically, the bound is tight, in the sense that its asymptotic behaviour matches that of un. We discuss applications to the evaluation of power series with guaranteed precision.

KW - Algorithm

KW - Bounds

KW - Cauchy-Kovalevskaya majorant

KW - Certified evaluation

KW - Holonomic functions

U2 - 10.1016/j.jsc.2010.06.024

DO - 10.1016/j.jsc.2010.06.024

M3 - Article

AN - SCOPUS:77955280341

SN - 0747-7171

VL - 45

SP - 1075

EP - 1096

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

IS - 10

ER -

Effective bounds for P-recursive sequences

Abstract

Keywords

Access to Document

Fingerprint

Cite this