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!

  • $\begingroup$ Use back-substitution. $\endgroup$ – 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} $$

and so on. Note that the solution of each subsystem depends on the solution of the previous one (except for the first one, of course).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.