Suppose that we have a $n\times n$ matrix $A$. We have its LU-factorization as $A=LU$ (or $PA=LU$ that $P$ is a permutation matrix). Now assume we change the last column of matrix $A$ and denote the new matrix as $A^\prime$. What is an efficient algorithm to find the LU-factorization of $A^\prime$ as $P^\prime A^\prime=L^\prime U^\prime$. If we look at the factorization process (Guassian elimination and partial pivoting), we can obviously find out that $P^\prime=P$ and $L^\prime=L$. Also $U$ and $U^\prime$ have the same entries except of in the last column. So only thing that we have to do, is to find the last column of $U^\prime$. What would be an efficient algorithm to find it?

  • 1
    $\begingroup$ Here is a similar previous question and detailed answer regarding the solution of multiple systems $Ax = b$ via LU decomposition where $A$ is perturbed by changing a single row. scicomp.stackexchange.com/questions/21303/… $\endgroup$
    – whpowell96
    Nov 9, 2023 at 16:58
  • 1
    $\begingroup$ You can take a look at the presentation "A Review of Sparsity and Stability in LU updates" by Michael Saunders web.stanford.edu/group/SOL/talks/12informs-saunders.pdf . Some key words that you want to search for and read about are eta-matrices (product form of the inverse), Forrest-Tomlin updates, Bartels-Golub updates . This is a well known problem in the optimization (particularly) simplex community. There are a lot of resources available online. $\endgroup$ Nov 11, 2023 at 4:26


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.