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?
