 Solution

For $m=n$, $U$ and $V$ are square orthogonal matrices. Multiply the linear system successively by $U^T$, ${\Sigma }^{-1}$ and $V$ to obtainWith the singular value decomposition already supplied, compute $c=U^{T}b$, divide $c_j$ by ${\sigma }_j$, then form $x=Vc$. The two dense matrix-vector products each cost $O(n^2)$ arithmetic operations in Big O notation, and the diagonal scaling costs $O(n)$. ThusIf the singular value decomposition first has to be computed, its usual dense cost is $O(n^3)$; that is a separate setup cost and can be reused for further right-hand sides.