1
$\begingroup$

Given $A, x, b$ and a linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ is full rank. Denote $A_{\backslash i}$ as a $(n-1)\times(n-1)$ matrix where $A$ removes its $i^{th}$ column and row, similarly $b_{\backslash i}$. What's the most efficient way to find a $y$ for each $i\in[n]$ s.t $A_{\backslash i}y=b_{\backslash i}$? (So in total these are $n$ linear systems, for different $i$ I want a different solution $y$).

I know one way is to use Sherman-Morrison formula, but is there any way that doesn't involve calculating $A^{-1}$? That is, suppose I have $x$ calculated, can $y$ be derived just using $A, x, b$?

Improve this question
$\endgroup$
14
  • $\begingroup$ When you write, "Given a linear system $Ax=b$," do you mean, given all three of $A,x,b$? When you write "find $A_{\backslash i}y=b_{\backslash i}$", do you mean "find $y$"? $\endgroup$
    – Gerry Myerson
    Commented Jul 14, 2020 at 3:03
  • $\begingroup$ Yes to both questions, I have modified the question. $\endgroup$
    – user3799934
    Commented Jul 14, 2020 at 3:08
  • $\begingroup$ Why don't you want to use $A^{-1}$ (or an equivalent factorization)? It seems the right tool for the job here. $\endgroup$
    – Federico Poloni
    Commented Jul 14, 2020 at 6:26
  • 1
    $\begingroup$ How would you use Sherman-Morrison formula? $\endgroup$
    – Vít Tuček
    Commented Jul 14, 2020 at 16:40
  • 3
    $\begingroup$ @FedericoPoloni it's roughly 80k*80k and dense. The issue is mostly with memory, I assume existing linear system solvers use iterative methods? Taking inverse seems to load the whole matrix into memory. $\endgroup$
    – user3799934
    Commented Jul 14, 2020 at 18:16

0

Reset to default

You must log in to answer this question.