# Sparse, left-looking LU factorization

I'm trying to understand the left-looking LU factorization algorithm for sparse matrices, by reading T.A. Davis' book, and have trouble in one step (sorry for the specific question) about returning sorted vectors.

The algorithm cs_lu is supposed to return a CSC matrix, i.e. compressed, sorted columns. There is a routine cs_spsolve that solves a linear system $$L x=b$$ for a lower-triangular matrix $$L$$ and a compressed column vector $$b$$; however, the result $$x$$ is not returned as a sorted vector, but only "topologically sorted", namely the nonzero entries $$x_i$$ only satisfy the guarantee that $$x_i$$ is after $$x_j$$ if there is a path $$L_{i,i_1},L_{i_1,i_2},\dots,L_{i_n,j}$$ of nonzeros in $$L$$.

Still, this vector $$x$$ is used directly as a new column of the result. My question: how can one guarantee that the columns of the result $$L$$ are sorted, without actually sorting them? Why is the code (Section 6.2, page 87) even correct? [To clarify: I'm sure it's correct, I just don't see why...]

Many thanks!

• I should add that I'm interested for other reasons than only understanding the algorithm: I could apply "sparse matrix*sparse vector -> sparse vector" in other contexts. – grok Jan 27 '19 at 16:05
• Here is a link to the book (available as ebook): doi.org/10.1137/1.9780898718881 – grok Jan 30 '19 at 15:26