Solving a system of linear equations by solving subsystems

I have a bidiagonal block matrix $M$ of the form

$$M = \begin{pmatrix} A_1 & B_1 & & & & \\ &A_2 &B_2 & & & & \\ &&A_3&B_3 \\ &&& \ddots & \ddots &\\&&&&A_{n-1}&B_{n-1} & \\&&&&&A_n\end{pmatrix}$$

with $M \in \mathbb{R}^{mn}$ and $A_j, B_j$ denote $m \times m$ matrices, where $A_j$ are invertible. I am trying to solve a system of linear equations $M x = b$ for a given matrix $M$ of the form above and a vector $b$. However I need to solve it via solving $m \times m$ subsystems, without explicitly having the matrix $M$ , but just having their blocks $A_j,B_j$ stored in a suitable format. I do not quite know, however, how I can solve the whole system of linear equations by splitting it into parts.

Does anyone know what I can do here? I am trying to implement this in Maple at the moment, but I am rather looking for a mathematical answer, since I do not quite grasp how I can solve the whole system with iterative steps by solving so to say "smaller" systems. Any help is greatly appreciated!

• Use back-substitution. – Rodrigo de Azevedo May 13 '17 at 22:20

The idea is to solve sub-systems starting from the lower right corner of $M$ and the last $m$ components of $x$ and $b$. First solve
$$A_n x_{nm} = b_{nm}$$
where $x_{nm}$ and $b_{nm}$ denote the last $m$ components of $x$ and $b$. This will always be possible since $A_n$ is invertible.
Once you've done that solve for the next-to-last $m$ components of $x$, which I'll denote by $x_{(n-1)m}$:
$$A_{n-1}x_{(n-1)m} = b_{(n-1)m} - B_{n-1}x_{nm}$$