search

pydata / sparse

Sparse multi-dimensional arrays for the PyData ecosystem
https://sparse.pydata.org
BSD 3-Clause "New" or "Revised" License
585 stars 125 forks source link

Sparse Cholesky Decomposition #286

Open TomMaullin opened 5 years ago

TomMaullin commented 5 years ago

I was recommended to ask this on the dask github issues threads here.

Would it be possible to implement a Cholesky Decomposition function for Sparse matrices? I understand this may not be a high priority currently but would be enormously helpful in the future!

hameerabbasi commented 5 years ago

Hi! Why do you need the decomposition? Is it to solve a system of linear equations? If so, sparse.solve exists.

TomMaullin commented 5 years ago

Hey! I am performing sparse numerical optimisation for mixed effects model estimation. To ensure certain matrices remain positive definite during the optimisation I need to perform a cholesky factorisation and work with the cholesky factor. This work is based on the paper behind the lme4 package in R (see here if you would like more information).

Also: Oh! I wasn't aware of sparse.solve - It doesn't solve the problem I have but will certainly be useful - I can't seem to find it in the documentation! Does it broadcast?

hameerabbasi commented 5 years ago

Edit: I was wrong, it doesn’t exist yet.

Harivallabha commented 4 years ago

Hi! I think scikit-sparse has the sparse cholesky decomposition implemented under sksparse.cholmod Sparse Cholesky Is this what you're looking for?

TomMaullin commented 4 years ago

Hi, it does yes thank you. However this decomposition may be run hundreds of thousands of times in my code and ideally everything would be done in sparse as the overhead for converting the data between different packages' sparse matrix formats becomes quite large with increasing iterations. Also `scikit-sparse' is no longer maintained and was ruled out of my work due to potential future compatibility issues.

I did try cvxopt which is the current winner - however ideally I need to perform as much as I can eventually in a parallel or vectorised form and as sparse is the chosen implementation for dask, and the dense parts of my code are already dask compatible, I thought id be best ask here first about a single sparse cholesky decomposition.

Harivallabha commented 4 years ago

Ah right, I see. That makes perfect sense.

hameerabbasi commented 4 years ago

We have a lot of linear algebra to get to before we can implement this. I'll leave this open to track it.

MickaelRigault commented 2 years ago

Hi all, I was wondering if we had any news concerning this development ?

hameerabbasi commented 2 years ago

I believe the functions in SciPy now accept sparse arrays.