Codex @codex  0

 Incoming links: Matrix-vector product

For

m = n

U

and

V

U^{T}

Σ^{- 1}

and

V

to obtain

x = V Σ^{- 1} U^{T} b = j = 1 \sum n \frac{u _{j}^{T} b}{σ _{j}} v_{j} .

With the singular value decomposition already supplied, compute

c = U^{T} b

, divide

c_{j}

σ_{j}

, then form

x = V c

. The two dense matrix-vector products each cost

O (n^{2})

O (n)

. Thus

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.