Module linalg

Expand description

Linear algebra: sparse matrices, eigensolvers (ARPACK, LAPACK), BLAS helpers and spectral embeddings of graphs.

This module covers six igraph C headers:

C header	Rust	What it offers
`igraph_sparsemat.h`	`SparseMat`, `SparseLu`, `SparseQr`, `SparseMatIter`	Owned sparse matrices (CXSparse), triplet and column-compressed formats, arithmetic, triangular/LU/QR/Cholesky solvers, ARPACK on sparse matrices
`igraph_arpack.h`	`arpack_rssolve`, `arpack_rnsolve`, `ArpackOptions`, `ArpackStorage`	Matrix-free eigensolvers driven by a Rust closure computing `y = A x`
`igraph_eigen.h`	`eigen_matrix_symmetric`, `eigen_matrix`, `Graph::eigen_adjacency`	A unified front-end choosing between LAPACK and ARPACK
`igraph_lapack.h`	`lapack_dgesv`, `lapack_dgetrf`, `lapack_dgetrs`, `lapack_dsyevr`, `lapack_dgeev`, `lapack_dgeevx`, `lapack_dgehrd`	Dense linear systems and eigenproblems
`igraph_blas.h`	`blas_dgemv`, `blas_dgemv_array`, `blas_dgemm`, `blas_ddot`, `blas_dnrm2`	Dense matrix products, dot products and norms
`igraph_embedding.h`	`Graph::adjacency_spectral_embedding`, `Graph::laplacian_spectral_embedding`, `dim_select`	Spectral embeddings of graphs and dimensionality selection

Dense matrices are the crate’s Matrix (column-major, like igraph and LAPACK); vectors are plain Rust slices and Vecs. Complex numbers are Complex (igraph’s igraph_complex_t, with re and im accessors).

§Safety net around the C library

The C routines wrapped here trust their callers a lot: a wrong vector length reads out of bounds, and an invalid argument handed to the bundled LAPACK or BLAS makes it terminate the process. The wrappers therefore validate every dimension, index and range on the Rust side and report problems as ErrorKind::InvalidValue errors; a few igraph quirks (present in both igraph 1.0.0 and 1.0.1: the linear algebra sources did not change in 1.0.1) are worked around and documented on the affected functions (e.g. SparseMat::transpose of non-square triplet matrices, SparseMat::max, blas_dgemm with beta != 0, 2 × 2 problems in arpack_rssolve). One cannot be worked around: the last ARPACK error is a process-wide C variable, so arpack_last_error is unsafe; use the thread-safe ArpackError::from_error instead.

igraph’s ARPACK is not re-entrant (its iteration state lives in thread-local statics): every ARPACK-based function of the crate (those of this module, and eigenvector centrality, hub and authority scores, eigenvector centralization, PageRank with the ARPACK algorithm and leading eigenvector communities) refuses to run nested inside another ARPACK run on the same thread (from its matrix-vector closure, or from a progress or interruption handler called by it), with an ErrorKind::Failure error (see arpack_rssolve). Also note that ARPACK starts from A v0, not from the start vector v0: null vectors of singular operators can be missed, shift the operator instead (see arpack_rssolve).

igraph_arpack_options_get_default is not wrapped: it hands out a mutable pointer to igraph’s shared default options; use ArpackOptions::default() (igraph_arpack_options_init) instead.

Need	Where
Adjacency matrix of a graph, dense or sparse	`Graph::get_adjacency`, `Graph::get_adjacency_sparse` (conversion)
Laplacian matrix of a graph, dense or as triplets	`Graph::get_laplacian`, `Graph::get_laplacian_sparse` (structural)
Stochastic (random-walk) matrix	`Graph::get_stochastic`, `Graph::get_stochastic_sparse` (conversion)
A graph from a (sparse) adjacency matrix	`Graph::adjacency`, `Graph::sparse_adjacency`, `Graph::sparse_weighted_adjacency` (constructors)
Spectral centralities (ARPACK/PRPACK inside)	`Graph::eigenvector_centrality`, `Graph::hub_and_authority_scores`, `Graph::pagerank` (centrality)
Spectral community detection	`Graph::community_leading_eigenvector` (community)
Spectral layouts	`Graph::layout_mds` (layout)
Seeding the random start vectors of ARPACK	`rng::seed` (per thread)

§Example: the spectrum of a path graph

The Laplacian of the path on n vertices has eigenvalues 2 - 2 cos(pi k / n), k = 0, ..., n - 1. Here we take it from the structural module as sparse triplets, load it into a SparseMat, compute its two largest eigenvalues with ARPACK and check the smallest one with a dense LAPACK solver.

use igraph::linalg::*;
use igraph::prelude::*;
use igraph::structural::LaplacianNormalization;
use std::f64::consts::PI;

let n = 10;
let path = Graph::ring(n, false, false, false).unwrap();
let triplets: Vec<(usize, usize, f64)> = path
    .get_laplacian_sparse(NeighborMode::All, LaplacianNormalization::Unnormalized, None)
    .unwrap()
    .into_iter()
    .map(|(i, j, x)| (i as usize, j as usize, x))
    .collect();
let lap = SparseMat::from_triplets(n, n, &triplets).unwrap().compress().unwrap();
assert!(lap.is_symmetric().unwrap());

// ARPACK, largest algebraic eigenvalues (the random start vector comes
// from this thread's igraph RNG: seed it for reproducible iterations).
rng::seed(42).unwrap();
let opts = ArpackOptions::default().with_nev(2).with_which(ArpackWhich::LargestAlgebraic);
let top = lap.arpack_rssolve(&opts, SparseSolveMethod::Lu).unwrap();
for (k, value) in top.values.iter().enumerate() {
    let expected = 2.0 - 2.0 * (PI * (n - 1 - k) as f64 / n as f64).cos();
    assert!((value - expected).abs() < 1e-8);
}

// LAPACK on the dense copy: the smallest eigenvalue is 0.
let dense = lap.to_dense().unwrap();
let low = lapack_dsyevr(&dense, &SymmetricRange::Select(0..1), 1e-12).unwrap();
assert!(low.values[0].abs() < 1e-10);

Structs§

ArpackInfo: Statistics reported by ARPACK after a successful run (the output fields of igraph_arpack_options_t).
ArpackNonSymmetricResult: Result of the non-symmetric ARPACK solvers.
ArpackOptions: Options of the ARPACK eigensolvers (a safe subset of igraph_arpack_options_t).
ArpackStorage: Preallocated working memory for repeated ARPACK runs (igraph_arpack_storage_t), freed on drop (igraph_arpack_storage_destroy).
ArpackSymmetricResult: Result of the symmetric ARPACK solvers.
ComplexEigen: Eigenvalues and eigenvectors of a general real matrix.
DgeevResult: Eigenvalues and eigenvectors of a general real matrix computed by lapack_dgeev, in LAPACK’s packed real format.
DgeevxResult: Output of lapack_dgeevx.
DgesvResult: The solution of a linear system computed by lapack_dgesv.
DsyevrResult: Eigenvalues and eigenvectors computed by lapack_dsyevr.
LuFactors: An LU factorization A = P L U computed by lapack_dgetrf.
SparseElements: The elements of a sparse matrix as returned by SparseMat::getelements (the raw CXSparse arrays).
SparseLu: A sparse LU factorization, see SparseMat::lu. It owns igraph’s symbolic and numeric decompositions and frees them on drop (igraph_sparsemat_symbolic_destroy, igraph_sparsemat_numeric_destroy).
SparseMatIter: Iterator over the stored entries of a SparseMat, see SparseMat::iter.
SparseQr: A sparse QR factorization of a square matrix, see SparseMat::qr.
SpectralEmbedding: A spectral embedding of the vertices of a graph.
SymmetricEigen: Eigenvalues and eigenvectors of a real symmetric matrix.

Enums§

ArpackError: Error conditions reported by ARPACK (igraph_arpack_error_t), see ArpackError::from_error and arpack_error_to_string.
ArpackMode: The kind of eigenproblem ARPACK solves (the mode field of igraph_arpack_options_t).
ArpackWhich: Which eigenvalues ARPACK should compute (the which field of igraph_arpack_options_t).
DgeevxBalance: Balancing performed by lapack_dgeevx (igraph_lapack_dgeevx_balance_t).
EigenAlgorithm: Which numerical library eigen_matrix_symmetric, eigen_matrix and Graph::eigen_adjacency use (igraph_eigen_algorithm_t).
EigenWhich: Which eigenvalues to compute (igraph_eigen_which_t).
EmbeddingWhich: Which eigenvalues (singular values for directed graphs) the spectral embeddings use (the admissible subset of igraph_eigen_which_position_t).
LaplacianEmbeddingType: The Laplacian used by Graph::laplacian_spectral_embedding (igraph_laplacian_spectral_embedding_type_t). D is the degree (strength) matrix, A the adjacency matrix.
SparseMatType: Storage format of a SparseMat (igraph_sparsemat_type_t).
SparseOrdering: Fill-reducing ordering used by the sparse factorizations (SparseMat::cholsol, SparseMat::lusol, SparseMat::lu, SparseMat::qr); the integer order argument of the C functions.
SparseSolveMethod: How the linear systems of the shift-and-invert mode of SparseMat::arpack_rssolve are solved (igraph_sparsemat_solve_t).
SymmetricRange: Which eigenvalues lapack_dsyevr computes (igraph_lapack_dsyev_which_t plus its parameters).

Functions§

arpack_error_to_string: Human readable description of an ARPACK error code (igraph_arpack_error_to_string).
arpack_last_error^⚠: The error code of the last ARPACK failure in the process (igraph_arpack_get_last_error).
arpack_rnsolve: Eigenvalues and eigenvectors of a general (non-symmetric) linear operator given as a Rust closure, with ARPACK’s implicitly restarted Arnoldi method (igraph_arpack_rnsolve).
arpack_rssolve: Eigenvalues and eigenvectors of a symmetric linear operator given as a Rust closure, with ARPACK’s implicitly restarted Lanczos method (igraph_arpack_rssolve).
arpack_unpack_complex: Rewrites the packed output of the non-symmetric ARPACK solver into a regular form (igraph_arpack_unpack_complex).
blas_ddot: Dot product of two vectors of the same length (igraph_blas_ddot).
blas_dgemm: Matrix-matrix product alpha * op(A) * op(B) + beta * C, where op(X) is X or its transpose (igraph_blas_dgemm). c may be None when beta is zero (or to mean a zero matrix).
blas_dgemv: Matrix-vector product alpha * op(A) * x + beta * y, where op(A) is A or its transpose (igraph_blas_dgemv); the result is returned as a new vector. When beta is zero, y only provides the length.
blas_dgemv_array: In-place matrix-vector product y <- alpha * op(A) * x + beta * y on plain slices (igraph_blas_dgemv_array).
blas_dnrm2: Euclidean norm of a vector (igraph_blas_dnrm2), computed without undue overflow or underflow.
dense_multiply: The dense product a * b of a dense matrix with a sparse one (igraph_sparsemat_dense_multiply).
dim_select: Dimensionality selection by profile likelihood (igraph_dim_select).
eigen_matrix: Selected eigenvalues and eigenvectors of a general real dense matrix (igraph_eigen_matrix); only EigenAlgorithm::Lapack is implemented by igraph 1.0.0 and 1.0.1.
eigen_matrix_symmetric: Selected eigenvalues and eigenvectors of a real symmetric dense matrix (igraph_eigen_matrix_symmetric), with LAPACK or ARPACK.
eigen_symmetric_fn: Selected eigenvalues and eigenvectors of a real symmetric operator given by a matrix-vector product closure (igraph_eigen_matrix_symmetric with a callback), see arpack_rssolve for the closure contract. With LAPACK the matrix is first formed by applying the closure to the unit vectors.
lapack_dgeev: Eigenvalues and, optionally, left and/or right eigenvectors of a general real square matrix (igraph_lapack_dgeev). The eigenvectors are normalized to unit Euclidean norm with largest component real.
lapack_dgeevx: Eigenvalues and left and right eigenvectors of a general real matrix, “expert” version (igraph_lapack_dgeevx): it also balances the matrix (see DgeevxBalance) and computes reciprocal condition numbers of the eigenvalues.
lapack_dgehrd: Reduces a general square matrix to upper Hessenberg form by an orthogonal similarity transformation (igraph_lapack_dgehrd): the result H = Q' A Q has zeros below the first subdiagonal and the same eigenvalues as A.
lapack_dgesv: Solves the linear system A X = B for a square A and one or more right hand sides (the columns of B), by LU decomposition with partial pivoting (igraph_lapack_dgesv).
lapack_dgetrf: LU factorization with partial pivoting of a general m × n matrix, A = P L U (igraph_lapack_dgetrf), where L is lower triangular (trapezoidal if m > n) with unit diagonal and U is upper triangular (trapezoidal if m < n).
lapack_dgetrs: Solves A X = B or A' X = B (transpose) using the LU factors of a square A computed by lapack_dgetrf (igraph_lapack_dgetrs). No check is made for singularity.
lapack_dsyevr: Selected eigenvalues and eigenvectors of a real symmetric matrix, with LAPACK’s relatively robust representations algorithm (igraph_lapack_dsyevr). Only the upper triangle of a is used.
solve: Solves A x = b for a single right hand side (via lapack_dgesv).

Type Aliases§

Complex: A complex number (igraph_complex_t), with re and im accessors and Complex::new.
SparseMat: An owned sparse matrix of reals (igraph_sparsemat_t), backed by the CXSparse library bundled with igraph.

Module linalg

Module linalg Copy item path

§Safety net around the C library

§Related functionality in other modules

§Example: the spectrum of a path graph

Structs§

Enums§

Functions§

Type Aliases§

Module linalg