Fast algorithm for solving system of linear equations I have a system of $N$ linear equations, $Ax=b$, in $N$ unknowns (where $N$ is large). 

If I am interested in the solution for only one of the unknowns, what are the best approaches? 

For example, assume $N=50,000$. We want the solution for $x_1$ through $x_{100}$ only. Is there any trick that does not require $O(n^{3})$ (or $O$(matrix inversion))?
The fastest matrix multiplication algorithm is an important open mathematical question

The Wikipedia page https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Sub-cubic_algorithms shows how the fast known asymptotic algorithm has evolved through time:



This begs the question: how close can we get to O(n^2), which is of course a lower bound since we have to read 2 * n^2 inputs at least once?

Proving the upper lower bound, even non constructively, would make you instantly famous. Wikipedia lists it as an "Unsolved problem in computer science".

The constant factor for the better algorithms is so large though that it makes them impractical for most matrix sizes found in practice today, and I doubt this will change if new algorithms are found.

Therefore any practical real world answer will come down to optimizing against a given machine model, which is an important software / hardware engineering optimization question, but not of much mathematical interest.

Personal guess about solving for single variables: I don't think you can reduce complexity like that in general, since the entire system is coupled. How would you know that your solution for some variables also satisfies the entire global solution?
Im suggesting you take a look into what quantum computing can do for you. 

If you are able to make api calls form your product - then this might be the most performant approach by a lot.

This youtube video for example is a lecture which discusses problems that appear with large nr of equations : Quantum algorithm for solving linear equations

For quantum computer api you can use a service like: http://rigetti.com/forest

I personally did not tested this services, but this answer is just for pointing out the posibility. Just to show is something that can be used today, not science fiction.