Lattice Reduction
المؤلف:
Borwein, J. M. and Corless, R. M
المصدر:
"Emerging Tools for Experimental Mathematics." Amer. Math. Monthly 106
الجزء والصفحة:
...
20-7-2020
2110
Lattice Reduction
The process of finding a reduced set of basis vectors for a given lattice having certain special properties. Lattice reduction algorithms are used in a number of modern number theoretical applications, including in the discovery of a spigot algorithm for pi. Although determining the shortest basis is possibly an NP-complete problem, algorithms such as the LLL algorithm can find a short basis in polynomial time with guaranteed worst-case performance.
The LLL algorithm of lattice reduction is implemented in the Wolfram Language using the function LatticeReduce. RootApproximant[x, n] also calls this routine in order to find a algebraic number of degree at most 
such that 
is an approximate zero of the number.
When used to find integer relations, a typical input to the algorithm consists of an augmented 
identity matrix with the entries in the last column consisting of the 
elements (multiplied by a large positive constant 
to penalize vectors that do not sum to zero) between which the relation is sought. For example, if an equality of the form
is known to exist, then doing a lattice reduction on the matrix
will produce a new matrix in which one or more entries in the last column being close to zero. This row then gives the coefficients ![<span style=]()
{a_1,a_2,a_3,0}" src="https://mathworld.wolfram.com/images/equations/LatticeReduction/Inline6.gif" style="height:15px; width:80px" /> of the identity. An example lattice reduction calculation is illustrated in both Borwein and Corless (1999) and Borwein and Lisonek (2000).
An example implementation of integer relation finding in the Wolfram Language is given by the following, which can be called as, for example, TranscendentalRecognize[N[Pi + E], ![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/LatticeReduction/Inline7.gif" style="height:15px; width:5px" />Pi, E, EulerGamma![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/LatticeReduction/Inline8.gif" style="height:15px; width:5px" />].
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])]]
REFERENCES:
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.
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
