Rand Stats

Math::SparseMatrix

zef:antononcube

Math::SparseMatrix

Actions Status Actions Status Actions Status

Raku package for sparse matrix algorithms:


Motivation

Sparse Matrix Algebra (SMA) is a "must have" for many computational workflows. Here is a (non-exhaustive) list given in the order of my preferences:


Usage examples

Here is a simple sparse matrix in Compressed Sparse Row (CSR) format:

use Math::SparseMatrix;
use Math::SparseMatrix::Utilities;

my $nrow = 5;
my $ncol = 8;
my $density = 0.2;
my $tol = 0.01;
my $type = 'CSR';

my $matrix1 = generate-random-sparse-matrix($nrow, $ncol, :$density, :$tol, :$type):!decorated;
say $matrix1;
# Math::SparseMatrix::CSR(:specified-elements(7), :dimensions((5, 8)), :density(0.175))

Here it is "pretty printed":

$matrix1.print;
# .    .    .    .    0.36 .    0.08 .   
# .    .    .    0.6  .    .    .    .   
# .    .    .    .    .    0.84 .    0.61
# .    .    .    0.3  .    .    0.29 .   
# .    .    .    .    .    .    .    .

Here 10 is multiplied with all elements:

my $matrix2 = $matrix1.multiply(10); 

$matrix2.print;
# .   .   .   .   3.6 .   0.8 .  
# .   .   .   6   .   .   .   .  
# .   .   .   .   .   8.4 .   6.1
# .   .   .   3   .   .   2.9 .  
# .   .   .   .   .   .   .   .

Here is the dot-product of the original matrix with its transpose:

my $matrix3 = $matrix1.dot($matrix1.transpose); 

$matrix3.print;
# 0.13599999999999998 .                   .                   0.0232              .                  
# .                   0.36                .                   0.18                .                  
# .                   .                   1.0776999999999999  .                   .                  
# 0.0232              0.18                .                   0.17409999999999998 .                  
# .                   .                   .                   .                   .

Special features

Here are few features that other SMA packages typically do not provide.

Named rows and columns

It is very convenient to have named rows and columns that are respected (or preserved) in the typical SMA operations.

Here is an example:

my $smat = Math::SparseMatrix.new($matrix1, row-names => 'a' .. 'e', column-names => 'A' .. 'H'); 

$smat.print;
# –––––––––––––––––––––––––––––––––––––––––––
#     A    B    C    D    E    F    G    H   
# ––┼––––––––––––––––––––––––––––––––––––––––
# a │ .    .    .    .    0.36 .    0.08 .   
# b │ .    .    .    0.6  .    .    .    .   
# c │ .    .    .    .    .    0.84 .    0.61
# d │ .    .    .    0.3  .    .    0.29 .   
# e │ .    .    .    .    .    .    .    .

Here is the dot-product of that matrix with its transpose:

my $smat2 = $smat.dot($smat.transpose); 

$smat2.round(0.02).print;
# ––––––––––––––––––––––––––––
#     a    b    c    d    e   
# ––┼–––––––––––––––––––––––––
# a │ 0.14 .    .    0.02 .   
# b │ .    0.36 .    0.18 .   
# c │ .    .    1.08 .    .   
# d │ 0.02 0.18 .    0.18 .   
# e │ .    .    .    .    .

Implicit value

The sparse matrices can have an implicit value that is different from 0. For example, adding a number to a sparse matrix produces another sparse matrix with different implicit value:

my $matrix3 = $matrix1.add(10);
# Math::SparseMatrix::CSR(:specified-elements(7), :dimensions((5, 8)), :density(0.175))
$matrix3.implicit-value
# 10

Here is the pretty print:

$matrix3.print(:iv)
# 10    10    10    10    10.36 10    10.08 10   
# 10    10    10    10.6  10    10    10    10   
# 10    10    10    10    10    10.84 10    10.61
# 10    10    10    10.3  10    10    10.29 10   
# 10    10    10    10    10    10    10    10

Remark: Currently, the implicit values are ignored in dot.


Design

General

Object-Oriented Programming (OOP) architecture

Here is a corresponding diagram:

classDiagram
    class Abstract["Math::SparseMatrix::Abstract"] {
        <<abstract>>
        +value-at()
        +row-at()
        +column-at()
        +row-slice()
        +AT-POS()
        +print()
        +transpose()
        +add()
        +multiply()
        +dot()
    }
    
    class CSR["Math::SparseMatrix::CSR"] {
        @row-ptr
        @col-index
        @values
        nrow
        ncol
        implicit-value
    }
    
    class DOK["Math::SparseMatrix::DOK"] {
        %adjacency-map
        nrow
        ncol
        implicit-value
    }
    
    class SparseMatrix["Math::SparseMatrix"] {
        Abstract core-matrix
        +AT-POS()
        +print()
        +transpose()
        +add()
        +multiply()
        +dot()
    }
    
    CSR --> Abstract : implements
    DOK --> Abstract : implements
    SparseMatrix --> Abstract : Hides actual component class
    SparseMatrix *--> Abstract

Implementation details


Performance


Acknowledgements

Thanks to @lizmat and @tony-o for helping figuring out the proper use of postcircumfix:<[]> and postcircumfix:<[; ]> in order to have the named rows and columns functionalities.


References

Books

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

Packages

[AAp1] Anton Antonov, ML::StreamsBlendingRecommender Raku package, (2021-2024), GitHub/antononcube.

[AAp2] Anton Antonov, Graph Raku package, (2024), GitHub/antononcube.

Videos

[AAv1] Anton Antonov, "TRC 2022 Implementation of ML algorithms in Raku", (2022), YouTube/antononcube.