I am trying to solve multiple systems of linear equations over $n$ variables $AX=B$, where $B$ is partially unknown. Let us assume that $A$ has shape $n' \times n$, $X$ has shape $n \times m$ and $B$ has shape $n' \times m$.
For example, given equations
$$ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 & y_1 \\ x_2 & y_2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & * \end{pmatrix}, $$
I am looking for solution spaces
\begin{align*} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} &= \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \text{ and} \\ \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} &= \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \alpha \begin{pmatrix} 0 \\ 1 \end{pmatrix} \quad \text{for arbitrary } \alpha \end{align*}
Clearly, I can solve $Ax=b$ repeatedly, by simply dropping those rows which involve unknown right-hand sides (as these constraints are irrelevant). However, this yields time complexity $\mathcal{O}(m \cdot n' \cdot n^2)$ assuming I solve equations using Gaussian elimination.
Is there a faster option?
If it matters: In my case, the equations are modulo 2.