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

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01065761
Contributor : Philippe Dumas <>
Submitted on : Thursday, September 18, 2014 - 3:30:10 PM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM
Long-term archiving on: Friday, December 19, 2014 - 1:45:52 PM

Files

Identifiers

Collections

Citation

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

Share

Metrics

Record views

314

Files downloads

467