<p>I'm interested in lower bounds on the complexity in the real-RAM model of solving systems of linear equations which have the sparsity pattern of a three-dimensional cubic mesh. Specifically, consider a matrix <span class="math-container">$A$</span> whose rows and columns are indexed by points in <span class="math-container">$\{1,\ldots,\sqrt[3]{N}\}^3$</span> with a nonzero entry in row <span class="math-container">$(i_1,i_2,i_3)$</span> and column <span class="math-container">$(j_1,j_2,j_3)$</span> only if <span class="math-container">$|i_1 - j_1| + |i_2 - j_2| + |i_3 - j_3| \le 1$</span>. The problem is:</p>
<blockquote>
<p>Given the <span class="math-container">$\mathcal{O}(N)$</span> nonzero entries comprising <span class="math-container">$A$</span> and <span class="math-container">$m$</span> right-hand sides <span class="math-container">$b_1,\ldots,b_m$</span>, compute <span class="math-container">$x_1 = A^{-1}b_1,\ldots,x_n = A^{-1}b_n$</span>.</p>
</blockquote>
<p>The prototypical example of this is the discrete Poisson equation in 3D or more generally a (generalized) Laplacian matrix on the three-dimensional mesh graph. There are results which show that if one additionally assumes <span class="math-container">$A$</span> is diagonally dominant, then approximate solutions <span class="math-container">$\tilde{x}_1,\ldots,\tilde{x}_n$</span> can be computed in <span class="math-container">$\tilde{\mathcal{O}}(mN)$</span> time. I'm interested in the case where there is no diagonal dominance assumption, and am in particular curious about the case where <span class="math-container">$x_1,\ldots,x_n$</span> are required to be computed exactly.</p>
<p>My understanding is the lower bound of <a href="https://epubs.siam.org/doi/abs/10.1137/0716027?casa_token=bqyUvtRsYO0AAAAA:N0KyzxwLxYevKklE2YE1Y7CjwOkP2eeQk6xIhknBpCvuMJhMLnPkRBs6E46wn9Og6W3EqCcNG6Y" rel="nofollow noreferrer">Lipton, Rose, and Tarjan</a> extends to the 3D case and thus solving such systems <em>by Gaussian elimination</em> requires <span class="math-container">$\mathcal{O}(N^2 + mN^{4/3})$</span> arithmetic operations, where <span class="math-container">$\mathcal{O}(N^2)$</span> are required to compute the factorization and <span class="math-container">$\mathcal{O}(N^{4/3})$</span> operations are required per right-hand side to do back- and forward-substitution. I believe this can be improved to <span class="math-container">$\mathcal{O}(N^{2\omega/3} + mN^{4/3})$</span> by using fast matrix multiplication algorithms, where <span class="math-container">$\omega \ge 2$</span> is the exponent of matrix multiplication. It seems that, in some sense, Gaussian elimination with a good elimination ordering is the &quot;natural&quot; algorithm for this problem. However, I am not aware of any truly general lower bounds for this problem. I know algebraic complexity bounds are hard to prove, but are such results known?</p>

CC BY-SA 4.0
2021-01-24T02:31:04.627Z
Would you consider randomized results?
user3483902
CC BY-SA 4.0
2021-01-25T03:36:52.060Z
@user3483902 Yes certainly. I would be surprised if randomization helped if one wants the solution computed exactly, but I would be happy to be proven wrong. I also limited the scope of my question to results for exact computation of $x_1,\ldots,x_n$ to keep the question direct, but I would certainly also be interested in lower bounds for approximate solution as well.
eepperly16
<cc.complexity-theory><lower-bounds><linear-algebra>
Complexity Lower Bounds for 3D Sparse Gaussian Elimination
eepperly16
# Complexity Lower Bounds for 3D Sparse Gaussian Elimination

(Asked by: username_0 on 2021-01-22)

I'm interested in lower bounds on the complexity in the real-RAM model of solving systems of linear equations which have the sparsity pattern of a three-dimensional cubic mesh. Specifically, consider a matrix $A$ whose rows and columns are indexed by points in $\{1,\ldots,\sqrt[3]{N}\}^3$ with a nonzero entry in row $(i\_1,i\_2,i\_3)$ and column $(j\_1,j\_2,j\_3)$ only if $|i\_1 - j\_1| + |i\_2 - j\_2| + |i\_3 - j\_3| \le 1$. The problem is:

> Given the $\mathcal{O}(N)$ nonzero entries comprising $A$ and $m$ right-hand sides $b\_1,\ldots,b\_m$, compute $x\_1 = A^{-1}b\_1,\ldots,x\_n = A^{-1}b\_n$.

The prototypical example of this is the discrete Poisson equation in 3D or more generally a (generalized) Laplacian matrix on the three-dimensional mesh graph. There are results which show that if one additionally assumes $A$ is diagonally dominant, then approximate solutions $\tilde{x}\_1,\ldots,\tilde{x}\_n$ can be computed in $\tilde{\mathcal{O}}(mN)$ time. I'm interested in the case where there is no diagonal dominance assumption, and am in particular curious about the case where $x\_1,\ldots,x\_n$ are required to be computed exactly.

My understanding is the lower bound of [Lipton, Rose, and Tarjan](https://epubs.siam.org/doi/abs/10.1137/0716027?casa_token=bqyUvtRsYO0AAAAA:N0KyzxwLxYevKklE2YE1Y7CjwOkP2eeQk6xIhknBpCvuMJhMLnPkRBs6E46wn9Og6W3EqCcNG6Y) extends to the 3D case and thus solving such systems *by Gaussian elimination* requires $\mathcal{O}(N^2 + mN^{4/3})$ arithmetic operations, where $\mathcal{O}(N^2)$ are required to compute the factorization and $\mathcal{O}(N^{4/3})$ operations are required per right-hand side to do back- and forward-substitution. I believe this can be improved to $\mathcal{O}(N^{2\omega/3} + mN^{4/3})$ by using fast matrix multiplication algorithms, where $\omega \ge 2$ is the exponent of matrix multiplication. It seems that, in some sense, Gaussian elimination with a good elimination ordering is the "natural" algorithm for this problem. However, I am not aware of any truly general lower bounds for this problem. I know algebraic complexity bounds are hard to prove, but are such results known?

**Tags:** cc.complexity-theory, lower-bounds, linear-algebra
> **Comments:**
> **username_1**: Would you consider randomized results?  
> **username_0**: @user3483902 Yes certainly. I would be surprised if randomization helped if one wants the solution computed exactly, but I would be happy to be proven wrong. I also limited the scope of my question to results for exact computation of $x_1,\ldots,x_n$ to keep the question direct, but I would certainly also be interested in lower bounds for approximate solution as well.  

---

## 0 answers

