There is a way to reduce the complexity and make the system solvable in parallel. It is called Diakoptics (a method invented by Gabriel Kron). The methods primary use is for large electrical networks that have few interconnections like power grids. But you should be able to adapt it.
The complexity (for the case below) is reduced from $O(n^3)$ to $O(2(\frac{n}{2})^3)$ or $O(\frac{1}{4}n^3)$, the impact can be much greater if the system is divided it into more subsystems. For that case the complexity is ($s$-subsysems, $c$-interconnection points) $O(c^3)+O((\frac{n^3}{s²}))$, if the systems is divided into equaly sized subsystems. I'm not sure about the notation for multiple variables, but you should get the point.
In short:
Lets assume you have a $N \times N$ system, lets say you can divide the system into two systems with 1 connection point(plus reference when you look at electrical systems). The connection points are $m$ and $n$. Lets assume these systems are of the size $N_1=N/2$ and $N_2=N/2$ (for simplicitys sake). You should now solve them separately.
$\mathbf A_1^{-1}=\mathbf B_1$
$\mathbf A_2^{-1}=\mathbf B_2$
The next step is to put them back together, that is done with the help of the so called "Thevenin Matrix"(in our case it is 1$\times$1). You can look up the exact principle for higher orders(more connection points), but for this example it looks like: \begin{align} \mathbf{B_{TH}}=B_{1mm}+B_{2nn}-2B_{mn} \end{align} For our case we have $B_{mn}=0$. Now we need the solutions $x_1$ and $x_2$ to form the coefficients $b_{th}$.
$\mathbf x_{th}=x_{1m}-x_{2n}$
$\mathbf b_{p}=\mathbf{B_{TH}}^{-1} \mathbf x_{th}$
\begin{align} \mathbf b_{th}=\begin{bmatrix}0&\cdots&b_{p}&\cdots&-b_{p}&\cdots&0 \end{bmatrix}^T \end{align}
The $\mathbf b_{th}$ matrix only has nonzero elements at $m$ an $N/2 +n$. Now we can finally find the solution $x_n$ for the whole system: \begin{align} \mathbf x_n=\begin{bmatrix}x_1\\x_2 \end{bmatrix}-\begin{bmatrix}B_1&0\\0&B_2 \end{bmatrix}\begin{bmatrix}b_{th} \end{bmatrix} \end{align}
I'm more used to the engineering notation with $Z, I, U$ and so on, so excuse for non-standard symbol usage.