Existence of sparse LU decomposition of sparse matrix

Question

Let $A$ be a sparse matrix over some field. I would like to know about the existence of LU decompositions so that $L,U$ are both sparse.

More precisely, let $A$ be an $N$-by-$N$ matrix. Suppose each row and column of $A$ has only $O(1)$ nonzero entries. I am looking for a decomposition of the form $A=PLUQ$ where $P,Q$ are permutation matrices. I would like to know what kind of sparsity of $L,U$ is achievable with an optimum choice of $P,Q$.

If one cannot show that $L,U$ can both be made sparse (or even log sparse), I would be satisfied with a weaker requirement: I would like to find a choice of $P,Q$ that bounds the number of nonzero entries of $L,U$. So, it would be acceptable to have, for example, one row of $L$ having $N$ nonzero entries so long as all other rows only had a few entries.

My understanding from Yannakakis's paper "Minimum fill-in is NP-complete" is that actually finding an optimum is NP-complete. However, I would like to know if there is some general upper bound on how good the optimum is.

Answer 1

It seems that the answer is that with high probability, a random sparse matrix (for an appropriate choice of probability distribution over matrices) does not have a sparse decomposition in this sense. This follows from a few known results. First, every choice of elimination order produces some fill-in, and the nonzero entries in the fill-in (assuming that the nonzero entries of the matrix A are chosen generically) define a chordal completion of a graph whose edges correspond to nonzero entries of the matrix A. See for example the Yannakakis paper in the question. Second, the treewidth of a graph is defined in several ways, but one definition is that the treewidth is the minimum, over chordal completions of the graph, of the size of the largest clique. Finally, this paper https://arxiv.org/pdf/1001.0461.pdf shows that, for an Erdos-Renyi random graph on n-vertices, with edges attached with probability p=c/n, then for any c>1, with high probability the graph has treewidth linear in n. Putting this together, if we consider sparse matrices corresponding to random graphs from that ensemble, then with high probability every choice of permutations P,Q will lead to some row of L having a linear number of nonzero entries.

Answer 2

For any matrix $A\in M_n(\mathbb{Q})$, we consider THE decomposition $A=PLU$ (given, for example by the Maple command LUDecomposition(.); that is, we fix the algorithm of decomposition).

Here $A$ is sparse (here we assume that $A$ has $n$ non-zero entries) and generic -for example, randomly choose $A$-. Let $z(n)$ the total number of non-zero entries $l_{i,j},i\not= j$ or $u_{i,j}$.

1. Experiments show that $E(z(10))\approx 10.8$ and $E(z(100))\approx 115.2$. In particular, $L,U$ are sparse.

Note that always $z(n)\geq n$ because $A$ depends on $n$ independent parameters and, from $P$ (which is in a finite set) and $L,U$ we can recover $A$; in the same way, $P$ is never $I_n$.

2. Now we assume that the non-zero entries of $A$ respect a given pattern, that is, we fix the list $\mathcal{L}=\{[i_1,j_1],\cdots,[i_k,j_k]\}$ of the indices of non-zero entries of $A$. Then, there is an associated pattern for $P,L,U$: if we do a generic choice of the parameters of $A$ in the fixed pattern, then $P$ is fixed and the non-zero entries of $=L,U$ will always be the same. Indeed, the patterns of $P,L,U$ can only change if some algebraic expressions are zero, which is impossible in the generic case.

Here are 2 extreme examples of patterns for $n = 10$.

where $z(A_1)=10$.

where $z(A_2)=15$.

To obtain the associated pattern of $P,L,U$, it suffices to test some random matrix $A$ respecting $\mathcal{L}$.

$\textbf{Conclusion.}$ 1. If $A$ respects a pattern, then $P,L,U$ respects some known pattern; it remains to study what can be practically done with it.

2. Of course, all this requires an infinite field $K$; or if we are satisfied with a large probability, then $ K $ may be a large finite field. Similarly, if the $ a_ {i, j} $ are bounded integers, then the bound must be large.

$\textbf{Answer to the OP.}$ Let $m(A),z(A)$ be the number of non-zero entries of $A$ and $L,U$ and let $n=100$.

If $m(A)=100$, then $E(z)\approx 115.2$ -an increase of 15%- with a maximum of $\approx 143$.

If $m(A)=200$, then $E(z)\approx 350$ -an increase of 75%- with a maximum of $\approx 446$ (less than 5% of the available $L,U$ entries).

You must choose $m(A) = 510$ to fill (on average) the third of the available $L,U$ entries.

Thus if, for example, $m(A)\leq 200$, $L,U$ are sparse and $P,L,U$ generically respect some pattern associated with that of $A$.

Now, if $A\in M_{100}$ is always sparse symmetric and respects a pattern with $m(A)\leq 200$, then some experiments seem to show that, generically, $L,U$ are sparse an $P,L,U$ respect some associated pattern.