论文标题
一阶线性复发系统的分母界限
A Family of Denominator Bounds for First Order Linear Recurrence Systems
论文作者
论文摘要
对于线性复发系统，通过计算结合内容或分母结合的内容，查找有理解决方案的问题将减少到计算多项式解决方案的问题。文献中有几个范围。最锐利的结合导致较低程度的多项式溶液，但是该优势不必补偿计算该结合的时间。 为了在界限与获得CPU的时间之间取得最佳平衡，我们将为一个界限提供一个界限。当$ J = 1 $，类似于（van Hoeij，1998年）时，这个家族的$ j $'TH与（Abramov，Barkatou，1998年）相似，当$ J $很大，并且以$ j $的中间值的形式进行新颖，这在夏普和CPU时间之间提供了最佳余额。 我们内容范围的设置是系统$τ（y）=我的$，其中$τ$是UFD的自动形态，而$ m $是可逆矩阵，其分数字段中有条目。此设置包括Shift Case，$ Q $ SHIFT案例，多基础案例等。我们提供两个版本，一个全局版本和一个分别界限每个条目的版本。
For linear recurrence systems, the problem of finding rational solutions is reduced to the problem of computing polynomial solutions by computing a content bound or a denominator bound. There are several bounds in the literature. The sharpest bound leads to polynomial solutions of lower degrees, but this advantage need not compensate for the time spent on computing that bound. To strike the best balance between sharpness of the bound versus CPU time spent obtaining it, we will give a family of bounds. The $J$'th member of this family is similar to (Abramov, Barkatou, 1998) when $J=1$, similar to (van Hoeij, 1998) when $J$ is large, and novel for intermediate values of $J$, which give the best balance between sharpness and CPU time. The setting for our content bounds are systems $τ(Y) = MY$ where $τ$ is an automorphism of a UFD, and $M$ is an invertible matrix with entries in its field of fractions. This setting includes the shift case, the $q$-shift case, the multi-basic case and others. We give two versions, a global version, and a version that bounds each entry separately.
