PSLQ
11-29-2017, 08:12 PM (This post was last modified: 12-05-2017 06:58 PM by Han.)
Post: #1 Han Senior Member Posts: 1,834 Joined: Dec 2013
PSLQ
PSLQ (Partial Sums LQ Decomposition) can be used to determine if there exists a set of integer coefficients $$\mathbf{a} = (a_1, a_2, \dotsm, a_n)$$ for a given vector $$\mathbf{x} = (x_1, x_2, \dotsm, x_n)$$ such that their dot product is 0 (i.e. $$\sum a_i x_i = 0$$ ).

Please note that this is beta; I have not implemented a full set of exit conditions!

Code:
NINT(x) BEGIN   local n:=IP(x);   if x > n+.5 then return(n+1); end;   if x < n-.5 then return(n-1); end;   return(n); END; EXPORT PSLQ(lst) BEGIN local MA,MB,MH; local j,k,n,m,r; local s:={}, y:={}; local t; local g:=2/sqrt(3); local M1,M2; local t0,t1,t2,t3,t4; local run:=0; n:=size(lst); MA:=idenmat(n); MB:=MA; MH:=MA; MH:=delcol(MH,n); for k from 1 to n do   s(k):=sqrt(sum(lst(j)^2,j,k,n)); end; t:=1/s(1); //for k from 1 to n do //  y(k):=t*lst(k); //  s(k):=t*s(k); //end; y:=t*lst; s:=t*s; for j from 1 to n-1 do   MH(j,j):=s(j+1)/s(j);   for k from j+1 to n do     MH(k,j):=-y(k)*y(j)/(s(j)*s(j+1));   end; end; for k from 2 to n do   for j from k-1 downto 1 do     t:=NINT(MH(k,j)/MH(j,j));     y(j):=y(j)+t*y(k);     for m from 1 to j do       MH(k,m):=MH(k,m)-t*MH(j,m);     end;     for m from 1 to n do       MA(k,m):=MA(k,m)-t*MA(j,m);       MB(m,j):=MB(m,j)+t*MB(m,k);     end;   end; end; // iterate repeat m:=1; M1:=g*abs(MH(1,1)); for k from 2 to n-1 do   M2:=g^k*abs(MH(k,k));   if M2>M1 then     m:=k; M1:=M2;   end; end; M2:=y(m); y(m):=y(m+1); y(m+1):=M2; MH:=swaprow(MH,m,m+1); MA:=swaprow(MA,m,m+1); MB:=swapcol(MB,m,m+1); if m<=n-2 then    t0:=sqrt(MH(m,m)^2+MH(m,m+1)^2);   t1:=MH(m,m)/t0;   t2:=MH(m,m+1)/t0;   for j from m to n do     t3:=MH(j,m);     t4:=MH(j,m+1);     MH(j,m):=t1*t3+t2*t4;     MH(j,m+1):=-t2*t3+t1*t4;   end; end; for k from m+1 to n do   for j from min(k-1,m+1) downto 1 do     t:=NINT(MH(k,j)/MH(j,j));     y(j):=y(j)+t*y(k);     for r from 1 to j do       MH(k,r):=MH(k,r)-t*MH(j,r);     end;     for r from 1 to n do       MA(k,r):=MA(k,r)-t*MA(j,r);       MB(r,j):=MB(r,j)+t*MB(r,k);     end;   end; end; m:=1; M1:=abs(y(1)); for j from 2 to n do   M2:=abs(y(j));   if M2<M1 then M1:=M2; m:=j; end; end; run:=(M1<1E-10); until run end; return(col(MB,m)); END;

This can be used to solve a number of interesting "algebraic form" problems. For example, the number 3.96811878507 is the decimal approximation of $$x=\sqrt{3} + \sqrt{5}$$. The value $$x$$ is a root of the polynomial $$x^4 - 16x^2 + 4$$. Moreover, numbers of the form $$\sqrt{a} + \sqrt{b}$$ are roots of $$x^4 - 2(a+b)x^2 + (a-b)^2$$. We can use PSLQ on the vector $$( x^4, x^3, x^2, x, 1 )$$ to obtain the result: $$( 1, 0, -16, 0, 4 )$$. Additionally solving $$-2(a+b) = -16$$ and $$(a-b)^2=4$$ simultaneously results in the values a=3 and b=5.

Code:
 X:=SQRT(3)+SQRT(5); PSLQ({X^4,X^3,X^2,X,1); // returns {1,0,-16,0,4}

Another example may be to rewrite $$x \approx 7.09439510239$$ in the preferred form $$2\pi/3 + 5$$. Notice that $$x$$ satisfies: $$0 = 2\pi -3x + 15$$. So if we apply PLSQ to the vector $$(\pi, 7.09439510239, 1 )$$ we get the vector $$(2,-3,15)$$

Code:
 X:=2*PI/3+5; PSLQ({PI,X,1}); // returns {2,-3,15}

Also, if we have a number of the form $$x= r_1 + \sqrt{r_2}$$ where the $$r_i$$'s are rational numbers, then simply apply PSLQ to $$( x^2, x, 1)$$ since such numbers are roots of some quadratic polynomial. The result from PSLQ -- $$( a,b,c )$$ -- are the coefficient of the quadratic polynomial, and can then be used to rewrite $$x$$ into a nice algebraic form using $$x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$$

Code:
 X:=2/3+4*SQRT(3); PSLQ({X^2,X,1}); // returns {9,-12,-428}

Graph 3D | QPI | SolveSys
 « Next Oldest | Next Newest »

 Messages In This Thread PSLQ - Han - 11-29-2017 08:12 PM RE: PSLQ - Han - 11-29-2017, 08:42 PM RE: PSLQ - Han - 11-29-2017, 08:52 PM RE: PSLQ - salvomic - 11-29-2017, 09:28 PM RE: PSLQ - Han - 11-29-2017, 09:33 PM RE: PSLQ - salvomic - 11-29-2017, 09:35 PM RE: PSLQ - salvomic - 11-29-2017, 08:58 PM RE: PSLQ - AlexFekken - 11-30-2017, 02:16 AM RE: PSLQ - Han - 11-30-2017, 03:14 AM RE: PSLQ - AlexFekken - 11-30-2017, 03:56 AM RE: PSLQ - BruceH - 11-30-2017, 11:10 PM RE: PSLQ - AlexFekken - 12-02-2017, 11:55 PM RE: PSLQ - ggauny@live.fr - 11-30-2017, 11:05 AM RE: PSLQ - Han - 11-30-2017, 12:19 PM RE: PSLQ - ggauny@live.fr - 11-30-2017, 12:29 PM

User(s) browsing this thread: 1 Guest(s)