Raku package with sparse matrix algebra functions implemented in C.

The package is a "standalone" implementation of sparse matrix functionalities using Compressed Sparse Row (CSR) format. The intent, though, is to use the class Math::SparseMatrix::Native::CSRStruct provided by this package in the general package "Math::SparseMatrix", [AAp1]. (See the section "Design" below.)

The core algorithms of the package follow the FORTRAN implementations given in the book "Sparse Matrix Technology" by Pissanetzky, [SP1].

This package should be compared -- and likely replaced -- with Raku package(s) interfacing sparse matrix algebra libraries, like, "SuiteSparse". (When/if such Raku packages are implemented.)

Remark: This package uses a C implementation based on standard C libraries ("math", "stdio", "stdlib", "string".) Hence, it should be cross platform.

Remark: Currently, on macOS, Apple's Accelerate library is not used. There are several reasons for this: (i) lack of appropriate documentation to sparse linear algebra in C, (i) using dense matrices for sparse matrix computations with its documented, older LAPACK interface libraries.

Make two random -- relatively large -- sparse matrices:

use Math::SparseMatrix::Native; use Math::SparseMatrix::Native::Utilities; my $nrow = 1000; my $ncol = 10_000; my $density = 0.005; my $nnz = ($nrow * $ncol * $density).Int; my $seed = 3432; my $matrix1 = Math::SparseMatrix::Native::CSRStruct.new.random(:$nrow, :$ncol, :$nnz, :$seed); my $matrix2 = Math::SparseMatrix::Native::CSRStruct.new.random(nrow => $ncol, ncol => $nrow, :$nnz, :$seed); say (:$matrix1); say (:$matrix2);

# matrix1 => Math::SparseMatrix::Native::CSRStruct(:specified-elements(50000), :dimensions((1000, 10000)), :density(0.005)) # matrix2 => Math::SparseMatrix::Native::CSRStruct(:specified-elements(50000), :dimensions((10000, 1000)), :density(0.005)) 

Remark: Compare the dimensions, densities, and the number of "specified elements" in the gists.

Here are 100 dot-products of those matrices (with timings):

my $tstart=now; my $n = 100; for ^$n { $matrix1.dot($matrix2) } my $tend=now; say "Total time : {$tend - $tstart}"; say "Mean time : {($tend - $tstart)/$n}"

# Total time : 0.187534002 # Mean time : 0.00187534002 

The primary motivation for implementing this package is the need to have fast sparse matrix computations.

• The pure-Raku implemented sparse matrix algorithms in "Math::SparseMatrix", [AAp1], are too slow.

• Same algorithms implemented in C (in this package) are ≈100 times faster.

The NativeCall class Math::SparseMatrix::Native::CSRStruct has Compressed Sparse Row (CSR) format sparse matrix operations. The Adapter pattern is used to include Math::SparseMatrix::Native::CSRStruct into the Math::SparseMatrix hierarchy:

classDiagram class Abstract["Math::SparseMatrix::Abstract"] { <<abstract>> +value-at() +row-at() +column-at() +row-slice() +AT-POS() +print() +transpose() +add() +multiply() +dot() } class CSRStruct { <<C struct>> } class NativeCSR["Math::SparseMatrix::CSR::Native"] { $row_ptr $col_index @values nrow ncol implicit_value } class NativeAdapater["Math::SparseMatrix::NativeAdapter"] { +row-ptr +col-index +values +nrow +ncol +implicit-value } class SparseMatrix["Math::SparseMatrix"] { Abstract core-matrix +AT-POS() +print() +transpose() +add() +multiply() +dot() } NativeAdapater --> Abstract : implements SparseMatrix --> Abstract : Hides actual component class SparseMatrix *--> Abstract NativeAdapater *--> NativeCSR NativeCSR -- CSRStruct : reprents 

In order to install within a local clone of the repository:

• Go to repository's folder
• Remove the directory "./resources/libraries"
• Remove the file "./src/Makefile"
• Use zef install . --force-install

The main goal of this package is to be used by "Math::SparseMatrix". In order to verify that the class of Math::SparseMatrix uses Math::SparseMatrix::Native run the tests in the directory of "./xt" of the "Math::SparseMatrix" (repository) folder.

• DONE Core functionalities
  • DONE C-struct representation: data and methods
  • DONE transpose
  • DONE dot-pattern
  • DONE dot matrix x dense vector
  • DONE dot (and dot-numeric) matrix x matrix
  • DONE add with a scalar
  • DONE add with another matrix
  • DONE multiply with a scalar
  • DONE multiply with another matrix
  • DONE Info methods
  • DONE Access functions
  • DONE Values operations unitize, clip, round.
• DONE Refactoring
  • Consistent use of unsigned int or int for row_ptr and col_index.
• DONE Adaptation to "Math::SparseMatrix"
  • This package was made in order to have faster computation with "Math::SparseMatrix", [AAp1].
  • But it can be self-contained and independent from "Math::SparseMatrix".
  • Hence, we make an adapter class:
    • See Math::SparseMatrix::NativeAdapter in "Math::SparseMatrix".
• DONE Unit tests
  • DONE Creation (and destruction)
  • DONE Access
  • DONE Element-wise operations
  • DONE Dot product
  • DONE Values operations unitize, clip, round.

[SP1] Sergio Pissanetzky, Sparse Matrix Technology, Academic Pr (January 1, 1984), ISBN-10: 0125575807, ISBN-13: 978-0125575805.

[AAp1] Anton Antonov, Math::SparseMatrix Raku package, (2024), GitHub/antononcube.