Methods for solving $Ax=b$, small and sparse A

Question

I'm trying to solve/implement a system of linear equations of the following form/structure: $$ Ax=b$$

$$A = \begin{bmatrix} * & * & 0 & * & -1 & 0 & 0 & 0 \cr * & * & * & 0 & 0 & -1 & 0 & 0 \cr 0 & * & * & * & 0 & 0 & -1 & 0 \cr * & 0 & * & * & 0 & 0 & 0 & -1 \cr 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \cr 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \cr 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{bmatrix} ,\quad b = \begin{bmatrix} 0\cr 0\cr 0\cr 0\cr 1\cr 1\cr 1\cr 1 \end{bmatrix} $$

where *'s indicate non-negative numbers (some or all of these could be zeros as well, but very unlikely).

Does anyone have any suggestions on what algorithms I should look into to solve this specific problem?

One thing to point out is that I'm doing this to solve for KKT (Karush–Kuhn–Tucker) conditions with 4 inequality constraints, so I have to re-solve the above equation multiple times in order to get an optimal solution by removing one or more columns and rows 5 through 8.

I'm currently solving this in MATLAB using mldivide, but I'm not sure what specific algorithm they are using to solve for this.

Answer 1

By direct substitution, trivially. $$ \begin{bmatrix} 0\\f \end{bmatrix} = \begin{bmatrix} M & -I\\ I & 0 \end{bmatrix} \begin{bmatrix} y\\z \end{bmatrix} = \begin{bmatrix} My-z\\ y \end{bmatrix} $$ gives $y=f$, $z=My$.