2023 - T3 - WS3 - Computer algebra for functional equations in combinatorics and physics

Collection 2023 - T3 - WS3 - Computer algebra for functional equations in combinatorics and physics

Organizer(s) Bostan, Alin ; Bouttier, Jérémie ; Cluzeau, Thomas ; Di Vizio, Lucia ; Krattenthaler, Christian ; Lairez, Pierre ; Maillard, Jean-Marie
Date(s) 04/12/2023 - 08/12/2023
linked URL https://indico.math.cnrs.fr/event/8115/
8 17

Submodule approach to creative telescoping

By Mark van Hoeij

This talk 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 $H$ in a D-module $M$ . The main idea is to look for submodules of $M$. For a non-trivial submodule $N$, constructing the minimal operator $R$ of the image of $H$ in $M / N$ gives a right-factor of $L$ in $D$. Then $L = L′R$ where $L′$ is the telescoper of $R(H)$. To expedite computing $L′$, compute the action of $D$ on a natural basis of $N$, then obtain the telescoper $L′$ for $R(H)$ 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 of submodules $N_1, \ldots, N_k$ . Then $L' = \text{LCLM}(L_1, \ldots, L_k)$ where $L_i$ is the telescoper of the projection of $R(H)$ on $N_i$. An LCLM can greatly increase the degrees of the coefficients, so $L′$ and hence $L$ can be much larger than the factors $L_1, \ldots, L_k$ and $R$. Examples show that computing each factor $L_i$ and $R$ separately can save a lot of CPU time compared to computing the full telescoper $L$ all at once with standard creative telescoping.

Information about the video

Citation data

  • DOI 10.57987/IHP.2023.T3.WS3.007
  • Cite this video van Hoeij, Mark (05/12/2023). Submodule approach to creative telescoping. IHP. Audiovisual resource. DOI: 10.57987/IHP.2023.T3.WS3.007
  • URL https://dx.doi.org/10.57987/IHP.2023.T3.WS3.007

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback