|
|
14#
大 中
小 發表於 2017-12-31 13:44 只看該作者
6-2.改進LLL方法－Jacobi方法
| 原本的Gauss/Lagrange方法 | 本論文的Gauss/Lagrange方法 |
1 \( do\{\; \)
2 \(if(v_1的長度>v_2的長度)\)
3 \( \{\; v_1和v_2兩個向量交換 \}\; \)
4 \(t=\lfloor\; v_1.v_2/v_1.v_1 \rceil\; \)
5 \(if(t!=0)\)
6 \(\{\; v_2=v_2−tv_1; \}\;\)
7 \(\}\;\)
8 \(while(t!=0);\) | 1 \(G=V^TV\)
2 \(U=I_2\)
3 \( if \) \(G(1,1)<G(2,2)\)
4 \( swap \) \(G(:,1)\) \(and\) \(G(:,2)\)
5 \( swap \) \(G(1,: )\) \(and\) \(G(2,: )\)
6 \( swap \) \(Z(:,1)\) \(and\) \(G(:,2)\)
7 \(end\)
8
9 \(while\) \(G(1,1)>G(2,2)\)
10 \(q=\lfloor\; G(1,2)/G(2,2) \rceil\;\)
11 \(G(:,2)=G(:,2)-q \times G(:,1)\)
12 \(G(2,: )=G(2,: )-q \times G(1,: )\)
13 \(U(:,2)=U(:,2)-q \times U(:,1)\)
14 \(end\)
15
16 \(return\) \(U\) |
註：說明論文所用的符號
1.\(G=V^TV\)代表gram矩陣，其中\(G(i,i)=v_i.v_i,G(i,j)=v_i.v_j\)，對角線元素為每個向量長度的平方，其他元素為兩向量的內積。
2.\(B\)代表lattice，為文章一致改用\(V\)表示lattice。
3.\(Z\)代表unimodular矩陣，但一般常用\(U\)表示unimodular矩陣，其中\(det(U)=+1或-1\)。
| Jacobi方法以列計算 | Jacobi方法以行計算 |
1 \(G=VV^T\)
2 \(U=I_n\)
3
4 \(while\) \(not\) \(all\) \(pairs\) \((v_i,v_j)\) \(satisfy\) \( \Vert\; v_i \Vert\; \le \Vert\; v_j \Vert\; \) and \( \displaystyle |\; v_i v_j |\; \le \frac{\Vert\; v_i \Vert\;^2}{2} \)
5 \(for\) \(i=1\) \(to\) \(n-1\)
6 \(for\) \(j=i+1\) \(to\) \(n\)
7 \(q=G(i,j)/G(i,i)\)
8 \(if\) \(|\; q |\;>1/2\)
9 \(G(:,j)=G(:,j)-\lfloor\; q \rceil\; \times G(:,i)\)
10 \(G(j,: )=G(j,: )-\lfloor\; q \rceil\; \times G(i,: )\)
11 \(U(j,: )=U(j,: )-\lfloor\; q \rceil\; \times U(i,: )\)
12 \(end\)
13 \(if\) \(G(i,i)>G(j,j)\)
14 \(swap\) \(G(:,i)\) \(and\) \(G(:,j)\)
15 \(swap\) \(G(i,: )\) \(and\) \(G(j,: )\)
16 \(swap\) \(U(i,: )\) \(and\) \(U(j,: )\)
17 \(end\)
18 \(end\)
19 \(end\)
20 \(end\)
21
22 \(return\) \(UV\) | 1 \(G=V^TV\)
2 \(U=I_n\)
3
4 \(while\) \(not\) \(all\) \(pairs\) \((v_i,v_j)\) \(satisfy\) \( \Vert\; v_i \Vert\; \le \Vert\; v_j \Vert\; \) and \( \displaystyle |\; v_i v_j |\; \le \frac{\Vert\; v_i \Vert\;^2}{2} \)
5 \(for\) \(i=1\) \(to\) \(n-1\)
6 \(for\) \(j=i+1\) \(to\) \(n\)
7 \(q=G(i,j)/G(i,i)\)
8 \(if\) \(|\; q |\;>1/2\)
9 \(G(:,j)=G(:,j)-\lfloor\; q \rceil\; \times G(:,i)\)
10 \(G(j,: )=G(j,: )-\lfloor\; q \rceil\; \times G(i,: )\)
11 \(U(:,j)=U(:,j)-\lfloor\; q \rceil\; \times U(:,i)\)
12 \(end\)
13 \(if\) \(G(i,i)>G(j,j)\)
14 \(swap\) \(G(:,i)\) \(and\) \(G(:,j)\)
15 \(swap\) \(G(i,: )\) \(and\) \(G(j,: )\)
16 \(swap\) \(U(:,i)\) \(and\) \(U(:,j)\)
17 \(end\)
18 \(end\)
19 \(end\)
20 \(end\)
21
22 \(return\) \(VU\) |
註：
論文演算法以行向量運算，本文章卻以列向量運算，所以將兩個演算法並列出來，其中第1,11,16,22行有差異。
論文演算法第7行\(q=G(i,j)/G(j,j)\)會導致lattice尚未化簡完程式就提早結束，更正為\(q=G(i,j)/G(i,i)\)。
參考資料：
http://www.cas.mcmaster.ca/~qiao/
Filip Jeremic and Sanzheng Qiao. A Parallel Jacobi-type Lattice Basis Reduction Algorithm. International Journal of Numerical Analysis and Modeling, Series B. Vol. 5, No. 1-2, 2014, 1-12.
http://www.cas.mcmaster.ca/~qiao/publications/JQ14.pdf
Filip Jeremic and Sanzheng Qiao. A GPU Implementation of a Jacobi Method for Lattice Basis Reduction. Proceedings of International Workshop on Data-Intensive Scientific Discovery (DISD), 2013, Shanghai University, Shanghai, China, August 1-4, 2013.
http://www.cas.mcmaster.ca/~qiao/publications/JQ13.pdf
以列向量運算的Jacobi方法
(%i1)
JacobibyRow(V):=block
([End,G,n:length(V),U,i,j],
G:V.transpose(V),
U:ident(n),
do
(End:true,
for i:1 thru n-1 do
(for j:i+1 thru n do
(q:G[i,j]/G[i,i],
if abs(q)>1/2 then
(print("G(",i,",",j,")/G(",i,",",i,")=",q,">",1/2," , round(",q,")=",round(q)),
print("G=",G," 第",j,"行-",round(q),"*第",i,"行 G=",G:columnop(G,j,i,round(q))),
print("G=",G," 第",j,"列-",round(q),"*第",i,"列 G=",G:rowop(G,j,i,round(q))),
print("U=",U," 第",j,"列-",round(q),"*第",i,"列 U=",U:rowop(U,j,i,round(q))),
End:false
),
if G[i,i]>G[j,j] then
(print("G(",i,",",i,")=",G[i,i],">G(",j,",",j,")=",G[j,j]),
print("G=",G," 第",i,"行和第",j,"行交換 G=",G:columnswap(G,i,j)),
print("G=",G," 第",i,"列和第",j,"列交換 G=",G:rowswap(G,i,j)),
print("U=",U," 第",i,"列和第",j,"列交換 U=",U:rowswap(U,i,j)),
End:false
)
)
),
if End=true then
(print("G=",G,",",vi.vj/vi.vi,"=",genmatrix(lambda([i,j],if i<j then G[i,j]/G[i,i] else "*"),n,n),
",向量長度=",genmatrix(lambda([i,j],sqrt(G[i,i])),n,1)),
print("所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束"),
print("化簡後向量V=U.V=",U,V,"=",U.V),
return(U.V)
),
print("------------------------")
)
)$
列向量的lattice
(%i2)
V:matrix([1,1,1],
[-1,0,2],
[3,5,6]);
(%o2) \( \left[ \matrix{1&1&1\cr -1&0&2\cr 3&5&6} \right] \)
(%i3) JacobibyRow(V);
\( \displaystyle G( 1,3)/G(1,1)=\frac{14}{3}>\frac{1}{2}\) , \( \displaystyle round(\frac{14}{3})=5\)
\( G=\left[ \matrix{3&1&14\cr 1&5&9\cr 14&9&70} \right] \)第3行-5*第1行 \( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr 14&9&0} \right] \)
\( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr 14&9&0} \right] \)第3列-5*第1列 \( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr -1&4&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr 0&1&0\cr 0&0&1} \right] \)第3列-5*第1列 \( U=\left[ \matrix{1&0&0\cr 0&1&0\cr -5&0&1} \right] \)
\( \displaystyle G( 2,3)/G(2,2)=\frac{4}{5}>\frac{1}{2}\) , \( \displaystyle round(\frac{4}{5})=1\)
\( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr -1&4&5} \right] \)第3行-1*第2行 \( G=\left[ \matrix{3&1&-2\cr
1&5&-1\cr -1&4&1} \right] \)
\( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -1&4&1} \right] \)第3列-1*第2列 \( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -2&-1&2} \right] \)
\( U=\left[ \matrix{1&0&0\cr 0&1&0\cr -5&0&1} \right] \)第3列-1*第2列 \( U=\left[ \matrix{1&0&0\cr
0&1&0\cr -5&-1&1} \right] \)
\( G( 2,2)=5>G(3,3)=2 \)
\( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -2&-1&2} \right] \)第2行和第3行交換 \( G=\left[ \matrix{3&-2&1\cr 1&-1&5\cr -2&2&-1} \right] \)
\( G=\left[ \matrix{3&-2&1\cr 1&-1&5\cr -2&2&-1} \right] \)第2列和第3列交換 \( G=\left[ \matrix{3&-2&1\cr -2&2&-1\cr 1&-1&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr 0&1&0\cr -5&-1&1} \right] \)第2列和第3列交換 \( U=\left[ \matrix{1&0&0\cr -5&-1&1\cr 0&1&0} \right] \)
------------------------
\( \displaystyle G( 1,2)/G(1,1)=-\frac{2}{3}>\frac{1}{2}\) , \( \displaystyle round(\frac{-2}{3})=-1\)
\( G=\left[ \matrix{3&-2&1\cr -2&2&-1\cr 1&-1&5} \right] \)第2行--1*第1行 \( G=\left[ \matrix{3&1&1\cr -2&0&-1\cr 1&0&5} \right] \)
\( G=\left[ \matrix{3&1&1\cr -2&0&-1\cr 1&0&5} \right] \)第2列--1*第1列 \( G=\left[ \matrix{3&1&1\cr
1&1&0\cr 1&0&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr -5&-1&1\cr 0&1&0} \right] \)第2列--1*第1列 \( U=\left[ \matrix{1&0&0\cr -4&-1&1\cr 0&1&0} \right] \)
\( G( 1,1)=3>G(2,2)=1\)
\( G=\left[ \matrix{3&1&1\cr 1&1&0\cr 1&0&5} \right] \)第1行和第2行交換 \( G=\left[ \matrix{1&3&1\cr 1&1&0\cr 0&1&5} \right] \)
\( G=\left[ \matrix{1&3&1\cr 1&1&0\cr 0&1&5} \right] \)第1列和第2列交換 \( G=\left[ \matrix{1&1&0\cr 1&3&1\cr 0&1&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr -4&-1&1\cr 0&1&0} \right] \)第1列和第2列交換 \( U=\left[ \matrix{
-4&-1&1\cr 1&0&0\cr 0&1&0} \right] \)
------------------------
\( \displaystyle G( 1,2)/G(1,1)=1>\frac{1}{2}\) , \( \displaystyle round(1)=1\)
\( G=\left[ \matrix{1&1&0\cr 1&3&1\cr 0&1&5} \right] \)第2行-1*第1行 \( G=\left[ \matrix{1&0&0\cr
1&2&1\cr 0&1&5} \right] \)
\( G=\left[ \matrix{1&0&0\cr 1&2&1\cr 0&1&5} \right] \)第2列-1*第1列 \( G=\left[ \matrix{1&0&0\cr
0&2&1\cr 0&1&5} \right] \)
\( U=\left[ \matrix{-4&-1&1\cr 1&0&0\cr 0&1&0} \right] \)第2列-1*第1列 \( U=\left[ \matrix{-4&-1&1\cr 5&1&-1\cr 0&1&0} \right] \)
------------------------
\( G=\left[ \matrix{1&0&0\cr 0&2&1\cr 0&1&5} \right]\),\( \displaystyle \frac{vi.vj}{vi^2}=\left[\matrix{\displaystyle *&0&0\cr *&*&\frac{1}{2}\cr *&*&*}\right]\),向量長度\(=\left[ \matrix{1\cr \sqrt{2}\cr \sqrt{5}} \right] \)
所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束
化簡後向量\( V=U.V=\left[ \matrix{-4&-1&1\cr 5&1&-1\cr 0&1&0} \right] \left[\matrix{1&1&1\cr -1&0&2\cr 3&5&6}\right]=\left[ \matrix{0&1&0\cr 1&0&1\cr -1&0&2} \right]\)
(%o3) \( \left[ \matrix{0&1&0\cr 1&0&1\cr -1&0&2} \right] \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
以行向量運算的Jacobi方法
(%i1)
JacobibyColumn(V):=block
([End,G,n:length(V),U,i,j],
G:transpose(V).V,
U:ident(n),
do
(End:true,
for i:1 thru n-1 do
(for j:i+1 thru n do
(q:G[i,j]/G[i,i],
if abs(q)>1/2 then
(print("G(",i,",",j,")/G(",i,",",i,")=",q,">",1/2," , round(",q,")=",round(q)),
print("G=",G," 第",j,"行-",round(q),"*第",i,"行 G=",G:columnop(G,j,i,round(q))),
print("G=",G," 第",j,"列-",round(q),"*第",i,"列 G=",G:rowop(G,j,i,round(q))),
print("U=",U," 第",j,"行-",round(q),"*第",i,"行 U=",U:columnop(U,j,i,round(q))),
End:false
),
if G[i,i]>G[j,j] then
(print("G(",i,",",i,")=",G[i,i],">G(",j,",",j,")=",G[j,j]),
print("G=",G," 第",i,"行和第",j,"行交換 G=",G:columnswap(G,i,j)),
print("G=",G," 第",i,"列和第",j,"列交換 G=",G:rowswap(G,i,j)),
print("U=",U," 第",i,"行和第",j,"行交換 U=",U:columnswap(U,i,j)),
End:false
)
)
),
if End=true then
(print("G=",G,",",vi.vj/vi.vi,"=",genmatrix(lambda([i,j],if i<j then G[i,j]/G[i,i] else "*"),n,n),
",向量長度=",genmatrix(lambda([i,j],sqrt(G[i,i])),n,1)),
print("所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束"),
print("化簡後向量V=V.U=",V,U,"=",V.U),
return(V.U)
),
print("------------------------")
)
)$
行向量的lattice
(%i2)
V:matrix([1,-1,3],
[1,0,5],
[1,2,6]);
(%o2) \( \left[ \matrix{1&-1&3\cr 1&0&5\cr 1&2&6} \right] \)
(%i3) JacobibyColumn(V);
\( \displaystyle G(1,3)/G(1,1)=\frac{14}{3}>\frac{1}{2} \) , \( \displaystyle round(14/3)=5 \)
\( G=\left[ \matrix{3&1&14\cr 1&5&9\cr 14&9&70} \right] \) 第3行-5*第1行 \( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr 14&9&0} \right] \)
\( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr 14&9&0} \right] \) 第3列-5*第1列 \( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr -1&4&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr 0&1&0\cr 0&0&1} \right] \) 第3行-5*第1行 \( U=\left[ \matrix{1&0&-5\cr 0&1&0\cr 0&0&1} \right] \)
\( \displaystyle G(2,3)/G(2,2)=\frac{4}{5}>\frac{1}{2} \) , \( \displaystyle round(4/5)=1\)
\( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr -1&4&5} \right] \) 第3行-1*第2行 \( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -1&4&1} \right] \)
\( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -1&4&1} \right] \) 第3列-1*第2列 \( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -2&-1&2} \right] \)
\( U=\left[ \matrix{1&0&-5\cr 0&1&0\cr 0&0&1} \right] \) 第3行-1*第2行 \( U=\left[ \matrix{1&0&-5\cr 0&1&-1\cr 0&0&1} \right] \)
\( G(2,2)=5>G(3,3)=2\)
\( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -2&-1&2} \right] \) 第2行和第3行交換 \( G=\left[ \matrix{3&-2&1\cr 1&-1&5\cr -2&2&-1} \right] \)
\( G=\left[ \matrix{3&-2&1\cr 1&-1&5\cr -2&2&-1} \right] \) 第2列和第3列交換 \( G=\left[ \matrix{3&-2&1\cr -2&2&-1\cr 1&-1&5} \right] \)
\( U=\left[ \matrix{1&0&-5\cr 0&1&-1\cr 0&0&1} \right] \) 第2行和第3行交換 \( U=\left[ \matrix{
1&-5&0\cr 0&-1&1\cr 0&1&0} \right] \)
------------------------
\( \displaystyle G(1,2)/G(1,1)=-\frac{2}{3}>\frac{1}{2} \) , \( \displaystyle round(-\frac{2}{3})=-1\)
\( G=\left[ \matrix{3&-2&1\cr -2&2&-1\cr 1&-1&5} \right] \) 第2行--1*第1行 \( G=\left[ \matrix{3&1&1\cr -2&0&-1\cr 1&0&5} \right] \)
\( G=\left[ \matrix{3&1&1\cr -2&0&-1\cr 1&0&5} \right] \) 第2列--1*第1列 \( G=\left[ \matrix{3&1&1\cr 1&1&0\cr 1&0&5} \right] \)
\( U=\left[ \matrix{1&-5&0\cr 0&-1&1\cr 0&1&0} \right] \) 第2行--1*第1行 \( U=\left[ \matrix{1&-4&0\cr 0&-1&1\cr 0&1&0} \right] \)
\( G(1,1)=3>G(2,2)=1\)
\( G=\left[ \matrix{3&1&1\cr 1&1&0\cr 1&0&5} \right] \) 第1行和第2行交換 \( G=\left[ \matrix{1&3&1\cr 1&1&0\cr 0&1&5} \right] \)
\( G=\left[ \matrix{1&3&1\cr 1&1&0\cr 0&1&5} \right] \) 第1列和第2列交換 \( G=\left[ \matrix{
1&1&0\cr 1&3&1\cr 0&1&5} \right] \)
\( U=\left[ \matrix{1&-4&0\cr 0&-1&1\cr 0&1&0} \right] \) 第1行和第2行交換 \( U=\left[ \matrix{
-4&1&0\cr -1&0&1\cr 1&0&0} \right] \)
------------------------
\( \displaystyle G(1,2)/G(1,1)=1>\frac{1}{2} \) , \( round(1)=1\)
\( G=\left[ \matrix{1&1&0\cr 1&3&1\cr 0&1&5} \right] \) 第2行-1*第1行 \( G=\left[ \matrix{1&0&0\cr 1&2&1\cr 0&1&5} \right] \)
\( G=\left[ \matrix{1&0&0\cr 1&2&1\cr 0&1&5} \right] \) 第2列-1*第1列 \( G=\left[ \matrix{1&0&0\cr 0&2&1\cr 0&1&5} \right] \)
\( U=\left[ \matrix{-4&1&0\cr -1&0&1\cr 1&0&0} \right] \) 第2行-1*第1行 \( U=\left[ \matrix{-4&5&0\cr -1&1&1\cr 1&-1&0} \right] \)
------------------------
\( G=\left[ \matrix{1&0&0\cr 0&2&1\cr 0&1&5}\right],\frac{vi.vj}{vi^2}=\left[ \matrix{*&0&0\cr *&*&\frac{1}{2}\cr *&*&*}\right] \),向量長度\( =\left[ \matrix{1\cr \sqrt{2}\cr \sqrt{5}} \right] \)
所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束
化簡後向量\( V=V.U=\left[ \matrix{1&-1&3\cr 1&0&5\cr 1&2&6} \right] \left[ \matrix{-4&5&0\cr -1&1&1\cr 1&-1&0} \right]=\left[ \matrix{0&1&-1\cr 1&0&0\cr 0&1&2} \right]\)
(%o3) \( \left[ \matrix{0&1&-1\cr 1&0&0\cr 0&1&2} \right] \)
[ 本帖最後由 bugmens 於 2017-12-31 13:54 編輯 ]
|
