1
$\begingroup$

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?

1 Answers 1

3

Well,

  1. Decompose $\mathbf A$ with your favorite decomposition. (e.g. the LU decomposition, $\mathbf P\mathbf A=\mathbf L\mathbf U$).

  2. Solve the system $\mathbf A^\top\mathbf y=\mathbf c$ with your decomposition.

  3. 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$.

  • 0
    As 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