1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – grok Jan 27 '19 at 16:05
  • $\begingroup$ Here is a link to the book (available as ebook): doi.org/10.1137/1.9780898718881 $\endgroup$ – grok Jan 30 '19 at 15:26
1
$\begingroup$

I was confused -- the algorithm does not produce sorted columns, only topologically sorted ones. To obtain a bona fide matrix, one must use e.g. the trick of transposing it twice.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.