# Find the solution of linear equation using Wiedemann/ Krylov method

Let given
$M =$

 1     0     1
0     1     1
1     1     1


and $b =$

 1
0
1


How to find the solution $x_3$ where $x=${$x_1,x_2,x_3$}?

Solution: Based on Wiedemann algorithm we has $u_i=[0; 0; 1]$. I am getting confused in the Step2. How to find $M_s$? Is it just the $3^th$ columns of $M_t$ as $M_s=[1 1 1]$ or it is created from Krylov sequence? Please help me find M_s and minimal polynomial?

Matlab code:

%% Input Generation Matrix M, b and index ith
%% Output single symbol x
M=[1 0 1;0 1 1;1 1 1];
b=[1; 0; 1];
index=2;
[K N]=size(M);
Mt=M';
Imatrix=eye(K,K);
x=[];
for index=1:K
u_i=Imatrix(:,index);
se_Krylov=[];
se_Krylov(:,1)=u_i;
for i=2:(2*K) % due to i=1 is u_i
se_Krylov(:,i)=mod((Mt^i)*u_i,2);
end
%% M_s is the operator Mt retricted to S
M_s=se_Krylov(index,:);

%% Compute the polynominal using Berlekmap Massey
[f, LCP] = Berlekamp_Massey2(M_s);
d=size(f,2)-1; %deg of f: x^d+x^(d-1)+....

x_comma=zeros(K,1);
for i=d:-1:1
x_comma=mod(x_comma+f(d).*(Mt)^(i-1)*u_i,2);
end
x_single=mod(x_comma'*b,2) ;%Inner product
x(index)=x_single;
end


## migrated from stackoverflow.comDec 30 '14 at 13:28

This question came from our site for professional and enthusiast programmers.

• -1 for the text-as-image. – Federico Poloni Dec 31 '14 at 9:44