Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: Algebraic and analytic approaches collated - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2014

Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: Algebraic and analytic approaches collated

Résumé

Among all sequences that satisfy a divide-and-conquer recurrence, those which are rational with respect to a numeration system are certainly the most basic and the most essential. Nevertheless, until recently this specific class of sequences has not been systematically studied from the asymptotic standpoint. We recall how a mechanical process designed by the author permits to compute their asymptotic expansions. The process is based on linear algebra, and involves computing Jordan normal forms, joint spectral radii, and solving dilation equations. The main contribution of the present article is the comparison between our algebraic method and the classical analytic number theory approach. Moreover, we develop new ways to compute the Fourier series of the periodic functions involved in the expansion. The article comes with an extended bibliography.
Parmi les suites qui vérifient une récurrence de type diviser pour régner, les suites qui sont rationnelles dans une base de numération sont les plus simples et les plus fondamentales. Cependant, jusqu'à récemment, cette classe particulière de suites n'a pas fait l'objet d'une étude systématique du point de l'analyse asymptotique. Nous rappelons comment un procédé régulier, mis au point par l'auteur, permet de calculer le développement asymptotique d'une telle suite. Le procédé est basé sur l'algèbre linéaire et utilise le calcul d'une forme de Jordan et d'un rayon spectral ainsi que la résolution d'équations de dilatation. La contribution principale du présent article est la comparaison entre notre méthode algébrique et l'approche classique issue de la théorie analytique des nombres. De plus nous mettons au point de nouvelles manières de calculer les séries de Fourier des fonctions périodiques qui apparaissent dans les développements. L'article est assorti d'une importante bibliographie.
Fichier principal
Vignette du fichier
Dumas2014.pdf (1.41 Mo) Télécharger le fichier
Dumas14.bib (358 B) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Autre

Dates et versions

hal-01065761 , version 1 (18-09-2014)

Identifiants

Citer

Philippe Dumas. Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: Algebraic and analytic approaches collated. Theoretical Computer Science, 2014, 548, pp.25-53. ⟨10.1016/j.tcs.2014.06.036⟩. ⟨hal-01065761⟩

Collections

INRIA INRIA2
95 Consultations
236 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More