arXiv Open Access 2018

A fast algorithm for solving linearly recurrent sequences

Seung Gyu Hyun Stephen Melczer Catherine St-Pierre

Lihat Sumber

Abstrak

We present an algorithm which computes the $D^{th}$ term of a sequence satisfying a linear recurrence relation of order $d$ over a field $K$ in $O( \mathsf{M}(\bar d)\log(D) + \mathsf{M}(d)\log(d))$ operations in $K$, where $\bar d \leq d$ is the degree of the squarefree part of the annihilating polynomial of the recurrence and $\mathsf{M}$ is the cost of polynomial multiplication in $K$. This is a refinement of the previously optimal result of $O( \mathsf{M}(d)\log(D) )$ operations, due to Fiduccia.

Topik & Kata Kunci

cs.SC math.CO

Penulis (3)

Seung Gyu Hyun

Stephen Melczer

Catherine St-Pierre

Format Sitasi

APA MLA BibTeX

Hyun, S.G., Melczer, S., St-Pierre, C. (2018). A fast algorithm for solving linearly recurrent sequences. https://arxiv.org/abs/1806.03554

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2018
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓