The other week I revisited an old classic factorization from my bachelors studies, the LU-factorization.
The LU factorization of a (square) matrix M finds lower and upper triangular matrices (L and U respectively) possibly together with a permutation matrix P so that $$PLU = M$$
Now the matrix $M$ which we in this question will consider to be sparse may not have the property of being "in-place friendly" in the sense that we can find an order to calculate the matrix vector multiplication $Mv$ in-place on the entries of $v$.
But $U$ and $L$ are due to their triangular nature both sure to have this property for a trivial order of calculations and a permutation matrix multiplication should be trivial to implement so that it also does this.
Now to the question. In which cases can we ensure that a sparse matrix $M$ will lead us to both matrices $L$ and $U$ being sparse? Much of the gains in numerical linear algebra is due to sparse matrix-vector multiplication being so fast to carry out so it would be vital to avoid breaking the sparsity if we are to benefit from this factorization.
Can we show that all sparse matrices have this property?
Or maybe only all matrices of some sub-set of sparse matrices will?
The most interesting sub-family for me personally are probably the convolutional matrices on a Cartesian lattice in 1 or more dimensions.
I am aware that the family of discrete wavelet lifting schemes introduced by Wim Sweldens have this property by construction. This means discrete convolutions for a large set of discrete wavelet filter banks are possible to factor in such a fashion although I am not sure if LU-factorization has any connection to their construction.
Own work
I have verified for a few convolutional matrices (both circulant and Toeplitz) that this is the case.