I have a class of matrices $A$ which are created by a domain decomposition method. Each matrix represents several subproblems of equal size, and I know that for some permutation matrix $P$, $PAP^T$ will be a block diagonal system, i.e. $$ A = \begin{bmatrix} A_1 & 0 & 0 \\ 0 & A_2 & 0 \\ 0 & 0 & A_3 \\ \end{bmatrix} $$ Solving this system for some right hand side is obviously just a matter of inverting each block and permuting back to he original ordering. The question is if there are any methods for such systems when the ordering required to permute the system into block diagonal form is not known.
- One approach would be to interpret the matrix system as a graph, and try to find cycles. The system can then be permuted by ordering according to each cycle. The question is then what algorithms are fast and suitable for the purpose?
- The condition number of such a system is often much lower than that of an similar system where the blocks are connected because the eigenvalues are that of each subblock. A question of general interest could be what algorithms are good at solving such systems without actually permuting the system - CG would probably converge faster for a more decoupled system because of the lowered condition number. Are some algorithms better for this type of problem?
- Is there a known nomenclature for such systems? When searching for inversion/permutation of block diagonal matrices, what I usually find is systems which are block diagonal except for the last row - a different problem, really.
While I have no problems solving each system, I thought this question was interesting. The submatrices can be thought of as similar to the five point stencil for the heat equation in terms of matrix properties - they arise from a similar mass conservation system. (I hope this is of general interest, so focusing on the structure of the submatrices is not very important)