A Sherman-Morrison approach to the solution of linear systems (Q818235)

An algorithm is proposed to solve a linear system \(Ax=b\) (\(A\in{\mathbb R}^{n\times n}\)) by writing \(A=A_0+P_1+\cdots+P_n\) where \(A_0=\text{diag}(A)\) and \(P_k\) is the rank one matrix that adds the off diagonal elements in the \(k\)th row of \(A\). First \(A_0 x_0 = b\) is solved, and then this solution is updated as implied by the Sherman-Morrison inversion formula for the \(n\) rank one modifications \(P_k\). The complexity is comparable to Gaussian elimination. When some pivoting strategy is implemented, also the accuracy is similar to Gaussian elimination with partial pivoting.