= Solution
{c}
For $m=n$, $U$ and $V$ are square <orthogonal matrices>. Multiply the <linear system> successively by $U^T$, $\Sigma^{-1}$ and $V$ to obtain
$$
\boxed{x=V\Sigma^{-1}U^Tb
=\sum_{j=1}^n\frac{u_j^Tb}{\sigma_j}v_j.}
$$
With the <singular value decomposition> already supplied, compute $c=U^Tb$, 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)$. Thus
$$
\boxed{\text{Cost per right-hand side with supplied factors: }O(n^2).}
$$
If 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.
Back to article page
