fast algorithm for solving system of linear equations

I have a system of linear equations, $Ax=b$, with $N$ equations and $N$ unknowns ($N$ 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 and 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) ) for that ?

-
Is $A$ full or sparse? Are you doing this once or many times with the same $A$? –  joriki Apr 1 '11 at 16:56
A is not sparse and has many nonzero elements, however, the coefficients themselves are derived from a smaller set of variables. –  mghandi Apr 2 '11 at 3:37
About your second question, yes I'm doing this many times. I am familiar with the LU decomposition trick to speed up when the coeffs matrix is unchanged. Is there any other tricks to do that even more efficiently? –  mghandi Apr 2 '11 at 3:51
You may apply iterative methods (CG, if you matrix is spd, GMRES something similar otherwise). You may also want to ask at scicomp.stackexchange.com. –  Dirk Dec 15 '12 at 17:43

Unless your matrix is sparse or structured (e.g. Vandermonde, Hankel, or those other named matrix families that admit a fast solution method), there is not much hope of doing things better than $O(n^3)$ effort. Even if one were to restrict himself to solving for just one of the 50,000 variables, Cramer will demand computing two determinants for your answer, and the effort for computing a determinant is at least as much as decomposing/inverting a matrix to begin with.

-
strang gilbert - linear algebra and its applications 3rd edition page 16 at the footer mentions that complexity had fallen already fallen below $O(Cn^{2.376})$ at the date of writing 1988, altough $C$ is so large that makes the algorithm impractical for most matrix sizes found in practice today. It does not mention the name of the algorithm though.