# How to solve Ax=b incrementally ?

Hi, everyone.

What I am struggling is the following problem. I have a linear matrix equation $Ax=b$, where $A$ is a known $n \times n$ large sparse real matrix, $x$ and $b$ are known $n \times 1$ vectors. Now, one entry of $A$ has changed into $a$ and we denote by this matrix $A'$. Since we make $b$ unchanged, the updated $A$ will cause the $x$ in the original linear eqaution accordingly changed to $x'$ such that $A'x'=b$. My goal is to find this new $x'$. A naive way is to re-solve $A'x'=b$. But since $A'$ is slightly different from $Ax=b$, is there any incremental way to fast solve $x'$ in $A'x'=b$ by taking advantage of the original equation $Ax=b$? Thank you very much for any of your kind suggestion!

Another method to update the solution is using the Sherman-Morrison formula: http://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula in your case, $u$ and $v$ are canonical basis vectors.

So basically you have to solve two linear systems with $A$ and then you can update the solution for all possible values of $A$ with little work. Solve $2n$ linear systems, and you can update as many times as you want every entry of $A$ (only one at a time though).

Not sure that this is really your best option though --- all depends on how many "modified systems" you have to solve with the same starting matrix $A$. We need more information from you to decide this.

[By the way, as already pointed out, you'd better use a linear system solver which is suitable for sparse matrices: sparse LU or iterative methods.]

An iterative scheme may do the trick. I would suggest looking into algorithms such as GMRES. Since you have a large, sparse matrix, there is a good chance you already have your matrix in a format that can be accepted by an iterative solver.

As Fumiyo Eda already mentioned, you can use an iterative method such as GMRES to resolve the system after the change to $A$.

If you want to use direct LU factorization rather than an iterative method, look into "rank one update" techniques for the LU factorization.

You can update p columns of de A Matrix with Woodbury matrix identity http://en.wikipedia.org/wiki/Woodbury_matrix_identity and solve an pxp system.

RR

• Well, that is basically the same as @Federico already proposed (although your link points to something more general, and in fact, more general than needed here). – Dirk Sep 10 '13 at 7:08