论文标题
在带有热带Gröbner基地的FGLM算法上
On FGLM Algorithms with Tropical Gröbner bases
论文作者
论文摘要
让K为配备估值的领域。可以用gr {Ö} Bner基础的理论来定义k的热带品种，并考虑到K的估值。由于估值的使用，热带gr {Ö} bner基地的理论已被证明为在P-Adic域而不是更稳定的类别grane grantic Grane的P-Adic领域提供了计算的设置。在本文中，我们调查了如何将订购算法的FGLM变化转换为热带设置。由于考虑了多项式系数的估值，因此经典的FGLM算法的增量方式（单元单体模拟单体）可以计算乘法矩阵，并且无法将基矩阵的更改完全转移到热带环境中。我们通过开发新的线性代数算法并将其应用于我们的新热带FGLM算法来缓解此问题。动机是双重的。首先，为了计算热带品种，通常会经过针对不同权重的许多热带gr {Ö} bner碱的计算（然后是变化的术语订单）。对于尺寸0的理想，热带FGLM算法提供了一种有效的方法，可以从热带gr {Ö} Bner基础上从一个重量到一个重量，从而增加一个重量。其次，可以将FGLM策略从热带gr {Ö} Bner基础上进行到经典的gr {Ö} Bner基础。我们提供的工具可以将热带gr {Ö} bner基础的稳定计算与[RV16]的FGLM的P-ADIC稳定变体进行稳定计算，以计算词典或形状位置基础。我们所有的算法都已将其实施到Sagemath中。我们提供数值示例来说明时间复杂性。然后，我们说明我们的策略对P-ADIC数值计算的稳定性的优势。
Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gr{ö}bner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical Gr{ö}bner bases has proved to provide settings for computations over polynomial rings over a p-adic field that are more stable than that of classical Gr{ö}bner bases. In this article, we investigate how the FGLM change of ordering algorithm can be adapted to the tropical setting. As the valuations of the polynomial coefficients are taken into account, the classical FGLM algorithm's incremental way, monomo-mial by monomial, to compute the multiplication matrices and the change of basis matrix can not be transposed at all to the tropical setting. We mitigate this issue by developing new linear algebra algorithms and apply them to our new tropical FGLM algorithms. Motivations are twofold. Firstly, to compute tropical varieties, one usually goes through the computation of many tropical Gr{ö}bner bases defined for varying weights (and then varying term orders). For an ideal of dimension 0, the tropical FGLM algorithm provides an efficient way to go from a tropical Gr{ö}bner basis from one weight to one for another weight. Secondly, the FGLM strategy can be applied to go from a tropical Gr{ö}bner basis to a classical Gr{ö}bner basis. We provide tools to chain the stable computation of a tropical Gr{ö}bner basis (for weight [0,. .. , 0]) with the p-adic stabilized variants of FGLM of [RV16] to compute a lexicographical or shape position basis. All our algorithms have been implemented into SageMath. We provide numerical examples to illustrate time-complexity. We then illustrate the superiority of our strategy regarding to the stability of p-adic numerical computations.
