Sparse Solvers#

enum raft::sparse::solver::LANCZOS_WHICH#

Enumeration specifying which eigenvalues to compute in the Lanczos algorithm.

Values:

enumerator LA#: LA: Largest (algebraic) eigenvalues.

enumerator LM#: LM: Largest (in magnitude) eigenvalues.

enumerator SA#: SA: Smallest (algebraic) eigenvalues.

enumerator SM#: SM: Smallest (in magnitude) eigenvalues.

template<typename IndexTypeT, typename ValueTypeT, typename NNZTypeT> int raft::sparse::solver::lanczos_compute_eigenpairs( raft::resources const &handle, lanczos_solver_config<ValueTypeT> const &config, raft::device_csr_matrix_view<ValueTypeT, IndexTypeT, IndexTypeT, NNZTypeT> 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 eigenpairs using lanczos solver.

Template Parameters:

IndexTypeT – the type of data used for indexing.
ValueTypeT – 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, typename NNZTypeT> int raft::sparse::solver::lanczos_compute_eigenpairs( raft::resources const &handle, lanczos_solver_config<ValueTypeT> const &config, raft::device_coo_matrix_view<ValueTypeT, IndexTypeT, IndexTypeT, NNZTypeT> 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 eigenpairs using lanczos solver.

Template Parameters:

IndexTypeT – the type of data used for indexing.
ValueTypeT – the type of data used for weights, distances.

Parameters:

handle – the raft handle.
config – lanczos config used to set hyperparameters
A – Sparse matrix in COO 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_eigenpairs( 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 eigenpairs using lanczos solver.

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 CSR matrix.
cols – Vector view of the cols of the sparse CSR matrix.
vals – Vector view of the vals of the sparse CSR matrix.
v0 – Optional Initial lanczos vector
eigenvalues – output eigenvalues
eigenvectors – output eigenvectors

Returns:

Zero if successful. Otherwise non-zero.

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>

Configuration parameters for the Lanczos eigensolver.

This structure encapsulates all configuration parameters needed to run the Lanczos algorithm for computing eigenvalues and eigenvectors of large sparse matrices.

Template Parameters:: ValueTypeT – Data type for values (float or double)

Public Members

int n_components#: The number of eigenvalues and eigenvectors to compute.

Note

Must be 1 <= n_components < n, where n is the matrix dimension

int max_iterations#: Maximum number of iterations allowed for the algorithm to converge.

int ncv#: The number of Lanczos vectors to generate.

Note

Must satisfy n_components + 1 < ncv < n, where n is the matrix dimension

ValueTypeT tolerance#: Convergence tolerance for residuals.

Note

Used to determine when to stop iteration based on ||Ax - wx|| < tolerance

LANCZOS_WHICH which#

Specifies which eigenvalues to compute in the Lanczos algorithm.

Sparse Randomized SVD#

template<typename ValueTypeT, typename OperatorT> void sparse_randomized_svd( raft::resources const &handle, sparse_svd_config<ValueTypeT> const &config, OperatorT const &op, raft::device_vector_view<ValueTypeT, uint32_t> singular_values, detail::nondeduced_optional_matrix_view_t<raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major>> U = std::nullopt, detail::nondeduced_optional_matrix_view_t<raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major>> Vt = std::nullopt )#

Compute truncated SVD using randomized algorithm with a generic linear operator.

Implements randomized SVD (Halko et al. 2009) with CholeskyQR2 orthogonalization (Tomás et al. 2024) for efficient GPU execution on sparse matrices.

The operator interface allows implicit linear operators (e.g. mean-centered sparse matrices for PCA) without materializing the dense matrix. OperatorT must expose the minimal interface used by the randomized SVD inner loop:

int rows() const / int cols() const
void apply(handle, X, Y) const computes Y = A @ X
void apply_transpose(handle, X, Z) const computes Z = A^T @ X

where X, Y, Z are raft::device_matrix_view<..., uint32_t, raft::col_major>. This is intentionally a narrow, SVD-specific operator: only the two matrix products above are required, and no other operations (addition, scaling, inverse, eigensolves, etc.) are assumed or supported; it is not a general-purpose linear operator like scipy.sparse.linalg.LinearOperator.

Note

References: [1] Halko, Martinsson, Tropp (2009) “Finding structure with randomness” https://arxiv.org/abs/0909.4061

[2] Tomás, Quintana-Ortí, Anzt (2024) “Fast Truncated SVD of Sparse and Dense Matrices

on Graphics Processors”

https://arxiv.org/abs/2403.06218

Template Parameters:

ValueTypeT – Data type (float or double)
OperatorT – Linear operator type satisfying the interface above

Parameters:

handle – [in] raft resources handle
config – [in] SVD configuration parameters
op – [in] linear operator representing the matrix to decompose
singular_values – [out] output singular values of shape (n_components,) in descending order
U – [out] optional output left singular vectors of shape (m, n_components), col-major. Pass std::nullopt to skip computing U.
Vt – [out] optional output right singular vectors of shape (n_components, n), col-major. Pass std::nullopt to skip computing Vt.

template<typename ValueTypeT, typename NNZTypeT> void sparse_randomized_svd( raft::resources const &handle, sparse_svd_config<ValueTypeT> const &config, raft::device_csr_matrix_view<const ValueTypeT, int, int, NNZTypeT> A, raft::device_vector_view<ValueTypeT, uint32_t> singular_values, detail::nondeduced_optional_matrix_view_t<raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major>> U = std::nullopt, detail::nondeduced_optional_matrix_view_t<raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major>> Vt = std::nullopt )#

Compute truncated SVD of a sparse CSR matrix using randomized algorithm.

Convenience overload that accepts a CSR matrix view directly.

Template Parameters:

ValueTypeT – Data type (float or double)
NNZTypeT – Type for number of non-zeros

Parameters:

handle – [in] raft resources handle
config – [in] SVD configuration parameters
A – [in] input sparse CSR matrix of shape (m, n)
singular_values – [out] output singular values of shape (n_components,) in descending order
U – [out] optional output left singular vectors of shape (m, n_components), col-major. Pass std::nullopt to skip computing U.
Vt – [out] optional output right singular vectors of shape (n_components, n), col-major. Pass std::nullopt to skip computing Vt.

template<typename ValueTypeT> struct sparse_svd_config#

#include <solver_types.hpp>

Configuration parameters for the sparse randomized SVD solver.

Template Parameters:: ValueTypeT – Data type for values (float or double)

Public Members

int n_components = 0#: Number of singular values/vectors to compute. Must be set by the user.

int n_oversamples = 10#: Number of extra random vectors for better approximation. Total subspace dimension is n_components + n_oversamples.

int n_power_iters = 2#: Number of power iteration passes. More iterations improve accuracy for matrices with slowly decaying singular values.

std::optional<uint64_t> seed = std::nullopt#: Random seed for reproducibility.

Sparse Lanczos SVD#

template<typename ValueTypeT, typename OperatorT> void sparse_lanczos_svd( raft::resources const &handle, sparse_lanczos_svd_config<ValueTypeT> const &config, OperatorT const &op, raft::device_vector_view<ValueTypeT, uint32_t> singular_values, detail::nondeduced_optional_matrix_view_t<raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major>> U = std::nullopt, detail::nondeduced_optional_matrix_view_t<raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major>> Vt = std::nullopt, sparse_lanczos_svd_stats *stats = nullptr )#

Compute truncated SVD using Lanczos bidiagonalization with a generic linear operator.

This solver computes the largest singular triplets using implicitly restarted Lanczos bidiagonalization, full reorthogonalization, and final A @ V post-refinement of returned left singular vectors. It is intended as the higher-accuracy sparse SVD path. The operator interface matches sparse_randomized_svd and supports implicit operators such as centered sparse matrices.

By default, the solver uses two-pass classical Gram-Schmidt (CGS2), which is efficient on GPUs. The configuration can request two-pass modified Gram-Schmidt (MGS2) as an alternate path for difficult spectra. If the requested components do not converge within config.max_iterations, this function raises an exception instead of returning partially converged vectors.

OperatorT must expose:

int rows() const / int cols() const
void apply(handle, X, Y) const computes Y = A @ X
void apply_transpose(handle, X, Z) const computes Z = A^T @ X

where X, Y, Z are raft::device_matrix_view<..., uint32_t, raft::col_major>.

Note

This solver intentionally uses 32-bit indexing, matching sparse_randomized_svd: the operator reports its shape as int and all device views use uint32_t extents, so matrix dimensions must fit in a signed 32-bit integer (m, n < 2^31).

Template Parameters:

ValueTypeT – Data type (float or double)
OperatorT – Linear operator type satisfying the interface above

Parameters:

handle – [in] raft resources handle
config – [in] SVD configuration parameters
op – [in] linear operator representing the matrix to decompose
singular_values – [out] output singular values of shape (n_components,) in descending order
U – [out] optional output left singular vectors of shape (m, n_components), col-major. Pass std::nullopt to skip storing U.
Vt – [out] optional output right singular vectors of shape (n_components, n), col-major. Pass std::nullopt to skip storing Vt.
stats – [out] optional host-side restart diagnostics. Pass nullptr (the default) to skip collection; collecting adds no device work or synchronization.

template<typename ValueTypeT, typename NNZTypeT> void sparse_lanczos_svd( raft::resources const &handle, sparse_lanczos_svd_config<ValueTypeT> const &config, raft::device_csr_matrix_view<const ValueTypeT, int, int, NNZTypeT> A, raft::device_vector_view<ValueTypeT, uint32_t> singular_values, detail::nondeduced_optional_matrix_view_t<raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major>> U = std::nullopt, detail::nondeduced_optional_matrix_view_t<raft::device_matrix_view<ValueTypeT, uint32_t, raft::col_major>> Vt = std::nullopt, sparse_lanczos_svd_stats *stats = nullptr )#

Compute truncated SVD of a sparse CSR matrix using Lanczos bidiagonalization.

Convenience overload that accepts a CSR matrix view directly.

Note

Like the generic overload, this API uses 32-bit indexing: the CSR matrix must use int indptr/indices (a cuSPARSE SpMM requirement) and matrix dimensions must fit in a signed 32-bit integer (m, n < 2^31).

Template Parameters:

ValueTypeT – Data type (float or double)
NNZTypeT – Type for number of non-zeros

Parameters:

handle – [in] raft resources handle
config – [in] SVD configuration parameters
A – [in] input sparse CSR matrix of shape (m, n)
singular_values – [out] output singular values of shape (n_components,) in descending order
U – [out] optional output left singular vectors of shape (m, n_components), col-major. Pass std::nullopt to skip storing U.
Vt – [out] optional output right singular vectors of shape (n_components, n), col-major. Pass std::nullopt to skip storing Vt.
stats – [out] optional host-side restart diagnostics. Pass nullptr (the default) to skip collection; collecting adds no device work or synchronization.

template<typename ValueTypeT> struct sparse_lanczos_svd_config#

#include <solver_types.hpp>

Configuration parameters for the sparse Lanczos SVD solver.

Template Parameters:: ValueTypeT – Data type for values (float or double)

Public Members

int n_components = 0#: Number of singular values/vectors to compute. Must be set by the user.

Note

Must satisfy 0 < n_components < min(m, n), where (m, n) is the matrix shape.

int ncv = 0#

Number of Lanczos vectors per restart.

If zero, a matrix-shape dependent default is selected. Larger values can improve convergence margin and orthogonality for clustered spectra, but increase sparse matrix-vector work and memory use.

Note

ValueTypeT tolerance = ValueTypeT(1e-4)#: Convergence tolerance for Lanczos Ritz residual estimates.

int max_iterations = 100#: Maximum number of restart iterations before reporting non-convergence.

std::optional<uint64_t> seed = std::nullopt#: Random seed for reproducibility.

bool use_mgs2_orthogonalization = false#

Use launch-heavy MGS2 instead of the default GPU-efficient CGS2 reorthogonalization.

MGS2 is kept as an alternate path for difficult spectra; CGS2 is the default used in normal GPU workloads.

struct sparse_lanczos_svd_stats#

#include <solver_types.hpp>

Optional per-call diagnostics for the sparse Lanczos SVD solver.

Public Members

int n_restarts = 0#

Number of restarts performed.

A restart is a sweep after which a new starting vector was built and another bidiagonalization followed, i.e. it excludes the final sweep that completes n_components and exits the loop.

int max_locked_per_restart = 0#

Largest number of Ritz pairs locked in a single sweep that was followed by a restart.

int total_iterations = 0#: Number of bidiagonalization sweeps executed, including the final one.

int breakdown_events = 0#: Number of times a candidate Lanczos vector fell below the breakdown threshold and was replaced by a random vector.