sprs
sprs copied to clipboard
sparsemat
Profile reduction for cholesky factorizations
Hey again @vbarrielle, I thought we might continue this discussion in a new issue. I am a Student, I research profile reduction methods for a minor assignment, though mostly for my own personal joy. So I have to disappoint you if you believed me to be an expert on the topic.
I will fork the project to implement my version of the RCM algorithm, using the George-Liu pseudoperipheral vertex finder. I will ask any questions that may arise in this issue.
Here is the list of reading material you asked for. I have not read all of these entirely, for that matter, I don't think many humans have ever done that.
-
This is the essential book describing classsical methods for profile and bandwidth reduction. It describes methods for finding pseudoperipheral verices from page 70 onwards. It also describes the minimum degree reordering, which is generally superior for the fill-in reduction of Cholesky factorizations, from page 133 onward. I might also get around to implementing this ordering.
-
This is the technical report for the implementation of sparse matrices in matlab. It esssentially claims: "Our implementation of symrcm is very similar to the one implemented in SPARSPAK", along with some more general, very interesting remarks. SPARSPAK is the library described in the above book.
-
Though only tangential to this conversation, this is a recent paper reviewing a variety of different more modern methods, including FNCHC , GPS and NSloan.
One remark about starting vertices: While they (of course) barely matter for random matrices, their choice becomes increasingly important for problems with inherent structure. Pseudoperipheral verices have proven to be superior to simply minimum degree vertices in those cases, as described in the first linked book.
By the way, just to show a life sign after his little while: I have not forgotten about this project, and intend to implement AMD (or at least support you at implementing it) some time in the future. These last few months, and the upcoming weeks, I have been and will be busy with other matters though.
Glad to hear it! Meanwhile, I've started binding the CAMD part of suitesparse, and I'll probably do AMD next, so this should be nice to compare!
