Feature Request: Sparse Cholesky decomposition

[rwolst]

System information

• Have I written custom code (as opposed to using a stock example script provided in TensorFlow):
• OS Platform and Distribution (e.g., Linux Ubuntu 16.04):
• TensorFlow installed from (source or binary):
• TensorFlow version (use command below):
• Python version:
• Bazel version (if compiling from source):
• GCC/Compiler version (if compiling from source):
• CUDA/cuDNN version:
• GPU model and memory:
• Exact command to reproduce:

Describe the problem

TensorFlow has a Cholesky decomposition kernel based on wrappers around the Eigen and cuSOLVER (for GPUs) libraries.

From experience, a sparse solver can provide huge speedups in the right circumstances. The cuSOLVER library has the feature in their sparse LAPACK library, cuSolverSP, and the Eigen library in the SparseCholesky module.

Alternatively, there is the CHOLMOD library which is supported by Eigen in the CholmodSupport module. This CHOLMOD library supports both CPU and GPU sparse Cholesky factorisations.

Would a Cholesky decomposition for sparse matrices be a feature of interest?

[skye]

@rmlarsen can you comment or redirect? Thanks!

[dpmerrell]

Let me revive this issue (and add something to it):

• At present there is a sparse Cholesky factorization hidden deep in TensorFlow. It's a little bit inconvenient, since it requires you to convert your SparseTensor to a "CSRSparseMatrix". It doesn't appear in the documentation.
  • source code
  • API definition
• I would add another "welcome contribution": a gradient method for the sparse Cholesky decomposition.
  • Backpropagation in this context would maintain the sparse structure.
  • I.e., if A=LL^T then backprop would only propagate the error in L to the nonzero entries of the lower triangle of A.

In the source for SparseMatrixSparseCholesky I see a few contributors. @kiszk @penpornk @bloops I wonder if you have thoughts about the sparse Cholesky decomposition and its gradient?

I have research interests related to this topic and would like to contribute, but I'm finding it difficult to learn TensorFlow's C++ API. I welcome any advice or suggestions.

[bloops]

Sure, @dpmerrell, I can help you with the TensorFlow implementation. Do you have the algorithm ready that you want to implement?

[chunduriv]

@rwolst,

Please check SparseMatrixSparseCholesky. Thanks!

[google-ml-butler[bot]]

This issue has been automatically marked as stale because it has no recent activity. It will be closed if no further activity occurs. Thank you.

[google-ml-butler[bot]]

Closing as stale. Please reopen if you'd like to work on this further.