I have a large matrix, with possibly over 100,000,000 elements in it and I want to solve it quickly. I want to take advantage of the fact that the matrix is partitioned into a small number of unique blocks, arranged in a symmetrical manner similar to a tridiagonal matrix.

$$ \begin{matrix} a & b & c & d & 0 & 0 & 0 & 0 & 0 \\ e & f & b & c & d & 0 & 0 & 0 & 0 \\ g & b & f & b & c & d & 0 & 0 & 0 \\ h & c & b & f & b & c & d & 0 & 0 \\ 0 & d & c & b & f & b & c & d & 0 \\ 0 & 0 & d & c & b & f & b & c & h \\ 0 & 0 & 0 & d & c & b & f & b & g \\ 0 & 0 & 0 & 0 & d & c & b & f & e \\ 0 & 0 & 0 & 0 & 0 & d & c & b & a \end{matrix} $$ where a, b, c, d, e, and f are all $n \times n$ matrices whose determinants are known. Is there some way I could apply Gaussian Elimination at the block level so as to preserve the limited number of unique blocks I have, while finding the solution?

Update: The sub-matrices are commutable.