Submodule approach to creative telescoping
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929356222234624 |
|---|---|
| author | van Hoeij, Mark |
| author_facet | van Hoeij, Mark |
| contents | This paper proposes ideas to speed up the process of creative telescoping, particularly when the telescoper is reducible. One can interpret telescoping as computing an annihilator $L \in D$ for an element $m$ in a $D$-module $M$. The main idea is to look for submodules of $M$. If $N$ is a non-trivial submodule of $M$, constructing the minimal operator $R$ of the image of $m$ in $M/N$ gives a right-factor of $L$ in $D$. Then $L = L' R$ where the left-factor $L'$ is the telescoper of $R(m) \in N$. To expedite computing $L'$, compute the action of $D$ on a natural basis of $N$, then obtain $L'$ with a cyclic vector computation.
The next main idea is that when $N$ has automorphisms, use them to construct submodules. An automorphism with distinct eigenvalues can be used to decompose $N$ as a direct sum $N_1 \oplus \cdots \oplus N_k$. Then $L'$ is the LCLM (Least Common Left Multiple) of $L_1, \ldots, L_k$ where $L_i$ is the telescoper of the projection of $R(m)$ on $N_i$. An LCLM can greatly increase the degrees of coefficients, so $L'$ and $L$ can be much larger expressions than the factors $L_1,\ldots,L_k$ and $R$. Examples show that computing each factor $L_i$ and $R$ seperately can save a lot of CPU time compared to computing $L$ in expanded form with standard creative telescoping. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_08455 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Submodule approach to creative telescoping van Hoeij, Mark Symbolic Computation 39A04 G.2.1 This paper proposes ideas to speed up the process of creative telescoping, particularly when the telescoper is reducible. One can interpret telescoping as computing an annihilator $L \in D$ for an element $m$ in a $D$-module $M$. The main idea is to look for submodules of $M$. If $N$ is a non-trivial submodule of $M$, constructing the minimal operator $R$ of the image of $m$ in $M/N$ gives a right-factor of $L$ in $D$. Then $L = L' R$ where the left-factor $L'$ is the telescoper of $R(m) \in N$. To expedite computing $L'$, compute the action of $D$ on a natural basis of $N$, then obtain $L'$ with a cyclic vector computation. The next main idea is that when $N$ has automorphisms, use them to construct submodules. An automorphism with distinct eigenvalues can be used to decompose $N$ as a direct sum $N_1 \oplus \cdots \oplus N_k$. Then $L'$ is the LCLM (Least Common Left Multiple) of $L_1, \ldots, L_k$ where $L_i$ is the telescoper of the projection of $R(m)$ on $N_i$. An LCLM can greatly increase the degrees of coefficients, so $L'$ and $L$ can be much larger expressions than the factors $L_1,\ldots,L_k$ and $R$. Examples show that computing each factor $L_i$ and $R$ seperately can save a lot of CPU time compared to computing $L$ in expanded form with standard creative telescoping. |
| title | Submodule approach to creative telescoping |
| topic | Symbolic Computation 39A04 G.2.1 |
| url | https://arxiv.org/abs/2401.08455 |