# 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.

• This is a bit unclear to me -- do you mean to find a single $X$ that satisfies all of your requirements at every $k$, or just at the terminal $k$ (when $I_k=I_{k+1}$)?
– Zim
Jun 2 '20 at 2:57
• @Zim $X$ is the solution of $S_k$. I mean $S_k \implies X \implies S_{k+1}\implies \cdots$. Jun 2 '20 at 3:00
• Ok, so we are seeking every solution $X$ at every $k$. Perhaps $X$ should be denoted $X_k$ so we know it changes at each stage? Also, do you have any guarantees that these solutions will be unique?
– Zim
Jun 2 '20 at 3:03
• @Zim $X$ is just like a temporary unknown variable at each stage to me, so I write $X$ rather than $X_k$ to simplify notation. The matrix $A$ is such that $X$ is unique. Jun 2 '20 at 3:08
• I'm sorry @Zim for missing your comment and not being clear enough. Unfortunately, it's not. The point is that you compute $I_{k+1}$ from $I_k$ and then $I_{k+1}^c = \{1, \ldots, n\} \setminus I_k$. Please see my update. Jun 3 '20 at 22:34

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}|$$).
• You said that In general this by itself already takes $O(n^3)$ basic operations ... and using low-rank updates $O(n^3)$ will suffice. From this, I'm unable to get how we gain from using Sherman-Morrison formula. Could you please elaborate more? Jun 17 '20 at 23:14
• Of course. In the $k$-th round we have to solve the system of linear equations $S_kX = s_k$. In general, this takes $\mathcal{O}(n^3)$ basic operations. Hence a naive implementation could take $\mathcal{O}(n^4)$ basic operations since there are up to $n$ rounds. But if we already know $S_{k-1}^{-1}$ then we can use the Sherman-Morrison formula to compute $S_k^{-1}$ using $\mathcal{O}(n^2l)$ basic operations. Thus over all rounds we probably get $\mathcal{O}(n^3)$ basic operations (I think this could be shown using an amortised analysis). Jun 18 '20 at 5:57