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?

Question

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.

Answer 1

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]$$

Answer 2

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.