1
$\begingroup$

Let $A\in\mathbb R^{n\times n}$ be a symmetric positive-definite matrix and $A^{-1}$ is already known. Now I want to compute the matrix $(A+\sum_{i=1}^n B_i)^{-1}$ where each $B_i$ is a sparse symmetric matrix with only four non-zero elements that are placed on the rectangle, which has the following form: $$B_i=(e_j-e_k)(e_j-e_k)^T=\left[\begin{array}{ccccc} & & & & \\ & 1 & -1 & & \\ & & & & \\ & -1 & 1 & \\ & & & & \end{array}\right]$$ where $e_j$ is the $j$-th unit vector.

Such a problem has many practical values (such as in graph theory). I wonder if there is some algorithm to compute $(A+\sum_{i=1}^n B_i)^{-1}$ in $\Theta(n^2)$ time based on the known matrix $A^{-1}$. I have tried to use the Sherman-Morrison-Woodbury formula: $$(A+vv^T)^{-1}=A^{-1}-\frac {A^{-1}vv^T A^{-1}}{1+v^T A^{-1} v},$$ but it seems that each iteration has to update the full matrix and the overall complexity remains $\Theta(n^3)$ (which is the same as a direct matrix inversion). Since the summation $\sum_{i=1}^n B_i$ is still highly sparse and the structure of the matrix has a special form, I wonder whether it is possible to calculate the inversion efficiently in $\Theta(n^2)$ time. Thank you!

$\endgroup$
5
  • 1
    $\begingroup$ Similar issues are well-studied in the context of interior point methods for semidefinite optimisation. $\endgroup$ Sep 26, 2022 at 12:22
  • 1
    $\begingroup$ Can semidefinite optimisation achieve the optimal complexity? To my knowledge, optimization based methods typically give an approximate solution rather than exact one and the complexity depends on the desired error $\epsilon$. Could you please give some reference for related problems? Thank you! $\endgroup$
    – zbh2047
    Sep 26, 2022 at 12:32
  • 1
    $\begingroup$ Is it also true that the summation over B_i's is still such that the number of non-zero rows/columns is subdued by the growth of n? $\endgroup$ Sep 26, 2022 at 12:45
  • 1
    $\begingroup$ Each $B_i$ can have two non-zero rows/columns, so it is possible that all rows/columns of $\sum_i B_i$ are non-zero. But the matrix is still sparse and has no more than 4n elements. $\endgroup$
    – zbh2047
    Sep 26, 2022 at 12:47
  • $\begingroup$ step directions of path-following (interior-point) methods for semidefinite optimisation are updated in a similar way, not that computing such an $A^{-1}$ is the goal of semidefinite optimisation. $\endgroup$ Sep 27, 2022 at 12:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.