Find the solution of linear equation using Wiedemann/ Krylov method

Question

I am using Wiedemann (some literature called Krylov method) to find the solution of a linear equation that defined as $$Mx=b$$ Instead of resolving entire elements of x (size $K \times 1$), we can solve a signle element at index i by following equation: $$M_tx'=u_i (1)$$ where $M_t=M^T$ and $x'$ is right combination, $u_i$ is unit vector at the index i.M has size $(N \times K)$ The solution of single element can be obtained by inner production $$x_i=\sum_{j=1}^{N} x'_j.b_j$$ To resolve equation (1) we can use Wiedemann algorithm as

• Step 1: Construct a Krylov sequence {$u_i,M_tu_i,....M_{2K-1}u_i$}
• Step2: Let $S$ is space spanned by this sequence. Denotes $M_s$ is the operator $M_t$ restriced to $S$. Find the minimal polynomial of $M_s$, called $f(z)$ (Using Berlekmap Massey). Let $d$ is degree of $f$ and $f[i]$ is coefficience of $z^i$ in $f(z)$
• Step3: The solution $x'$ is $x'=\sum_{i}^{d}f[i]M_t^{i-1}u_i$

Note that I am using this method in GF(2) in which only 1 or 0. and bit operations. The method is clearly explained as above. Now, we will have a numerical experiment for this algorithm

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]$

• Step 1: Construct a Krylov sequence {$u_i,M_tu_i,....M_{2K-1}u_i$} - DONE
• Step2: I am confusing in this step. 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?
• Step3: After finding $M_s$ and minimal polynomial, we can easy find $x'$