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

Migrate PageRank and HITS implementations from sprs to faer #1248

Open
IvanIsCoding opened this issue Jul 11, 2024 · 1 comment
Open

Migrate PageRank and HITS implementations from sprs to faer #1248

IvanIsCoding opened this issue Jul 11, 2024 · 1 comment
Labels
enhancement New feature or request good first issue Good for newcomers

Comments

@IvanIsCoding
Copy link
Collaborator

IvanIsCoding commented Jul 11, 2024

What is the expected enhancement?

Update the code in https://github.com/Qiskit/rustworkx/blob/main/src/link_analysis.rs to use https://github.com/sarah-ek/faer-rs/.

The functions should still rely mostly on the power method to estimate the eigenvector. And they should still use sparse matrices. faer provides a function to multiply a dense vector by a sparse matrix that we should use https://docs.rs/faer/latest/faer/sparse/linalg/matmul/fn.sparse_dense_matmul.html.

The motivation is mostly for consistency with Qiskit, that already uses faer (https://github.com/Qiskit/qiskit/blob/1e8205e43d72cf2a186a8013072aa6b2c5cd1196/crates/accelerate/Cargo.toml#L23). We might need to benchmark the code to check that there is no performance regressions though.

@IvanIsCoding IvanIsCoding added enhancement New feature or request good first issue Good for newcomers labels Jul 11, 2024
@mtreinish
Copy link
Member

FWIW, I don't think consistency with what qiskit is using is enough of a reason to do this. I originally suggested investigating faer to see if we could use it to accelerate the eigendecomposition instead of doing the power iteration method we're using now. I would only think we should do this if there is a performance improvement. Otherwise we can just stick with sprs.

The other place this could be useful is in the eigenvector and katz centrality implementations in: https://github.com/Qiskit/rustworkx/blob/main/rustworkx-core/src/centrality.rs

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request good first issue Good for newcomers
Projects
None yet
Development

No branches or pull requests

2 participants