Consider a square $N \times N$ block-matrix $\mathbf{A}$, where each $n \times n$ block $\mathbf{A}_{ii}$ is either a dense block or a zero-block. So, $N$ denotes the number of blocks, $n$ denotes the size of each square block.
Random example for illustration: $$ \mathbf{A}=\left[ \begin{array}{ccccc} \mathbf{A}_{11} & \mathbf{0} & \mathbf{A}_{13} & \mathbf{A}_{14} & \mathbf{0} \\ \mathbf{A}_{21} & \mathbf{A}_{22} & \mathbf{0} & \mathbf{0} & \mathbf{A}_{25} \\ \mathbf{0} & \mathbf{0} & \mathbf{A}_{33} & \mathbf{A}_{34} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{A}_{43} & \mathbf{A}_{44} & \mathbf{0} \\ \mathbf{A}_{51} & \mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{A}_{55} \\ \end{array} \right] $$
Now, one wants to compute an LU decomposition of this block matrix with minimal fill-in.
I am generally aware of the algorithms for reducing the fill-in for general sparse matrices. Say, Matlab reference gives an overview of several methods and their effect on Cholesky factorization. However, these algorithms certainly do not give an optimal reordering to give an optimal structure for the factorization in preserving zeros. This is done for a very good reason: for a large sparse matrix, finding an optimal reordering is very expensive, unneeded, and is unlikely to give substantial benefits compared to the common relatively fast techniques.
However, I wonder if that can be slightly different for the factorization of a block-matrix. In this case, $N$ is an order of magnitudes smaller, and one might be willing to use very expensive [graph?] algorithms to find this optimal fill-in for a given block pattern.
I wonder:
- what family of algorithms should I look at?
- is there a canonical reference on this aspect of reducing fill-in? (my search is constantly swamped by results on reducing fill-in of simple sparse matrices not the block-wise case with its own peculiarities – as much more expensive algorithm can become feasible)?
- is it even a tangible problem for relatively small $N$?
Notes:
- In this example, all blocks have the same $n \times n$ size for simplicity, and I am interested in it. I might be interested in the example where each block is still square, but the block-sizes differ.
- For my applications, the number of blocks $N$ can range from 1 (trivial) to, say, 100, and $n$ is on the order of thousands (not that $n$ matters at all).
- I am willing to spend significant precomputation time (say 10$\times t_\text{LU}$) to analyze the pattern and come up with the best reordering
