Attention

The vector search and clustering algorithms in RAFT are being migrated to a new library dedicated to vector search called cuVS. We will continue to support the vector search algorithms in RAFT during this move, but will no longer update them after the RAPIDS 24.06 (June) release. We plan to complete the migration by RAPIDS 24.10 (October) release and they will be removed from RAFT altogether in the 24.12 (December) release.

Sparse Solvers#

template<typename IndexTypeT, typename ValueTypeT>
int raft::sparse::solver::lanczos_compute_smallest_eigenvectors(raft::resources const &handle, lanczos_solver_config<ValueTypeT> const &config, raft::device_csr_matrix_view<ValueTypeT, IndexTypeT, IndexTypeT, IndexTypeT> A, std::optional<raft::device_vector_view<ValueTypeT, uint32_t, raft::row_major>> v0, raft::device_vector_view<ValueTypeT, uint32_t, raft::col_major> eigenvalues, raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major> eigenvectors)#

Find the smallest eigenpairs using lanczos solver.

Todo:

Add largest eigenvalues computation (issue #2483)

Template Parameters:

  • index_type_t – the type of data used for indexing.

  • value_type_t – the type of data used for weights, distances.

Parameters:

  • handle – the raft handle.

  • config – lanczos config used to set hyperparameters

  • A – Sparse matrix in CSR format.

  • v0 – Optional Initial lanczos vector

  • eigenvalues – output eigenvalues

  • eigenvectors – output eigenvectors

Returns:

Zero if successful. Otherwise non-zero.

template<typename IndexTypeT, typename ValueTypeT>
int raft::sparse::solver::lanczos_compute_smallest_eigenvectors(raft::resources const &handle, lanczos_solver_config<ValueTypeT> const &config, raft::device_vector_view<IndexTypeT, uint32_t, raft::row_major> rows, raft::device_vector_view<IndexTypeT, uint32_t, raft::row_major> cols, raft::device_vector_view<ValueTypeT, uint32_t, raft::row_major> vals, std::optional<raft::device_vector_view<ValueTypeT, uint32_t, raft::row_major>> v0, raft::device_vector_view<ValueTypeT, uint32_t, raft::col_major> eigenvalues, raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major> eigenvectors)#

Find the smallest eigenpairs using lanczos solver.

Todo:

Add largest eigenvalues computation (issue #2483)

Template Parameters:

  • index_type_t – the type of data used for indexing.

  • value_type_t – the type of data used for weights, distances.

Parameters:

  • handle – the raft handle.

  • config – lanczos config used to set hyperparameters

  • rows – Vector view of the rows of the sparse matrix.

  • cols – Vector view of the cols of the sparse matrix.

  • vals – Vector view of the vals of the sparse matrix.

  • v0 – Optional Initial lanczos vector

  • eigenvalues – output eigenvalues

  • eigenvectors – output eigenvectors

Returns:

Zero if successful. Otherwise non-zero.

template<typename index_type_t, typename value_type_t> int raft::sparse::solver::computeSmallestEigenvectors (raft::resources const &handle, raft::spectral::matrix::sparse_matrix_t< index_type_t, value_type_t > const &A, index_type_t nEigVecs, index_type_t maxIter, index_type_t restartIter, value_type_t tol, bool reorthogonalize, index_type_t &iter, value_type_t *__restrict__ eigVals_dev, value_type_t *__restrict__ eigVecs_dev, unsigned long long seed=1234567)

Compute smallest eigenvectors of symmetric matrix Computes eigenvalues and eigenvectors that are least positive. If matrix is positive definite or positive semidefinite, the computed eigenvalues are smallest in magnitude. The largest eigenvalue is estimated by performing several Lanczos iterations. An implicitly restarted Lanczos method is then applied to A+s*I, where s is negative the largest eigenvalue.

Template Parameters:

  • index_type_t – the type of data used for indexing.

  • value_type_t – the type of data used for weights, distances.

Parameters:

  • handle – the raft handle.

  • A – Matrix.

  • nEigVecs – Number of eigenvectors to compute.

  • maxIter – Maximum number of Lanczos steps. Does not include Lanczos steps used to estimate largest eigenvalue.

  • restartIter – Maximum size of Lanczos system before performing an implicit restart. Should be at least 4.

  • tol – Convergence tolerance. Lanczos iteration will terminate when the residual norm is less than tol*theta, where theta is an estimate for the smallest unwanted eigenvalue (i.e. the (nEigVecs+1)th smallest eigenvalue).

  • reorthogonalize – Whether to reorthogonalize Lanczos vectors.

  • iter – On exit, pointer to total number of Lanczos iterations performed. Does not include Lanczos steps used to estimate largest eigenvalue.

  • eigVals_dev – (Output, device memory, nEigVecs entries) Smallest eigenvalues of matrix.

  • eigVecs_dev – (Output, device memory, n*nEigVecs entries) Eigenvectors corresponding to smallest eigenvalues of matrix. Vectors are stored as columns of a column-major matrix with dimensions n x nEigVecs.

  • seed – random seed.

Returns:

error flag.

template<typename index_type_t, typename value_type_t> int raft::sparse::solver::computeLargestEigenvectors (raft::resources const &handle, raft::spectral::matrix::sparse_matrix_t< index_type_t, value_type_t > const &A, index_type_t nEigVecs, index_type_t maxIter, index_type_t restartIter, value_type_t tol, bool reorthogonalize, index_type_t &iter, value_type_t *__restrict__ eigVals_dev, value_type_t *__restrict__ eigVecs_dev, unsigned long long seed=123456)

Compute largest eigenvectors of symmetric matrix Computes eigenvalues and eigenvectors that are least positive. If matrix is positive definite or positive semidefinite, the computed eigenvalues are largest in magnitude. The largest eigenvalue is estimated by performing several Lanczos iterations. An implicitly restarted Lanczos method is then applied to A+s*I, where s is negative the largest eigenvalue.

Template Parameters:

  • index_type_t – the type of data used for indexing.

  • value_type_t – the type of data used for weights, distances.

Parameters:

  • handle – the raft handle.

  • A – Matrix.

  • nEigVecs – Number of eigenvectors to compute.

  • maxIter – Maximum number of Lanczos steps. Does not include Lanczos steps used to estimate largest eigenvalue.

  • restartIter – Maximum size of Lanczos system before performing an implicit restart. Should be at least 4.

  • tol – Convergence tolerance. Lanczos iteration will terminate when the residual norm is less than tol*theta, where theta is an estimate for the largest unwanted eigenvalue (i.e. the (nEigVecs+1)th largest eigenvalue).

  • reorthogonalize – Whether to reorthogonalize Lanczos vectors.

  • iter – On exit, pointer to total number of Lanczos iterations performed. Does not include Lanczos steps used to estimate largest eigenvalue.

  • eigVals_dev – (Output, device memory, nEigVecs entries) Largest eigenvalues of matrix.

  • eigVecs_dev – (Output, device memory, n*nEigVecs entries) Eigenvectors corresponding to largest eigenvalues of matrix. Vectors are stored as columns of a column-major matrix with dimensions n x nEigVecs.

  • seed – random seed.

Returns:

error flag.

template<typename vertex_t, typename edge_t, typename weight_t, typename alteration_t = weight_t>
Graph_COO<vertex_t, edge_t, weight_t> raft::sparse::solver::mst(raft::resources const &handle, edge_t const *offsets, vertex_t const *indices, weight_t const *weights, vertex_t const v, edge_t const e, vertex_t *color, cudaStream_t stream, bool symmetrize_output = true, bool initialize_colors = true, int iterations = 0)

Compute the minimum spanning tree (MST) or minimum spanning forest (MSF) depending on the connected components of the given graph.

Template Parameters:

  • vertex_t – integral type for precision of vertex indexing

  • edge_t – integral type for precision of edge indexing

  • weight_t – type of weights array

  • alteration_t – type to use for random alteration

Parameters:

  • handle –

  • offsets – csr inptr array of row offsets (size v+1)

  • indices – csr array of column indices (size e)

  • weights – csr array of weights (size e)

  • v – number of vertices in graph

  • e – number of edges in graph

  • color – array to store resulting colors for MSF

  • stream – cuda stream for ordering operations

  • symmetrize_output – should the resulting output edge list should be symmetrized?

  • initialize_colors – should the colors array be initialized inside the MST?

  • iterations – maximum number of iterations to perform

Returns:

a list of edges containing the mst (or a subset of the edges guaranteed to be in the mst when an msf is encountered)

template<typename vertex_t, typename edge_t, typename weight_t>
struct Graph_COO#
template<typename ValueTypeT>
struct lanczos_solver_config#
#include <lanczos_types.hpp>

Public Members

int n_components#

The number of eigenvalues and eigenvectors to compute. Must be 1 <= k < n.

int max_iterations#

Maximum number of iteration.

int ncv#

The number of Lanczos vectors generated. Must be k + 1 < ncv < n.

ValueTypeT tolerance#

Tolerance for residuals ||Ax - wx||

uint64_t seed#

random seed

template<typename vertex_t, typename edge_t, typename weight_t, typename alteration_t>
class MST_solver#