I have the following linear system to solve:

\boldsymbol{A} \boldsymbol{x} = \boldsymbol{0}, \quad \text{subject to} \; {x}_{i} = {v}_{i} \; \forall i \in \mathcal{V}

Where \boldsymbol{A} \in \mathbb{R}^{m \times n} with m < n.

The matrix \boldsymbol{A} is a banded matrix (5-9 bands).

The set \mathcal{V} is a sub set of indices to force equality on a sub set of values of \boldsymbol{x}.

I wonder how to solve this in the most efficient way.

My current approach is to make this a Least Squares Problem:

\begin{align}
\arg \min_{\boldsymbol{x}} \quad & \frac{1}{2} \boldsymbol{x}^{T} \boldsymbol{B} \boldsymbol{x} \\
\text{subject to} \quad & \begin{aligned}
{x}_{i} & = {v}_{i}, \; \forall i \in \mathcal{V} \\
\end{aligned}
\end{align}

Where \boldsymbol{B} = \boldsymbol{A}^{T} \boldsymbol{A} is a Symmetric Positive Semi Definite (SPSD) matrix.

By defining a permutation matrix \boldsymbol{P} one can arrange the elements:

\begin{bmatrix} \boldsymbol{x}_{\mathcal{U}} \\ \boldsymbol{x}_{\mathcal{V}} \end{bmatrix} = \boldsymbol{P} \boldsymbol{x}

Which yields a partitioned formulation of the problem:

\boldsymbol{x}^{T} \boldsymbol{B} \boldsymbol{x} = \boldsymbol{x}^{T} \boldsymbol{P}^{T} \left( \boldsymbol{P} \boldsymbol{B} \boldsymbol{P}^{T} \right) \boldsymbol{P} \boldsymbol{x} = \begin{bmatrix} \boldsymbol{x}_{\mathcal{U}}^{T} & \boldsymbol{x}_{\mathcal{V}}^{T} \end{bmatrix} \begin{bmatrix} \boldsymbol{B}_{\mathcal{U}} & \boldsymbol{C} \\ \boldsymbol{C} & \boldsymbol{B}_{\mathcal{V}} \end{bmatrix} \begin{bmatrix} \boldsymbol{x}_{\mathcal{U}} \\ \boldsymbol{x}_{\mathcal{V}} \end{bmatrix}

Since only \boldsymbol{x}_{\mathcal{U}} is sought, the problem becomes:

\arg \min_{\boldsymbol{x}_{\mathcal{U}}} \frac{1}{2} \boldsymbol{x}_{\mathcal{U}}^{T} \boldsymbol{B}_{\mathcal{U}} \boldsymbol{x}_{\mathcal{U}} + \boldsymbol{x}_{\mathcal{v}}^{T} \boldsymbol{C} \boldsymbol{x}_{\mathcal{U}}

Which is a convex, smooth and constraint free problem.

Its minimization is given where the gradient vanishes:

\boldsymbol{B}_{\mathcal{U}} \hat{\boldsymbol{x}}_{\mathcal{U}} = - \boldsymbol{C} \boldsymbol{x}_{\mathcal{V}}

Which a simple linear system with SPSD matrix.

The advantages of this solution:

- Smaller constrained free system.
- SPSD system.

The weakness is being built by \boldsymbol{A}^{T} \boldsymbol{A} which increase the condition number.

Is there a better approach?

Usually Iâ€™d solve the last equation using the Conjugate Gradient solver in `Krylov.jl`

. Is there an optimized solver for this?

**Remark**: I also posted the question on StackExchange Computational Science.