Let me take this opportunity to make a comment that talks about the upper bound, not the lower.

Actually, let me remind you that it is a common false belief that Gaussian Elimination has $O(n^3)$ complexity. See the nice question with its answers here at cstheory

This misbelief happens because even though GE requires $O(n^3)$ arithmetic operations, if not done properly, there can be massive intermediate coefficient growth, which renders judging the true complexity of GE a difficult task.

You might also enjoy looking here at the near linear time algorithms for solving special linear systems (example for diagonally dominant matrices). For general, non-structured matrices, the situation is less clear.

Let me take this opportunity to make a comment that talks about the upper bound, not the lower.

Actually, let me remind you that it is a common false belief that Gaussian Elimination has $O(n^3)$ complexity. See the nice question with its answers here at cstheory

This misbelief happens because even though GE requires $O(n^3)$ arithmetic operations, if not done properly, there can be massive intermediate coefficient growth, which renders judging the true complexity of GE a difficult task.

You might also enjoy looking here at the near linear time algorithms for solving special linear systems (example for diagonally dominant matrices). For general, non-structured matrices, the situation is less clear.

Let me take this opportunity to make a comment that talks about the upper bound, not the lower.

Actually, let me remind you that it is a common false belief that Gaussian Elimination has $O(n^3)$ complexity. See the nice question with its answers here at cstheory

This misbelief happens because even though GE requires $O(n^3)$ arithmetic operations, if not done properly, there can be massive intermediate coefficient growth, which renders judging the true complexity of GE a difficult task.

As far as a lower bound is concerned, sorry, I don't have anything special to add beyond what you already know.

Let me take this opportunity to make a comment that talks about the upper bound, not the lower.

Actually, let me remind you that it is a common false belief that Gaussian Elimination has $O(n^3)$ complexity. See the nice question with its answers here at cstheory

This misbelief happens because even though GE requires $O(n^3)$ arithmetic operations, if not done properly, there can be massive intermediate coefficient growth, which renders judging the true complexity of GE a difficult task.

You might also enjoy looking here at the near linear time algorithms for solving special linear systems (example for diagonally dominant matrices). For general, non-structured matrices, the situation is less clear.