If $A$ is an $n\times n$ nonsingular matrix, and $b$ , $c$ are column vectors of length $n$. Is there an algorithm I can use to compute the matrix $W = bc^\top A^{-1}$ in $\frac{2}{3}n^3 + O(n^2)$ flops?
Is there an algorithm to compute this matrix at $\frac{2}{3}n^3 + O(n^2)$ flops?
1
$\begingroup$
linear-algebra
numerical-methods
1 Answers
3
Well,
Decompose $\mathbf A$ with your favorite decomposition. (e.g. the LU decomposition, $\mathbf P\mathbf A=\mathbf L\mathbf U$).
Solve the system $\mathbf A^\top\mathbf y=\mathbf c$ with your decomposition.
Form the outer product $\mathbf b\mathbf y^\top$.
I leave the details, including the flop counting, to you.
It seems the hints I gave earlier wasn't sufficiently clear, so here's another:
$\mathbf A^{-\top}=\mathbf P\mathbf L^{-\top}\mathbf U^{-\top}$
where $\mathbf A^{-\top}$ denotes the inverse of $\mathbf A^\top$.
You should now be able to figure how to use the LU decomposition of $\mathbf A$ to generate the column vector $\mathbf y$.
-
0As I said, do the flop counting yourself. How much flops does an LU decomposition take? A backsubstitution? $F$orming an outer product? – 2012-07-24