Pseudo-linear algebra (also known as Ore algebra) is the study of common properties and common mathematical abstraction of linear functional equations such as differential and difference equations. The objects of study in pseudo-linear algebra are skew polynomials, which represent single equations, and pseudo-linear operators, which represent systems.

Algebraic algorithms have been generalized to arbitrary pseudo-linear equations. This includes algorithms to:

- Uncouple systems of linear functional equations

- Construct the minimal annihilator

- Solve the accurate integration problem

- Find the d'Alembertian solution of linear functional equations

The OreTools package is designed to perform the basic arithmetic in Ore algebra. The routines are classified as follows.

-  Define an Ore ring: SetOreRing

-  Perform basic arithmetic: Add, Minus, ScalarMultiply, Multiply, Quotient, Remainder, Euclidean, ExtendedGCD, GCD, LCM, Primitive, Content, Normalize, MonicAssociate

-  Define an adjoint Ore ring and construct an adjoint Ore polynomial: AdjointRing, AdjointOrePoly

-  Apply an Ore operator to a given expression: Apply

-  Convert between different representations by functions in the submodule Converters: Converters:-FromOrePolyToLinearEquation, Converters:-FromLinearEquationToOrePoly, Converters:-FromOrePolyToPoly, Converters:-FromPolyToOrePoly

-  Perform fraction-free computation by functions in the submodule FractionFree: FractionFree:-RightPseudoRemainder, FractionFree:-RightPseudoQuotient, FractionFree:-RightEuclidean

-  Perform certain mathematical constructions by functions in the submodule MathOperations: MathOperations:-AccurateIntegration, MathOperations:-HilbertTwistReduction, MathOperations:-InverseOfHilbertTwistReduction

-  Perform modular arithmetic by functions in the submodule Modular: Modular:-Add, Modular:-Minus, Modular:-ScalarMultiply, Modular:-Multiply, Modular:-RightRemainder, Modular:-RightQuotient, Modular:-RightPseudoRemainder, Modular:-RightPseudoQuotient, Modular:-RightEuclidean, Modular:-FractionFreeRightEuclidean, Modular:-GCRD, Modular:-LCLM

-  Access properties of a given algebra by functions in the submodule Properties: Properties:-GetRingName, Properties:-GetVariable, Properties:-GetSigma, Properties:-GetSigmaInverse, Properties:-Getdelta, Properties:-GetTheta1

-  Compute various coefficients and degrees of  an Ore polynomial by functions in the submodule Utility: Utility:-Coefficient, Utility:-Coefficients, Utility:-LeadingCoefficient, Utility:-TrailingCoefficient, Utility:-Degree, Utility:-LowDegree, Utility:-VariableDegree

-  Useful tools: Converters:-AddConversionRule, Utility:-RandOrePoly, Consequences:-MinimalEquation, Consequences:-ReducedSystem

For a brief review of pseudo-linear algebra (also known as Ore algebra), see OreAlgebra.

For a description of the OrePoly structure, which is used to represent an Ore polynomial, see OrePoly.

The main difference between the OreTools and Ore_algebra packages is that, in the OreTools package, the skew polynomial rings are defined over a field, whereas in the Ore_algebra package, the skew polynomial rings are defined over a ring.

Each command in the OreTools package can be accessed by using either the long form or the short form of the command name in the command calling sequence.

The long form, OreTools:-command, is always available. The short form can be used after loading the package.

The following is a list of available commands.

To display the help page for a particular OreTools command, see Getting Help with a Command in a Package.

The following is a list of OreTools subpackages.

$\mathrm{with}\left(\mathrm{OreTools}\right)$

$\left[\mathrm{Add}\,\mathrm{AdjointOrePoly}\,\mathrm{AdjointRing}\,\mathrm{Apply}\,\mathrm{Consequences}\,\mathrm{Content}\,\mathrm{Converters}\,\mathrm{Convertors}\,\mathrm{Euclidean}\,\mathrm{ExtendedGCD}\,\mathrm{FractionFree}\,\mathrm{GCD}\,\mathrm{LCM}\,\mathrm{MathOperations}\,\mathrm{Minus}\,\mathrm{Modular}\,\mathrm{MonicAssociate}\,\mathrm{Multiply}\,\mathrm{Normalize}\,\mathrm{ParametricGCRD}\,\mathrm{Primitive}\,\mathrm{Properties}\,\mathrm{Quotient}\,\mathrm{Remainder}\,\mathrm{ScalarMultiply}\,\mathrm{SetOreRing}\,\mathrm{Utility}\right]$

$A≔\mathrm{SetOreRing}\left(n\,'\mathrm{shift}'\right)$

$A≔\mathrm{UnivariateOreRing}\left(n\,\mathrm{shift}\right)$

$\mathrm{Ore1}≔\mathrm{OrePoly}\left(-\frac{n}{n-1}\,-\frac{-5n+n^2+3}{n-1}\,n-3\right)$

$\mathrm{Ore1}≔\mathrm{OrePoly}\left(-\frac{n}{n-1}\,-\frac{n^2-5n+3}{n-1}\,n-3\right)$

$\mathrm{Ore2}≔\mathrm{OrePoly}\left(-n\,3n-n^2-1\,{\left(n-1\right)}^2\right)$

$\mathrm{Ore2}≔\mathrm{OrePoly}\left(-n\,-n^2+3n-1\,{\left(n-1\right)}^2\right)$

$\mathrm{GCD}\left['\mathrm{right}'\right]\left(\mathrm{Ore1}\,\mathrm{Ore2}\,A\right)$

$\mathrm{OrePoly}\left(\mathrm{-1}\,1\right)$

$\mathrm{GCD}\left['\mathrm{left}'\right]\left(\mathrm{Ore1}\,\mathrm{Ore2}\,A\right)$

$\mathrm{OrePoly}\left(1\right)$

$\mathrm{LCM}\left['\mathrm{left}'\right]\left(\mathrm{Ore1}\,\mathrm{Ore2}\,A\right)$

$\mathrm{OrePoly}\left(-\frac{n+1}{n\left(n^2-3n+2\right)}\,-\frac{2n^3-4n^2-3n+3}{n^2\left(n^2-3n+2\right)}\,-\frac{n^3-4n^2+n+3}{n^2\left(n-2\right)}\,1\right)$

$\mathrm{LCM}\left['\mathrm{right}'\right]\left(\mathrm{Ore1}\,\mathrm{Ore2}\,A\right)$

$\mathrm{OrePoly}\left(\frac{\left(n^6-20n^5+152n^4-560n^3+1036n^2-880n+271\right)n}{n^9-35n^8+524n^7-4376n^6+22246n^5-70218n^4+133143n^3-134227n^2+43670n+18200}\,\frac{2n\left(n^7-18n^6+122n^5-388n^4+550n^3-118n^2-465n+316\right)}{\left(n^4-17n^3+106n^2-288n+288\right)\left(n^5-9n^4+21n^3-5n^2-31n+31\right)}\,\frac{n\left(n^8-17n^7+99n^6-206n^5-92n^4+988n^3-1503n^2+1029n-299\right)}{\left(n^3-8n^2+21n-18\right)\left(n^5-4n^4-5n^3+14n^2-9n+8\right)\left(n-5\right)}\,-\frac{2n\left(n^7-6n^6-5n^5+66n^4-49n^3-60n^2-32n+46\right)}{\left(n^2-4n+4\right)\left(n^5+n^4-11n^3-15n^2-7n+5\right)\left(n-4\right)}\,1\right)$

$A≔\mathrm{SetOreRing}\left(\left[x\,q\right]\,'\mathrm{qshift}'\right)$

$A≔\mathrm{UnivariateOreRing}\left(x\,\mathrm{qshift}\right)$

$\mathrm{Poly}≔\mathrm{OrePoly}\left(-q\left(1-qx\right)\,1\right)$

$\mathrm{Poly}≔\mathrm{OrePoly}\left(-q\left(-qx+1\right)\,1\right)$

$\mathrm{Apply}\left(\mathrm{Poly}\,s\left(x\right)\,A\right)$

$-q\left(-qx+1\right)s\left(x\right)+s\left(qx\right)$

$\mathrm{Poly1}≔\mathrm{AdjointOrePoly}\left(\mathrm{Poly}\,A\right)$

$\mathrm{Poly1}≔\mathrm{OrePoly}\left(q\left(qx-1\right)\,1\right)$

$\mathrm{Apply}\left(\mathrm{Poly1}\,s\left(x\right)\,A\right)$

$q\left(qx-1\right)s\left(x\right)+s\left(qx\right)$

Abramov, S. A.; Le, H. Q.; and Li, Z. "OreTools: a computer algebra library for univariate Ore polynomial rings." Technical Report CS-2003-12, School of Computer Science, University of Waterloo, 2003.

Bronstein, M., and Petkovsek, M. "An introduction to pseudo-linear algebra" Theoretical Computer Science. Vol. 157, (1996): 3-33.

Ore, O. "Theory of non-commutative polynomials." Annals of Mathematics. Vol. 34, (1933): 480-508.