Cost of solving systems of simultaneous linear equations

Question

Given $A,$ a $n \times n $ non-singular matrix and $B,$ a $n \times k$ matrix, I am interested in estimating the computational cost of solving $$AX=B$$ for different values of $k.$ Take as a reference the case $k=1,$ which is solving a linear system. In my problem, $n$ is around 500. How expensive would be to solve the problem with $k \sim 500$ compared to the case $k=1$? How many times as costful would that be? It must be, of course, much less that 500 times as costful, because it is enough to invert $A$ once.

Answer 1

I think you could take as an upper bound the worst case complexity for multiplying $A^{-1}$ $n\times n$ with $B$ $n \times k$, which is $O(n^2k)$.

Update: As noticed in the comments, i ignored the inversion which is $O(n^3)$. So the correct answer is $O(n^3)$ as in the answer from @loup blanc . My bad.

Answer 2

We assume that the entries of the matrices are floating point numbers (otherwise, the complexity is much greater) and that $A$ is not too badly conditioned. Moreover, $comp$, the complexity is (for us) the number of used couples of operations $(+,\times)$.

Method 1. We calculate the decomposition $A=LU$, $comp\sim n^3/3$. We solve $k$ equations $LUx=B_i,i=1\cdots,n$; $comp\sim n^2\times k$. Then $totalcomp\approx n^3/3+n^2k$.

Method 2. We calculate $A^{-1}$, $comp\sim n^3$; we calculate $A^{-1}B$, $comp\sim n^2\times k$. Then $totalcomp\approx n^3+n^2k$.

Conclusion. Method 1 is slightly better.