Math::SparseMatrix::Native

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.

Usage examples

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);

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}"

Design

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:

Development notes

Local installation

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

Connection with "Math::SparseMatrix"

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.

TODO

• 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.

• TODO Additional functionalities

  • DONE Singular Value Decomposition (SVD) svd

  • TODO (Sparse) linear system of equations solving

    • This is a large topic. Hence it will require using multiple C files.

• 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.

References

Books

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

Packages

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