主题
Search

格约化

为给定格找到一组具有特定特殊性质的约化基向量的过程。格约化算法被用于许多现代数论应用中，包括发现圆周率的流式算法。尽管确定最短基可能是一个 NP-完全问题，但诸如 LLL 算法之类的算法可以在多项式时间内找到一个短基，并保证最坏情况下的性能。

格约化的 LLL 算法在 Wolfram 语言中使用以下函数实现LatticeReduce. RootApproximant[x, n] 也调用此例程，以找到一个次数最多为 n 的代数数，使得 x 是该数的近似零点。

当用于查找整数关系时，该算法的典型输入由一个增广的 n×n 单位矩阵组成，其最后一列的条目由 n 个元素（乘以一个大的正常数 w 以惩罚不求和为零的向量）组成，这些元素之间正在寻找关系。例如，如果已知存在形式如下的等式

a_1x+a_2y+a_3z=0

是已知存在的，那么对矩阵进行格约化

m=[1 0 0 wx; 0 1 0 wy; 0 0 1 wz]

将产生一个新的矩阵，其中最后一列中的一个或多个条目接近于零。然后，该行给出恒等式的系数 {a_1,a_2,a_3,0}。Borwein 和 Corless (1999) 以及 Borwein 和 Lisonek (2000) 都说明了一个格约化计算示例。

以下给出了在 Wolfram 语言中查找整数关系的示例实现，例如可以调用为：TranscendentalRecognize[N[Pi + E], {Pi, E, EulerGamma}]. 

TranscendentalRecognize[n_, basis_] := Module[
  {c, d, digs, e, id, lat, powerten, r, s, vals},
  {d, e} = RealDigits[n];
  s = Sign[n];
  c = FromDigits[d];
  powerten = 10^(Length[d] - e);
  digs = (RealDigits[N[#1, -e + Length[d] + 5]]&) /@ basis;
  r = (FromDigits[Take[First[#1], -e + Last[#1] + Length[d]]]&) /@
    digs;
  lat = Transpose[
    Append[IdentityMatrix[Length[basis] + 2],
     Flatten[{powerten, r, c}]]];
  vals = Take[First[LatticeReduce[lat]], Length[basis] + 2];
  Expand[-((s (Take[vals, {2, -2}].basis + First[vals]))/Last[vals])]]

另请参阅

格拉姆-施密特正交化, 整数关系, LLL 算法, PSLQ 算法

使用 Wolfram|Alpha 探索

参考文献

Borwein, J. M. and Corless, R. M. "Emerging Tools for Experimental Mathematics." Amer. Math. Monthly 106, 899-909, 1999.Borwein, J. M. and Lisonek, P. "Applications of Integer Relation Algorithms." Disc. Math. 217, 65-82, 2000.Cohen, H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, 1993.Coster, M. J.; Joux, A.; LaMacchia, B. A.; Odlyzko, A. M.; Schnorr, C. P.; and Stern, J. "Improved Low-Density Subset Sum Algorithms." Comput. Complex. 2, 111-128, 1992.Hastad, J.; Just, B.; Lagarias, J. C.; and Schnorr, C. P. "Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers." SIAM J. Comput. 18, 859-881, 1988.Lagarias, J. C.; Lenstra, H. W. Jr.; and Schnorr, C. P. "Korkin-Zolotarev Bases and Successive Minima of a Lattice and Its Reciprocal Lattice." Combinatorica 10, 333-348, 1990.Schnorr, C. P. "A More Efficient Algorithm for Lattice Basis Reduction." J. Algorithms 9, 47-62, 1988.Schnorr, C. P. and Euchner, M. "Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems." In Fundamentals of Computation Theory: Proceedings of the 8th International Conference, Fct '91 Gosen, Germany, September 9-13, 1991. Berlin: Springer-Verlag, pp. 68-85, 1991.

在 Wolfram|Alpha 中被引用

格约化

请引用为

韦斯坦因，埃里克·W. "格约化。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/LatticeReduction.html

主题分类