[FEA] support for stencil operators

[skoranne]

Is your feature request related to a problem? Please describe.
Is there any way to represent a sparse matrix given the location of its non zeros

Consider A= kron D I
Where D is the 5 point gem stencil

Describe the solution you'd like
There exists a way to represent a sparse matrix using minimal perfect hashing such that non zeros are represented as the output of a hash function given the flat address

Describe alternatives you've considered
Sparse matrix coming from linear discretized operators can be implemented using minimal perfect hashing such functions

Additional context
Add any other context or screenshots about the feature request here.

[skoranne]

I have presented the method at SPARSE DAYS 2025
https://sparsedays.cerfacs.fr/wp-content/uploads/sites/72/2025/05/Sparse-days-2025-booklet-1.pdf

[aartbik]

MatX is in the process of adding support for sparse tensors that is based on the Universal Sparse Tensor (UST) type (which encompasses many common storage formats such as sparse vectors, sparse matrices in COO, CSR, CSC, DCSR, DCSC, BSR, BSC, DIA etc. and with generalizations to sparse tensors). Consequently, we are very interested in learning more about this.

Can you share more details on your feature request? The link only brings us to abstracts of Sparse Days 2025.

[skoranne]

Consider a matrix with its flat address and its non zero value
You can concert the sparse matrix to a minimal hash function and encode the matrix by a lambda

This can always be done iff the number of UNIQUE non zero is low; this assumption is warranted under quantization like fp4

If the universe of unique non zero is small the sparse matrix can be encoded into a lambda

[aartbik]

I think the idea of converting a sparse matrix to a lambda (with minimal hash function) is understood. But do you have concrete suggestions and/or examples on how MatX can use this idea to accelerate computations on NVIDIA GPUs?

[aartbik]

Hi @skoranne, friendly reminder, can you share some of your papers on this (both on the ideas of 5 point stencil codegen as well as the details on your perfect hashing idea)?

[skoranne]

Hi AartYes the papers will soon be online at CERFACSKeeping the non zeros in a vector/array and indexing them in the sparse matrix is an alternative representation which does not need the hash function and allows new non zeros to be createdSandeep On Jun 26, 2025, at 1:13 PM, Aart Bik ***@***.***> wrote:aartbik left a comment (NVIDIA/MatX#978) Hi @skoranne, friendly reminder, can you share some of your papers on this (both on the ideas of 5 point stencil codegen as well as the details on your perfect hashing idea)? —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you were mentioned.Message ID: ***@***.***>

[skoranne]

https://sparsedays.cerfacs.fr/wp-content/uploads/sites/72/2025/06/SKORANNE_SPARSEDAYS_2025_MINSPM.pdfOn Jun 26, 2025, at 1:41 PM, Sandeep Koranne ***@***.***> wrote:Hi AartYes the papers will soon be online at CERFACSKeeping the non zeros in a vector/array and indexing them in the sparse matrix is an alternative representation which does not need the hash function and allows new non zeros to be createdSandeep On Jun 26, 2025, at 1:13 PM, Aart Bik ***@***.***> wrote:aartbik left a comment (NVIDIA/MatX#978) Hi @skoranne, friendly reminder, can you share some of your papers on this (both on the ideas of 5 point stencil codegen as well as the details on your perfect hashing idea)? —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you were mentioned.Message ID: ***@***.***>

[skoranne]

https://sparsedays.cerfacs.fr/wp-content/uploads/sites/72/2025/06/SKORANNE_SPARSEDAYS_2025_MINSPM.pdf