# Complexity Lower Bounds for 3D Sparse Gaussian Elimination

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 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?

• Would you consider randomized results? Jan 24, 2021 at 2:31
• @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. Jan 25, 2021 at 3:36