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

Specific Domains Optimization (Mathematical)
, , , ,
11

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

  • Decompose using the 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}