nalgebra-sparse 0.2.0

Sparse matrix computation based on nalgebra.
Documentation

Sparse matrices and algorithms for nalgebra.

This crate extends nalgebra with sparse matrix formats and operations on sparse matrices.

Goals

The long-term goals for this crate are listed below.

  • Provide proven sparse matrix formats in an easy-to-use and idiomatic Rust API that naturally integrates with nalgebra.
  • Provide additional expert-level APIs for fine-grained control over operations.
  • Integrate well with external sparse matrix libraries.
  • Provide native Rust high-performance routines, including parallel matrix operations.

Highlighted current features

  • CSR, CSC and COO formats, and conversions between them.
  • Common arithmetic operations are implemented. See the [ops] module.
  • Sparsity patterns in CSR and CSC matrices are explicitly represented by the SparsityPattern type, which encodes the invariants of the associated index data structures.
  • proptest strategies for sparse matrices when the feature proptest-support is enabled.
  • matrixcompare support for effortless (approximate) comparison of matrices in test code (requires the compare feature).

Current state

The library is in an early, but usable state. The API has been designed to be extensible, but breaking changes will be necessary to implement several planned features. While it is backed by an extensive test suite, it has yet to be thoroughly battle-tested in real applications. Moreover, the focus so far has been on correctness and API design, with little focus on performance. Future improvements will include incremental performance enhancements.

Current limitations:

  • Limited or no availability of sparse system solvers.
  • Limited support for complex numbers. Currently only arithmetic operations that do not rely on particular properties of complex numbers, such as e.g. conjugation, are supported.
  • No integration with external libraries.

Usage

Add the following to your Cargo.toml file:

[dependencies]
nalgebra_sparse = "0.1"

Supported matrix formats

Format Notes
COO Well-suited for matrix construction. Ill-suited for algebraic operations.
CSR Immutable sparsity pattern, suitable for algebraic operations. Fast row access.
CSC Immutable sparsity pattern, suitable for algebraic operations. Fast column access.

What format is best to use depends on the application. The most common use case for sparse matrices in science is the solution of sparse linear systems. Here we can differentiate between two common cases:

  • Direct solvers. Typically, direct solvers take their input in CSR or CSC format.
  • Iterative solvers. Many iterative solvers require only matrix-vector products, for which the CSR or CSC formats are suitable.

The COO format is primarily intended for matrix construction. A common pattern is to use COO for construction, before converting to CSR or CSC for use in a direct solver or for computing matrix-vector products in an iterative solver. Some high-performance applications might also directly manipulate the CSR and/or CSC formats.

Example: COO -> CSR -> matrix-vector product

use nalgebra_sparse::{coo::CooMatrix, csr::CsrMatrix};
use nalgebra::{DMatrix, DVector};
use matrixcompare::assert_matrix_eq;

// The dense representation of the matrix
let dense = DMatrix::from_row_slice(3, 3,
&[1.0, 0.0, 3.0,
2.0, 0.0, 1.3,
0.0, 0.0, 4.1]);

// Build the equivalent COO representation. We only add the non-zero values
let mut coo = CooMatrix::new(3, 3);
// We can add elements in any order. For clarity, we do so in row-major order here.
coo.push(0, 0, 1.0);
coo.push(0, 2, 3.0);
coo.push(1, 0, 2.0);
coo.push(1, 2, 1.3);
coo.push(2, 2, 4.1);

// The simplest way to construct a CSR matrix is to first construct a COO matrix, and
// then convert it to CSR. The `From` trait is implemented for conversions between different
// sparse matrix types.
// Alternatively, we can construct a matrix directly from the CSR data.
// See the docs for CsrMatrix for how to do that.
let csr = CsrMatrix::from(&coo);

// Let's check that the CSR matrix and the dense matrix represent the same matrix.
// We can use macros from the `matrixcompare` crate to easily do this, despite the fact that
// we're comparing across two different matrix formats. Note that these macros are only really
// appropriate for writing tests, however.
assert_matrix_eq!(csr, dense);

let x = DVector::from_column_slice(&[1.3, -4.0, 3.5]);

// Compute the matrix-vector product y = A * x. We don't need to specify the type here,
// but let's just do it to make sure we get what we expect
let y: DVector<_> = &csr * &x;

// Verify the result with a small element-wise absolute tolerance
let y_expected = DVector::from_column_slice(&[11.8, 7.15, 14.35]);
assert_matrix_eq!(y, y_expected, comp = abs, tol = 1e-9);

// The above expression is simple, and gives easy to read code, but if we're doing this in a
// loop, we'll have to keep allocating new vectors. If we determine that this is a bottleneck,
// then we can resort to the lower level APIs for more control over the operations
{
use nalgebra_sparse::ops::{Op, serial::spmm_csr_dense};
let mut y = y;
// Compute y <- 0.0 * y + 1.0 * csr * dense. We store the result directly in `y`, without
// any intermediate allocations
spmm_csr_dense(0.0, &mut y, 1.0, Op::NoOp(&csr), Op::NoOp(&x));
assert_matrix_eq!(y, y_expected, comp = abs, tol = 1e-9);
}