# Solving a Shifted Linear System of 2 Symmetric Positive Semi Definite (SPSD) Matrices

**URL:** <https://discourse.julialang.org/t/solving-a-shifted-linear-system-of-2-symmetric-positive-semi-definite-spsd-matrices/131636>\
**Category:** Optimization (Mathematical)\
**Tags:** linearalgebra, convex-optimization, linear-regression, linearsolve, least-squares\
**Created:** [August 16, 2025, 10:47am UTC](https://discourse.julialang.org/t/solving-a-shifted-linear-system-of-2-symmetric-positive-semi-definite-spsd-matrices/131636 "2025-08-16T10:47:40Z")\
**Posts on this page:** 1\
**Showing post:** 11

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [August 17, 2025, 5:06pm UTC](https://discourse.julialang.org/t/solving-a-shifted-linear-system-of-2-symmetric-positive-semi-definite-spsd-matrices/131636/11 "2025-08-17T17:06:58Z")

</div>

OK, I think I missed it for some reason, but I can do as following:

- Decompose using the [LDL Decomposition](https://en.wikipedia.org/wiki/Cholesky_decomposition#LDL_decomposition): \boldsymbol{C} = \boldsymbol{L} \boldsymbol{D} \boldsymbol{L}^{T}.
- Multiply both ends of the equation by \boldsymbol{L}^{-1} to yield \boldsymbol{L}^{-1} \left( \boldsymbol{A} + \lambda \boldsymbol{L} \boldsymbol{D} \boldsymbol{L}^{T} \right) \boldsymbol{L}^{-T} \boldsymbol{L}^{T} \boldsymbol{x} = \boldsymbol{L}^{-1} \boldsymbol{b}.
- Define \boldsymbol{E} = \boldsymbol{L}^{-1} \boldsymbol{A} \boldsymbol{L}^{-T}, \boldsymbol{y} = \boldsymbol{L}^{T} \boldsymbol{x} and \boldsymbol{f} = \boldsymbol{L}^{-1} \boldsymbol{b} will yield \left( \boldsymbol{E} + \lambda \boldsymbol{D} \right) \boldsymbol{y} = \boldsymbol{f} where \boldsymbol{E} is SPSD.
- The case where \boldsymbol{D} is all positive is solved easily (See above or Shifted Krylov methods).
- The motivation for this case is some values are zeros. In this case the system should be decomposed into zeros and non zeros (Block System). It can be tuned into a form of a smaller system with all positive diagonal system.

For more complexity one can use Eigen Decomposition on \boldsymbol{C} and go through the same logic with Orthogonal Matrices instead of Triangular.

### Solving Shifted System with Non Negative Diagonal Matrix

This section describes how to solve the following case:

\left( \boldsymbol{E} + \lambda \boldsymbol{D} \right) \boldsymbol{y} = \boldsymbol{f}

Where {D}\_{i, i} \geq 0 and \boldsymbol{E} \in \mathcal{S}\_{+}^{n}.

Since some of the last elements are zeros \boldsymbol{D} = \operatorname{Diag} \left( \begin{bmatrix} \boldsymbol{d}\_{s} \\ \boldsymbol{d}\_{z} \end{bmatrix} \right) where {{d}\_{s}}\_{i} \> 0. One can reformulate the problem accordingly:

\left( \begin{bmatrix} \boldsymbol{E}\_{SS} & \boldsymbol{E}\_{SZ} \\ \boldsymbol{E}\_{SZ} & \boldsymbol{E}\_{ZZ} \end{bmatrix} + \alpha \operatorname{Diag} \left( \begin{bmatrix} \boldsymbol{d}\_{s} \\ \boldsymbol{d}\_{z} \end{bmatrix} \right) \right) \begin{bmatrix} \boldsymbol{y}\_{s} \\ \boldsymbol{y}\_{z} \end{bmatrix} = \begin{bmatrix} \boldsymbol{f}\_{s} \\ \boldsymbol{f}\_{z} \end{bmatrix}

The system can be decomposed into 2 systems:

\begin{align\*} \left( \boldsymbol{E}\_{SS} + \lambda \operatorname{Diag} \left( \boldsymbol{d}\_{s} \right) \right) \boldsymbol{y}\_{s} + \boldsymbol{E}\_{SZ} \boldsymbol{y}\_{z} & = \boldsymbol{f}\_{s} \\ \boldsymbol{E}\_{SZ} \boldsymbol{y}\_{s} + \boldsymbol{E}\_{ZZ} \boldsymbol{y}\_{z} & = \boldsymbol{f}\_{z} \end{align\*}

Define \boldsymbol{u} = \boldsymbol{E}\_{ZZ}^{-1} \boldsymbol{f}\_{z}, \boldsymbol{v} = \boldsymbol{f}\_{s} - \boldsymbol{E}\_{SZ} \boldsymbol{u}, \; \boldsymbol{P} = \boldsymbol{E}\_{ZZ}^{-1} \boldsymbol{E}\_{ZS}, \; \boldsymbol{Q} = \boldsymbol{E}\_{SS} - \boldsymbol{E}\_{SZ} \boldsymbol{P} and form the system:

\left( \boldsymbol{Q} + \lambda \operatorname{Diag} \left( \boldsymbol{d}\_{s} \right) \right) \boldsymbol{y}\_{s} = \boldsymbol{v}

Which is a Shifted System of SPSD matrix + Positive Diagonal which can be solved as above.  
To recover \boldsymbol{y}\_{z} use \boldsymbol{y}\_{z} = \boldsymbol{u} - \boldsymbol{P} \boldsymbol{y}\_{s}

---

_[View the full topic](https://discourse.julialang.org/t/solving-a-shifted-linear-system-of-2-symmetric-positive-semi-definite-spsd-matrices/131636)._