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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

25 Citations (Scopus)

Résumé

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.

langue originale	Anglais
Pages (de - à)	1075-1096
Nombre de pages	22
journal	Journal of Symbolic Computation
Volume	45
Numéro de publication	10
Les DOIs	https://doi.org/10.1016/j.jsc.2010.06.024
état	Publié - 1 oct. 2010
Modification externe	Oui

Accès au document

10.1016/j.jsc.2010.06.024

Contient cette citation

@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

Résumé

Accès au document

Empreinte digitale

Contient cette citation