8
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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}$)? $\endgroup$
    – Zim
    Jun 2 '20 at 2:57
  • $\begingroup$ @Zim $X$ is the solution of $S_k$. I mean $S_k \implies X \implies S_{k+1}\implies \cdots$. $\endgroup$
    – Akira
    Jun 2 '20 at 3:00
  • $\begingroup$ 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? $\endgroup$
    – Zim
    Jun 2 '20 at 3:03
  • $\begingroup$ @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. $\endgroup$
    – Akira
    Jun 2 '20 at 3:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Akira
    Jun 3 '20 at 22:34
1
+500
$\begingroup$

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}|$).

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Akira
    Jun 17 '20 at 23:14
  • $\begingroup$ 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). $\endgroup$
    – araomis
    Jun 18 '20 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.