How to utilize the special feature of this recursive problem to reduce computational complexity? Assume


*

*$A$ is a $n \times n$ matrix of non-negative numbers.

*$A_i$ is the $i$-th row of $A$.

*$(a_1, \ldots, a_n)$ and $(b_1, \ldots, b_n)$ belong to $\mathbb R_+^n$.

*$I_0 = \{1, \ldots, n\}$.

*$X= [x_1, \ldots, x_n]^\intercal$ is unknown.
At stage $k$, we have $I_k \subseteq \{1 ,\ldots,n\}$ and a system $(S_k)$ of linear equations:
$$\left \{\begin{aligned}
\forall j \in I_k&: x_j &&= a_j \\
I^c_k  & &&=   \{1, \ldots, n\} \setminus I_k\\
\forall j \in I^c_k &: A_j X &&= 0 \\
\end{aligned}\right.$$
Then $$I_{k+1} = \{j \in I_k \mid A_j X - b_j > 0\}$$
This procedure is repeated until $I_k = I_{k+1}$.

My question: 
Clearly, if the equation $A_j X = 0$ appears in $(S_k)$, then it also appears in $(S_{k+1})$.
The matrix $A$ is of very large dimension. Is there any method to utilize this special feature to reduce the computational complexity? Any reference is greatly appreciated.
 A: I think one way to exploit this special feature is to formulate your linear system of equations $S_k$ in matrix form and then apply the https://en.wikipedia.org/wiki/Woodbury_matrix_identity formula to compute the solution of $S_{k + 1}$ by computing a low-rank update on the system matrix of $S_k$. However, this will only work if all system matrices we observe are invertible.
So lets say that in the $k$-th round you can compute $X$ as the unique solution of the system $S_kX = s$ where $S_k$ is an invertible $n \times n$-matrix and $s_k$ is an $n$-dimensional vector. You can do this by computing $X = S_k^{-1}s_k$. In general this by itself already takes $O(n^3)$ basic operations because you have to invert $S_k$. But if you already know the inverse of the previous round $S_{k - 1}^{-1}$ then you can use the Sherman-Morrison formula to compute $S_k^{-1}$ from $S_{k - 1}^{-1}$ by writing $S_k = S_{k - 1} + UV$ where $U$ is a $n \times l$-matrix and $V$ is a $l \times n$-matrix.
A naive implementation of your procedure would take $\mathcal{O}(n^4)$ basic operations. I think that using low-rank updates $\mathcal{O}(n^3)$ will suffice. However, this does only work under the restriction that we will only observe invertible system matrices.
For example, the first system of equations ($S_0$) could be written in matrix form as:
$$I_nX = a$$
By replacing rows of $I_n$ with the the corresponding rows of $A$ and by updating the right-hand side accordingly you can obtain the matrix formulation of the general system of equations $S_k$.
Note that this strategy exploits the fact that if we have $A_jX = 0$ in round $k$ then we will also have $A_jX = 0$ in later rounds: In every round we only have to update our system matrix with a rank $l$ update where $l$ is the number of elements which we deleted from the index set (or in other words l = $|I_{k} \setminus I_{k + 1}|$).
