What's the fastest way to solve a system of equations a million times such that the coefficient matrix is same but the constant matrix is different? I need an efficient way to solve $Ax=C$ a million times such that coefficient matrix $A$ is always the same but the constant matrix $C$ is always different for each of the million problems.
To solve the problem one time I can evaluate determination $A,A_x,A_y...$ using Gauss Elimination which would take like $O(n*n^3log||A||)$ time,
where n is degree of $|A|$. But for million cases that would be too much redundant calculations.
I am looking for an approach which is $<= O(n*n*million)$
@littleO suggested we can do it efficiently by LU Decomposition.

If $A$ is an $n\times n$ matrix, then you can solve the $n$ equations
$$Az_i=e_i$$
where $e_i$ is all zeroes except for a $1$ in the $i$th position. (Here the subscripted terms $z_i,e_i$ denote column vectors.)
Then the solution to $Ax=C$ is simply $$x=\sum_{i=1}^n c_iz_i$$
(Here the $z_i$'s are column vectors, but the $c_i$'s are the elements of $C$. Sorry if that is confusing!)
This is really just @Ilya's suggestion of computing the inverse $$A^{-1}=[z_1\; z_2\; \ldots\; z_n]$$
