0

I have an algorithm for generating some upper triangular sparse matrix $A$ of size $2^n\times 2^n$, which is invertible. I want to solve the linear system $A\mathbf{x}=\mathbf{1}$ where $\mathbf{1}$ is all ones vector for $n=100$. I wonder if there are some tools or some algorithm to deal with this problem.

kswim
  • 433

1 Answers1

0

In general one would use back substitution for upper triangular matrices for solve systems of this form. If the back substitution is too expensive you can also exploit the sparsity and run any iterative method exploiting the sparsity.

In your situation however your matrix has size $2^{100} \times 2^{100}$ so your vector $x$ is in $\mathbb{R}^{100}$. Since you said $A$ is invertible all the diagonal elements are non-zero. This makes both storing $A$ and $x$ completely intractable. No computer is able to handle this much storage.

I would assume that your matrix arises from a NP hard problem. Unfortunately, there is no way to solve this system. You should look at your original problem again and try to find a different (heuristic) algorithm for the problem.

Inflax
  • 101
  • Thanks a lot for your comment. In the second paragraph, you would mean "$x$ is in $\mathbb{R}^{2^{100}}$", right? – kswim Oct 04 '21 at 13:03
  • Yes, it should be $\mathbb{R}^{2^{100}}$ which is too large to store for any computer. Your only chance to compute a solution might be additional structure in $x$ such as entries following a certain repetition pattern or quickly decaying entries such that storing the first entries is sufficient. – Inflax Oct 04 '21 at 14:35
  • Do you happen to have a simple example for "quickly decaying entries" in your mind? I am not clear about what you meant. – kswim Oct 04 '21 at 14:39
  • Let $A$ be the identity matrix and $x_i = b_i = \exp(-i)$. If you are only interested in a numerical approximation with some accuracy, $x_i$ will be numerically zero starting from a certain index. In this case you could try to identify this index and only solve with respect to smaller $i$. – Inflax Oct 07 '21 at 07:30