Blockbidiagonal

Blockbidiagonal refers to a matrix structure organized in blocks where nonzero blocks appear only on the main block diagonal and on one adjacent block diagonal, forming a two-band pattern. This generalizes the scalar bidiagonal form to matrices composed of small blocks. A block upper bidiagonal matrix, for example, has the form A = [B1 C1 0 … 0; 0 B2 C2 … 0; …; 0 0 … Bn], where Bi and Ci are p×p blocks and the zeros fill the remaining positions. A block lower bidiagonal variant replaces the superdiagonal blocks Ci with subdiagonal blocks Di. The total size of such a matrix is n·p by n·p, with n blocks along the main diagonal and p the size of each block.

Properties and computation: The block bidiagonal structure implies a sparsity pattern that enables efficient numerical algorithms. Solving Ax = b can be performed by forward and backward substitutions that exploit the two-band form, typically with cost scaling like O(n p^3) for dense p×p blocks, which is advantageous when p is modest. Factorizations such as block LU or block QR can be tailored to preserve the structure, reducing fill-in and improving cache performance.

Applications: Block bidiagonal matrices arise in discretizations of two-dimensional problems, such as finite-difference schemes for Poisson-type equations, as well as in certain Markov chains, control theory, and dynamic programming problems where state-space representations are naturally partitioned into blocks.

Example: For n = 3 and block size p, an upper block bidiagonal matrix has nonzeros only in B1 and C1 in the first block row, B2 and C2 in the second, and B3 in the last, with all other off-diagonal blocks zero.