
Calling Sequence


UniversalDenominator(sys, vars, opts)
UniversalDenominator(A, b, x, case, opts)
UniversalDenominator(A, x, case, opts)


Parameters


sys



list of equations; linear functional system

vars



list of function variables such as [y1(x), y2(x), ...]; variables to solve for

A



Matrix with rational elements

b



Vector with rational elements

x



independent variable

case



name indicating the case of the system; one of differential, difference, or qdifference

opts



optional arguments of the form 'keyword'='value', where keyword is either hybrid (for differential systems only) or refined





Description


•

The UniversalDenominator command returns a universal denominator of a given linear functional system of equations with polynomial coefficients (that is, a denominator which is a multiple of the denominator of any component of any rational solution of the given system). If a universal denominator cannot be found then FAIL is returned.


The system parameter is entered either in list form (a list of equations sys and a list of function variables vars to solve for), or in matrix form (matrix A, vector b, and the independent variable x, where the vector b is optional).


The matrix form specifies the system $\mathrm{Ly}\left(x\right)=\mathrm{Ay}\left(x\right)+b$, where L is an operator (either differential, difference, or qdifference), $y\left(x\right)$ is a vector of the functions to solve for, A is a rational matrix, and b is a rational vector (righthand side).


For the matrix from of the calling sequence, the case of the system must be specified as one of 'differential', 'difference', or 'qdifference'. If b is not specified, the system is assumed to be homogeneous.

•

The function works differently depending on the case of the given system.


In the differential case, the singularities of the system are computed. If 'hybrid'=false is specified then for each singularity the function rewrites the given system in the singularity point and constructs the corresponding matrix recurrence system. Then it bounds the corresponding pole order using LinearFunctionalSystems[MatrixTriangularization] for the leading matrix of this matrix recurrence system as LinearFunctionalSystems[PolynomialSolution] does for the polynomial solution degree using LinearFunctionalSystems[MatrixTriangularization] for the trailing matrix. The universal denominator is the product of the bounded poles that are found. If 'hybrid'=true is specified (the default) then a hybrid method is used, which combines the above approach with an other one based on an algorithm by Bronstein & Trager working on regular singularities. The latter algorithm (with some heuristic added) allows to separate regular singularities (though some of them may be missed). For these separated regular singularities a classical method is used, and the rest of the singularities are processed by the above approach based on LinearFunctionalSystems[MatrixTriangularization].


In the difference case, the function builds polynomials which are analogous to the leading and trailing coefficient of the recurrence corresponding to the difference equation in the scalar case. Then it uses the dispersion algorithm by S.A. Abramov for finding the denominator. The algorithm for computing the dispersion of two polynomials by Wright and Man is used.


In qdifference case, the combinations of the above approaches is used. At zero (0), the function bounds the order of the pole and at all other points the qanalog of the dispersion algorithm is applied. The qextension of the algorithm for computing the qdispersion of two polynomials by Wright and Man is used.

•

This function returns the inverse value of the universal denominator.

•

If 'refined'=true is specified then the universal denominator is refined for every component of the solution. In this case, the procedure returns a componentwise sequence $\frac{1}{\mathrm{u1}},\frac{1}{\mathrm{u2}},...,\frac{1}{\mathrm{un}}$ where $\mathrm{ui}$ is a multiple of the denominator of ith component of any rational solution of the system. Each element of the sequence can be simpler then the common universal denominator. Here the algorithm by S.A. Abramov and S.P. Polyakov is used.

•

If the number of linear independent equations of the system is less than the number of the function variables then the universal denominator cannot be found and FAIL is returned. In the case it is possible to extend the system by additional equations, in particular giving the desirable value of some of the function variables (see example).

•

The given system should be of first order. (This is always true if the system is given in the matrix form.)

•

This function is part of the LinearFunctionalSystems package; so it can be used in the form UniversalDenominator(..) only after executing the command with(LinearFunctionalSystems). However, it can always be accessed through the long form of the command by using the form LinearFunctionalSystems[UniversalDenominator](..).



Examples


>

with(LinearFunctionalSystems):

>

sys := [x^2*y2(x) + 2*x^2*y1(x) + 4*y1(x)*x  y1(x + 1)*x^2  4*y1(x + 1)*x + 2*y1(x)  4*y1(x + 1), y2(x + 1)  y1(x)]:

>

UniversalDenominator(sys, vars);

$\frac{{1}}{{\left({x}{+}{1}\right)}^{{2}}{}{{x}}^{{2}}}$
 (1) 
>

sys := [x*diff(y1(x),x)2*y1(x)y2(x)]:

>

u := UniversalDenominator(sys, vars);

${u}{\u2254}{\mathrm{FAIL}}$
 (2) 
>

sys := [op(sys),y2(x)=1/x^3]:

>

UniversalDenominator(sys, vars);

$\frac{{1}}{{{x}}^{{3}}}$
 (3) 
>

sys := [x*(x + 3)*(2*x + 3)*y1(x + 1)  (x + 2)*(x  1)*(2*x  1)*y2(x),
y2(x + 1)  y1(x)];

${\mathrm{sys}}{\u2254}\left[{x}{}\left({x}{+}{3}\right){}\left({2}{}{x}{+}{3}\right){}{\mathrm{y1}}{}\left({x}{+}{1}\right){}\left({x}{+}{2}\right){}\left({x}{}{1}\right){}\left({2}{}{x}{}{1}\right){}{\mathrm{y2}}{}\left({x}\right){\,}{\mathrm{y2}}{}\left({x}{+}{1}\right){}{\mathrm{y1}}{}\left({x}\right)\right]$
 (4) 
>

UniversalDenominator(sys,[y1(x), y2(x)]);

$\frac{{1}}{\left({x}{+}{2}\right){}\left({x}{+}{1}\right){}{x}{}\left({x}{}{1}\right){}\left({2}{}{x}{+}{1}\right){}\left({2}{}{x}{}{1}\right)}$
 (5) 
>

UniversalDenominator(sys, [y1(x), y2(x)], 'refined' = true);

$\frac{{1}}{{x}{}\left({x}{+}{2}\right){}\left({2}{}{x}{+}{1}\right)}{,}\frac{{1}}{\left({x}{}{1}\right){}\left({x}{+}{1}\right){}\left({2}{}{x}{}{1}\right)}$
 (6) 


References



Abramov, S. A. "EGEliminations." Journal of Difference Equations and Applications. (1999): 393433.


Abramov, S. A. "Rational Solutions of Linear Difference and Qdifference Equations with Polynomial Coefficients." Programming and Computer Software, Vol. 21(6). (1995): 273278.


Bronstein, M., and Trager, B. M. "A Reduction for Regular Differential Systems." In Proceedings of MEGA '03, CDROM. 2003.


Man, YiuKwong, and Wright, Francis J. "Fast Polynomial Dispersion Computation and its Application to Indefinite Summation." In Proceedings of ISSAC '94, pp. 175180. Edited by Malcolm MacCallum. New York: ACM Press, 1994.


Abramov, S. A., and Polyakov, S.P. "Refined universal denominators" Programming and Computer Software, (2007), to appear.



