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

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.

• MATLAB will be using LU factorization. If you've stored the matrix in sparse form than MATLAB might be taking advantage of that, but your matrix is so tiny that simply using a dense LU factorization routine is probably faster. See the documentation on mldivide for an explanation of the algorithms it uses. – Brian Borchers Sep 30 '17 at 1:05

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$.