Skip to content
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

Add range minimum query kernels #1764

Open
wants to merge 29 commits into
base: develop
Choose a base branch
from
Open

Add range minimum query kernels #1764

wants to merge 29 commits into from

Conversation

upsj
Copy link
Member

@upsj upsj commented Jan 11, 2025

This adds a data structure to answer queries of the kind $\text{argmin}_{i \in [a,b]} \text{array}[i]$ in constant time. This will be used to speed up the computation of LCAs in the symbolic Cholesky algorithm, turning the counting step from $O(nnz(L))$ algorithm to a $O(nnz(A))$ algorithm.

The corresponding Wikipedia articles describe the algorithms pretty well https://en.wikipedia.org/wiki/Range_minimum_query, the constant time query is described in more detail in J. Fischer and V. Heun, “Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays,” SIAM J. Comput., vol. 40, no. 2, pp. 465–492, Jan. 2011, doi: 10.1137/090779759.

TODO:

  • add test for device queries

@upsj upsj added the 1:ST:ready-for-review This PR is ready for review label Jan 11, 2025
@upsj upsj requested a review from a team January 11, 2025 13:33
@upsj upsj self-assigned this Jan 11, 2025
@ginkgo-bot ginkgo-bot added reg:build This is related to the build system. reg:testing This is related to testing. mod:core This is related to the core module. mod:cuda This is related to the CUDA module. labels Jan 11, 2025
@ginkgo-bot ginkgo-bot added mod:reference This is related to the reference module. mod:hip This is related to the HIP module. labels Jan 11, 2025
@yhmtsai
Copy link
Member

yhmtsai commented Jan 13, 2025

my first impression on turning $O(nnz(L))$ to $O(nnz(A))$ is more operation.
do I miss something?

@upsj
Copy link
Member Author

upsj commented Jan 13, 2025

L includes fill-in, A does not

@MarcelKoch MarcelKoch self-requested a review January 14, 2025 08:32
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
1:ST:ready-for-review This PR is ready for review mod:core This is related to the core module. mod:cuda This is related to the CUDA module. mod:hip This is related to the HIP module. mod:reference This is related to the reference module. reg:build This is related to the build system. reg:testing This is related to testing.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants