sanic: Solving Ax = b Nimbly in C++

Nikolas KuschnigOpenalex Unknown 2020 · DOI · OpenAlex

Abstract

Routines for solving large systems of linear equations and eigenproblems in R. Direct and iterative solvers from the Eigen C++ library are made available. Solvers include Cholesky, LU, QR, and Krylov subspace methods (Conjugate Gradient, BiCGSTAB). Dense and sparse problems are supported.

Introduction

In scientific computing and data science, the primary bottleneck is often solving massive systems of linear equations ($Ax = b$) or finding eigenvalues for large matrices. While R provides built-in functions like solve() or eigen(), these can be suboptimal for very large datasets or specialized matrix structures, such as highly sparse matrices.

The sanic package addresses this performance gap by providing a high-performance R interface to the Eigen C++ library. By bridging R with optimized C++ routines via Rcpp and RcppEigen, it offers researchers a suite of fast direct and iterative solvers that handle both dense and sparse matrices with minimal overhead.

Methodology

The package's methodology is divided into three core functional areas:

  1. Direct Solvers: Wrappers for Cholesky (LLT/LDLT), LU (Partial/Full pivoting), and QR decompositions. These are exact solvers (up to machine precision) that include options for various pivoting and ordering schemes to maintain numerical stability.
  2. Iterative Solvers: For systems too large for direct decomposition, sanic offers Krylov subspace methods. This includes Conjugate Gradient (CG) for symmetric positive definite matrices, BiCGSTAB for general square matrices, and LSCG for rectangular least-squares problems.
  3. Spectral Decomposition: The package implements Arnoldi iteration and Lanczos methods to iteratively approximate eigenvalues and eigenvectors, as well as Singular Value Decomposition (SVD) using Divide and Conquer or Jacobi strategies.

Implementation and Iterative Control

A significant advantage of sanic is its exposure of low-level parameters that allow users to tune solver performance. For iterative methods, users can specify initial guesses (x0), maximum iterations, and preconditioning schemes, which are essential for ensuring convergence in complex models.

Parameters for iterative solvers in sanic, including control over iterations, tolerance, and preconditioning.

For direct solvers, the package provides flexibility in selecting pivoting and ordering schemes (such as AMD or COLAMD). This level of control is crucial for maintaining efficiency when dealing with sparse matrices, where the order of operations significantly impacts memory usage and speed.

Parameters for direct solvers, highlighting options for pivoting and ordering schemes.

Key Insights and Features

  • The "Smart" Solver: The solve2() function acts as a high-level dispatcher that automatically selects a direct method based on input matrix format, prioritizing speed for general use.
  • Sparsity as a First-Class Citizen: Designed to work seamlessly with the Matrix package's dgCMatrix class, the sparsify() function ensures the underlying C++ code utilizes sparse-optimized memory structures.
  • Reorthogonalization: In its spectral implementations, the package includes an orthogonalise flag, allowing users to choose full reorthogonalization to prevent the loss of orthogonality in basis vectors—a common pitfall in iterative spectral methods.

Conclusion

The sanic package provides a unified, flexible interface that achieves near-native performance for large-scale numerical problems. While users must still be mindful of numerical stability in ill-conditioned systems, the package significantly expands the capabilities of the R environment for high-performance linear algebra.

Summary updated

Abstract

Routines for solving large systems of linear equations and eigenproblems in R. Direct and iterative solvers from the Eigen C++ library are made available. Solvers include Cholesky, LU, QR, and Krylov subspace methods (Conjugate Gradient, BiCGSTAB). Dense and sparse problems are supported.
BibTeX
@inproceedings{kuschnig2020sanic,
  author = {Nikolas Kuschnig},
  title = {{sanic: Solving Ax = b Nimbly in C++}},
  booktitle = {Openalex Unknown},
  year = {2020},
  doi = {10.32614/cran.package.sanic},
}
Figure