Algorithm for solving systems which are nearly symmetric/adjoint?

Question

I am familiar with Cholesky decomposition and LU factorization for solving systems of linear equations.

I have a problem where I have large sparse matrices (say, 1000x1000 or larger) where only one or two rows/columns (last couple rows/columns) break symmetry. I understand that Cholesky is nearly twice as efficient as LU, but I can't use Cholesky due to these outlier rows/columns.

Is there another method or algorithm that can handle this particular case - i.e., take advantage of the fact that nearly the entire matrix is self-adjoint/symmetric (real values only here)?

Answer 1

Let's express the matrix $A \in \mathbb{R}^{n \times n}$ with which we want to solve linear systems as $$ A = S + U V $$ where $S$ is a symmetric matrix, $U \in \mathbb{R}^{n \times r}$, and $V \in \mathbb{R}^{r \times n}$. That is, $U V$ is a low rank update to account for the lack of symmetry. From your question, it appears $r$ is just 1 or 2.

The Woodbury matrix identity tells us that $$ A^{-1} x = (I_{n \times n} - \underbrace{S^{-1} U (I_{r \times r} + V S^{-1} U)^{-1}}_{W} V) S^{-1} x = (I_{n \times n} - W V) S^{-1} x. $$ Now, inverses appear for the symmetric matrix $S$. During the preprocessing step, you can compute the Cholesky factorization of $S$ and precompute $W = S^{-1} U (I_{r \times r} + V S^{-1} U)^{-1}$. Note that $W$ only requires $\mathcal{O}(r n^2)$ flops to compute, and that should be neglidgible.

After preprocessing, a linear system can be solved with $(I_{n \times n} - W V) S^{-1} x$. Working right to left, we can use forward/back substitution to compute $S^{-1} x$. Then, we need to perform a matrix-vector multiplication with $\left( I_{n \times n} - W V \right)$. At a cost of $\mathcal{O}(r n)$, that is neglidgible.