#1




Sparse LU decomposition
So I have a symmetric, semi positive definite matrix I want to decompose. It's formed from a rectangular matrix J (cxb, where c <= b) and a diagonal matrix M (cxc) by J * M * J^T. This matrix itself isn't necessarily sparse, but J sure is (each row has at most k non zero elements, no matter the size of c or b).
So my thinking at the moment is to try and LU decompose J. Because it's rectangular, my thought was to find additional rows to add to it to make it square, and just be sure that each new row is orthogonal to existing rows. That is, for each new row (c'), and each existing row (c), c * c' = 0. That way adding new rows won't influence the existing rows in any way. I also want to make sure that the resulting square matrix isn't singular. So first question: is this a reasonable approach? Or am I being silly to add new rows, and there's a much easier way to go about this? Also, what's the most efficient (as in easy to calculate and preserves sparsity) way to calculate these additional rows? After making J square, I can LU decompose it. Since J is so sparse, I figured there would be good techniques to use to take advantage of its sparseness. But I'm not finding any good articles on sparse LU decomposition. There's the comment in NR about choosing a good pivot. And there's manual pages online about various linear algebra packages and how to use their sparse matrix solvers, but I'm not finding much else. My thinking is that you should be able to decompose J in O(b*k) time, but I'm not sure how to prove or disprove it. Likewise once J is decomposed, the SPD matrix I really want to decompose can be expressed as L * U * M * U^T * L^T. I want to be able to show that you can use that decomposition to solve a linear system in linear time, if you take advantage of the sparseness. But again, I'm having a hard time figuring out how to approach it, and there isn't much literature available online about it. So any thoughts/hints/links anyone can share would be appreciated. 
Thread Tools  
Display Modes  

