A sparse MPC solver for walking motion generation (old version).: Cholesky decomposition of Schur complement

Once Schur complement is formed we can use Cholesky decomposition $\mbm{S} = \mbm{L}\mbm{L}^T$ . to obtain Langrange multipliers.

$\mbm{L} = \left[ \begin{array}{cccccc} \mbm{L}_{11} & \mbm{0} & \mbm{0} & \dots & \mbm{0} & \mbm{0} \\ \mbm{L}_{21} & \mbm{L}_{22} & \mbm{0} & \dots & \mbm{0} & \mbm{0} \\ \mbm{0} & \mbm{L}_{32} & \mbm{L}_{33} & \dots & \mbm{0} & \mbm{0} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \mbm{0} & \mbm{0} & \mbm{0} & \dots & \mbm{L}_{N-1,N-1} & \mbm{0} \\ \mbm{0} & \mbm{0} & \mbm{0} & \dots & \mbm{L}_{N,N-1} & \mbm{L}_{NN} \end{array} \right],$

Directly from observation we have

$\\ \mbm{S}_{11} = \mbm{L}_{11}\mbm{L}_{11}^T, \\ \mbm{S}_{12} = \mbm{S}_{21}^T = \mbm{L}_{11}\mbm{L}_{21}^T, \quad \mbm{L}_{21}^T = \mbm{L}_{11}^{-1}\mbm{S}_{12}, \\ \mbm{S}_{22} = \mbm{L}_{21}\mbm{L}_{21}^T + \mbm{L}_{22}\mbm{L}_{22}^T, \quad \dots$

In the second step $\mbm{L}_{21}^T$ is computed by forward substitution, and in the third step, forming $\mbm{L}_{22}$ requires the computation of the Cholesky factors of $\mbm{S}_{22} - \mbm{L}_{21}\mbm{L}_{21}^T$ .