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.
 A: 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]$$
A: When numerically solving a linear system of equations, the most common technique uses an LU factorization of $A$:
$$
PA = LU
$$
where $L$ is lower triangular, $U$ is upper triangular, and $P$ is a permutation matrix. Computing an LU factorization of $A$ is equivalent to doing Gaussian elimination. Numerical linear algebra libraries will compute an LU factorization of $A$ for you.
Then, to solve $Ax = c$, notice that
$$
Ax = c \iff PAx = Pc \iff LU x = Pc.
$$
We can first solve $Ly = Pc$, which is inexpensive because $L$ is lower triangular (so we can just use back substitution). Then we can solve $Ux = y$, which is inexpensive because $U$ is upper triangular.
Note that $P, L$, and $U$ only need to be computed once.
