Time complexity of $(A-BD^{-1}C)^{-1}$

97 Views Asked by At

Assume that there is a block matrix $I\in\mathbb{R}^{p\times p}$ that can be partitioned into

$$ I=\begin{pmatrix} A & B \\ C & D \\ \end{pmatrix}\,, $$

where $A\in\mathbb{R}^{p_1\times p_1}\,$, $B\in\mathbb{R}^{p_1\times p_2}\,$, $C\in\mathbb{R}^{p_2\times p_1}$ and $D\in\mathbb{R}^{p_2\times p_2}$ with $p=p_1+p_2\,$.

I know that the inversion of $I$ via SVD is $\mathcal{O}(p^3)\,$. Now I am interested in the following two inversions:

$$ (A-BD^{-1}C)^{-1} $$

and

$$ D^{-1}\,. $$

The following are my steps to compute the time complexity:

  1. Computing $D^{-1}$ costs $\mathcal{O}(p_2^3)\,$;

  2. Computing $BD^{-1}$ costs $\mathcal{O}(p_1p_2^2)\,$;

  3. Computing $BD^{-1}C$ costs $\mathcal{O}(p_1^2p_2)\,$;

  4. Computing $A-BD^{-1}C$ costs $\mathcal{O}(p_1^2)\,$;

  5. Computing $(A-BD^{-1}C)^{-1}$ costs $\mathcal{O}(p_1^3)\,$.

Thus, the overall complexity is

$$ \mathcal{O}(p_1^3+p_2^3+p_1^2+p_1^2p_2+p_1p_2^2)\,, $$

which costs less than inverting $I$ with $\mathcal{O}(p^3)=\mathcal{O}\left((p_1+p_2)^3\right)\,$?

Could anyone please check if what I did above are correct or not?