I am analyzing the run time of an algorithm that depends on finding a solution to the linear system $A x = b$ where $A$ is an $m \times n$ matrix and need to know the run time complexity of this operation.
If $A$ is an $n \times n$ matrix the linear system of equations $A x = b$ can be solved by calling a matrix multiplication algorithm. The Coppersmith-Winograd algorithm multiplies two $n \times n$ matrices in $O(n^{2.375477})$ time. However, I'm assuming more goes into solving the linear system than just a call to this algorithm. What is the complexity of solving a linear system using this implementation? Can we get a similar run time complexity for $m \times n$ matrices?