-
Notifications
You must be signed in to change notification settings - Fork 203
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
New Sparse Matrix APIs #1279
New Sparse Matrix APIs #1279
Conversation
… fea-2304-sparse_matrix
cc @mhoemmen for thoughts |
… to capture the sparsity types
… having to care whether it's sparsity owning or preserving
Hi @cjnolet ! I do like the idea of distinguishing between structure-preserving formats and structure-owning formats. The latter show up, for example, when wrapping third-party libraries that ingest 3-array CSR and produce an optimized opaque format. Sometimes those libraries give users a way to modify values or even structure. Regardless, users still may want to take some structure-preserving or opaque format, and "dissolve" it to get a transparent, modifiable format. I'll take a look at the PR; thanks for tagging me! |
@mhoemmen, thanks so much! I'm looking forward to your feedback. I tried to find a way to generalize the different states w/ nomenclature that we could apply directly to the different options. |
… fea-2304-sparse_matrix
Co-authored-by: Divye Gala <[email protected]>
Co-authored-by: Divye Gala <[email protected]>
Co-authored-by: Divye Gala <[email protected]>
Opened up docs issue as follow-on #1342. |
/merge |
Closes #348.
This design addresses some problems we've had in the past when modeling sparse data where our objects were not flexible nor composable enough, which led to APIs which were hard to maintain and state which was hard to track.
This design starts by decomposing sparse formats into two components which are utlimately combined to compose the full sparse object:
structural
component manages the sparsity of the object , indexing, and data-specific metadata, such as total number of rows and columns.valued
ormatrix
component combines with a structure and manages the nonzero elements.Note that this design also affords the ability to model a sparse tensor in the future, as a new format
tensor
could allow for composing multiple structural and multiplevalued
components. This could enable our algorithms to support things decompositions of higher ordered structures and/or associated values.In addition to being flexible and composable, this design also needs to satisfy a couple different levels of immutability:
Two concepts introduced in this design are pretty core to the 3 states above:
structure-preserving
formats are views and require the sparsity to be known at creation time. The actual structural components may or may not be mutable.structure-owning
formats house owning containers and don't require the sparsity to be known at creation time and provide a way toinitialize()
the sparsity once it is known. These formats will have mutable structure and nonzero elements.Both the
structure
andmatrix
formats can bestructure-preserving
orstructure-owning
. While this PR only includescsr_matrix
andcoo_matrix
(I'm considering dropping ther
fromcsr
since it doesn't really matter if it's csr or csc), the design will further allow for other formats, such asdcsr
andbcsr
, in the future.csr_matrix_view
- this is astructure-preserving
matrix view. Sparsity must be known up front and the underlying arrays may or may not beconst
.csr_matrix
- this can bestructure-owning
orstructure-preserving
depending on whether its underlying structural component isstructure-preserving
(view) orstructure-owning
. Callingview()
on this object produces thecsr_matrix_view
above.coo_matrix_view
- this is astructure-preserving
matrix view. Sparsity must be known up front and the underlying arrays may or may not beconst
.coo_matrix
- this can bestructure-owning
orstructure-preserving
depending on whether its underlying structural component isstructure-preserving
(view) orstructure-owning
. Callingview()
on this object produces thecsr_matrix_view
above.Similar to
mdarray
andmdspan
, a bunch of factory functions are provided inraft/core/device_sparse_matrix.hpp
to ease the construction process for users. The owning matrix types can be constructed either to own the underlying structure or a view of the structure.These new formats will allow us to model our sparse APIs so they are much more concise- a function can explicitly require a structure-owning matrix, which is a signal to the user that the function itself will compute the sparsity and at least fill in the initial structure. This will allow us to continue to provide an API which is easier to use, and ultimately feels more like our dense API, while still considering the design differences in sparse computations.
I also want to thank @divyegala for his help making the template metaprogramming layer flexible, reusable, and generally pleasant to use.