Numerical Recipes Forum  

Go Back   Numerical Recipes Forum > Obsolete Editions Forum > Methods: Chapters 2, 11, and 18

Thread Tools Display Modes
Old 07-30-2009, 02:01 PM
Numsgil Numsgil is offline
Registered User
Join Date: Jul 2009
Posts: 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.
Reply With Quote

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

All times are GMT -5. The time now is 11:31 PM.

Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.