主題
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 演算法

使用 探索

參考文獻

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.

在 中被引用

格約化

請引用為

韋斯坦因，埃裡克·W. "格約化。" 來自 —— 資源。 https://mathworld.tw/LatticeReduction.html

主題分類