Skip to content

Sparse inverse#1

Open
jluttine wants to merge 15 commits into
scikit-sparse:masterfrom
jluttine:master
Open

Sparse inverse#1
jluttine wants to merge 15 commits into
scikit-sparse:masterfrom
jluttine:master

Conversation

@jluttine

Copy link
Copy Markdown

The sparse inverse of sparse symmetric positive definite matrix K is a sparse matrix with the same sparsity structure (symbolically) as K but the non-zero elements are equal to the elements of the inverse of K. This pull request implements the sparse inverse method spinv for class Factor. Also, the documentation and the tests are updated accordingly.

The sparse inverse is implemented only for real matrices. In addition, only simplicial LDL and supernodal LL are implemented, these are the defaults in CHOLMOD. CHOLMOD doesn't support supernodal LDL, and simplicial LL would require one to change Common->final_ll to 1 but I think it is not possible through scikits.sparse interface.

For more details on the sparse inverse, see, for instance:
http://cholmod-extra.readthedocs.org/en/latest/functions.html#sparse-inverse

@njsmith

njsmith commented Nov 1, 2012

Copy link
Copy Markdown
Collaborator

Sorry for not getting back to you on this more promptly!

What do you mean by "simplicial LL would require one to change Common->final_ll to 1 but I think it is not possible through scikits.sparse interface."? Anything that can be done in C can be done in Cython -- is there some change needed to cholmod.pyx?

Comments:

  • can you rename the directory to cholmod_sparse_inverse or similar? We may e.g. add UMFPACK support at some point, but this code is clearly cholmod-specific.
  • the spinv function has a different license than either CHOLMOD or the rest of scikits.sparse. We need to either document this somewhere more visibly (including the docstring), or, would it be possible to relicense it under GPLv2-or-later instead of GPLv3-or-later, so it matches the rest of CHOLMOD? (And can you confirm that the bit of code you're okay with licensing the bit of code added to cholmod.pyx under the BSD? That also makes it easier to keep track of, if we can keep the whole file under a single license...)
  • Can you add a test that spinv does something sensible when called on a complex matrix? i.e., raises an appropriate exception (as opposed to returning nonsense or crashing).

@jluttine

jluttine commented Dec 5, 2012

Copy link
Copy Markdown
Author
  • By saying that "it is not possible to change Common->final_ll to 1 through scikits.sparse interface", I mean that the users of scikits.sparse do not have access to it via the Python interface of scikits.sparse. Of course, in scikits.sparse's Cython code (cholmod.pyx) it would be possible to change this, but at the moment it is untouched.
  • Yep, folder renamed to cholmod_sparse_inverse.
  • The C-code (the files in cholmod_sparse_inverse folder) is now GPLv2-or-later. I confirm that my bit of code in cholmod.pyx, setup.py and test_cholmod.py are licensed under the BSD.
  • Factor.spinv should now raise CholmodError exception for complex matrices. There is also a test for it in test_cholmod: test_spinv_complex.

@anntzer anntzer force-pushed the master branch 3 times, most recently from 9526c22 to bb2de35 Compare August 12, 2016 07:11
@anntzer anntzer force-pushed the master branch 5 times, most recently from 76c79c4 to bb2de35 Compare August 23, 2016 17:14
@anntzer anntzer force-pushed the master branch 3 times, most recently from 29df5b7 to 2ab1364 Compare October 14, 2016 17:56
@evfro

evfro commented Jan 1, 2019

Copy link
Copy Markdown

Hi! This feature would be indeed very helpful. Is there any chance that it will make it to one of the future releases?

@howsiyu

howsiyu commented Feb 19, 2023

Copy link
Copy Markdown

I'm also very interested in this.

@howsiyu

howsiyu commented Feb 19, 2023

Copy link
Copy Markdown

It seems like Suitesparse has implemented this though confusingly in MATLAB_Tools:
https://github.com/DrTimothyAldenDavis/SuiteSparse/blob/stable/MATLAB_Tools/sparseinv/sparseinv.c

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants