主題
Search

LLL 演算法

一種格約化演算法，以發現者 Lenstra、Lenstra 和 Lovasz (1982) 的名字命名，該演算法產生“短”向量的格基。Lenstra 等人 (1982) 注意到，該演算法可以用於獲得單變數多項式的因子，這相當於確定整數關係。然而，該演算法的這種應用，後來成為其主要應用之一，在最初的論文中並未強調。

有關 LLL 演算法的複雜度分析，請參見 Storjohann (1996)。

Wolfram 語言命令LatticeReduce[矩陣] 實現了 LLL 演算法以執行格約化。Wolfram 語言的實現要求輸入由有理陣列成，因此Rationalize可能需要首先呼叫。

最近，已經開發了其他演算法，例如 PSLQ，它可能比 LLL 快得多，用於查詢整數關係。PSLQ 實現其效能是因為巧妙的技術允許在許多中間步驟中使用機器算術，而 LLL 必須使用適度的精度（雖然通常不如 HJLS 演算法）。

另請參見

Ferguson-Forcade 演算法, HJLS 演算法, 整數關係, 格約化, PSLQ 演算法, PSOS 演算法

使用 探索

參考文獻

Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; 和 Moll, V. H. "整數關係檢測"。§2.2 in 《實驗數學實踐》。Wellesley, MA: A K Peters, pp. 29-31, 2007。Borwein, J. 和 Bailey, D. 《實驗數學：21 世紀的似真推理》。Wellesley, MA: A K Peters, pp. 51-52, 2003。Borwein, J. M. 和 Corless, R. M. "實驗數學的新興工具"。Amer. Math. Monthly 106, 899-909, 1999。Borwein, J. M. 和 Lisonek, P. "整數關係演算法的應用"。Disc. Math. 217, 65-82, 2000。實驗與構造數學中心。"整數關係"。http://www.cecm.sfu.ca/projects/IntegerRelations/。Cohen, H. 《計算代數數論課程》。New York: Springer-Verlag, 1993。Lenstra, A. K.; Lenstra, H. W.; 和 Lovasz, L. "有理係數多項式的因式分解"。Math. Ann. 261, 515-534, 1982。Matthews, K. "Keith Matthews 的 LLL 頁面"。http://www.numbertheory.org/lll.html。Mignotte, M. 《計算機代數數學》。New York: Springer-Verlag, 1991。Storjohann, A. "更快的整數格基約化演算法"。技術報告 249. Zurich, Switzerland: Department Informatik, ETH. 1996 年 7 月 30 日。Zimmerman, P. "使用精確多精度算術的 LLL"。http://www.loria.fr/~zimmerma/free/lll.c。

在 中引用

LLL 演算法

請引用為

Weisstein, Eric W. "LLL 演算法"。來自 Web 資源。https://mathworld.tw/LLLAlgorithm.html

主題分類