| Popis: |
The notion of integrality known for algebraic numbers and algebraic functions has been extended to D-finite functions by Kauers and Koutschan in 2015. One aim of the present thesis is to further extend this notion to the case of P-recursive sequences. In order to do so, we formulate a general algorithm for finding all integral elements of valued vector spaces and then show that this algorithm includes not only the algebraic and D-finite cases but also covers the case of P-recursive sequences. A second aim of the thesis is to explore the applications of integral bases in symbolic integration via creative telescoping. Bronstein’s lazy Hermite reduction is a symbolic integration technique that reduces algebraic functions to integrands with only simple poles without the prior computation of an integral basis. We sharpen the lazy Hermite reduction by combining it with the polynomial reduction to solve the decomposition problem of algebraic functions. The sharpened reduction is then used to design a reduction-based telescoping algorithm for algebraic functions in two variables. Trager’s Hermite reduction solved the integration problem for algebraic functions via integral bases, which was extended to Fuchsian D-finite functions. We remove the Fuchsian restriction and present Hermite reduction for general D-finite functions. It reduces the pole orders of integrands at finite places, but may not reduce to simple poles as in the algebraic and Fuchsian D-finite cases. Instead of using the polynomial reduction, we develop Hermite reduction at infinity to reduce the pole order of D-finite functions at infinity via local integral bases at infinity. Combining Hermite reduction at finite places and at infinity, we obtain a new reduction-based telescoping algorithm for D-finite functions in two variables. Im Jahr 2015 wurde der Begriff der Integralität, der für algebraische Zahlen und Funktionen bekannt ist, von Kauers und Koutschan auf D-finite Funktionen erweitert. Ein Ziel der vorliegenden Arbeit ist die weitere Erweiterung dieses Begriffs auf P-finite Folgen. Um dies zu erreichen, formulieren wir einen allgemeinen Algorithmus zum Auffinden integraler Elemente in bewerteten Vektorräumen und zeigen dann, dass dieser Algorithmus nicht nur den algebraischen und den D-finiten Fall sondern auch den Fall von P-finiten Folgen abdeckt. Ein zweites Ziel dieser Arbeit ist die Untersuchung von Anwendungen von Integralbasen für Integrationsalgorithmen im Zusammenhang mit “creative telescoping”. Bronsteins “lazy Hermite reduction” ist eine Technik zum symbolischen Integrieren, die algebraische Funktionen auf Integranden mit nur einfachen Polen reduziert ohne zuvor eine Integralbasis zu berechnen. Wir verschärfen die “lazy Hermite reduction”, indem wir sie mit polynomieller Reduktion kombinieren, und erhalten so eine Lösung des Zerlegungsproblems für algebraische Funktionen. Die verschärfte Reduktion wird dann benutzt, um einen reduktions-basierten Algorithmus für “creative telescoping” für algebraische Funktionen in zwei Variablen zu entwerfen. Tragers Hermite-Reduktion löste das Integrationsproblem für algebraische Funktionen mithilfe von Integralbasen und wurde auf den Fuchsschen D-finiten Fall erweitert. Wir eliminieren die Einschränkung auf die Fuchssche Klasse und geben eine Hermite-Reduktion für beliebige D-finite Funktionen an. Diese reduziert Pol-Ordnungen von Integranden an endlichen Stellen, erreicht aber im allgemeinen keine einfachen Pole wie im algebraischen oder im Fuchsschen D-finiten Fall. Anstelle der polynomiellen Reduktion entwickeln wir eine Hermite-Reduktion bei unendlich, um die Pol-Ordnung einer D-finiten Funktion bei unendlich mithilfe einer lokalen Integralbasis bei unendlich zu reduzieren. Durch die Kombination der Hermite-Reduktionen an endlichen Stellen und bei unendlich erhalten wir einen neuen reduktions-basierten Algorithmus für D-finite Funktionen in zwei Variablen. Author Lixin Du Dissertation Universität Linz 2022 |
