Skip to content

Stdlib Sparse matrix API

Jump to bottom
Williams A. Lima edited this page May 17, 2020 · 43 revisions

Stdlib Sparse matrix API Specification

https://github.com/fortran-lang/stdlib/issues/38

Introduction

Goals

To be compact instead of being exhaustive. It aims at supplying Fortran users with a minimum (yet useful) number of routines and data structures related to sparse matrices storage and operations. This library is particularly targeted at a non-expert in numerical computation public. Thus we aim at having a simple and easy to use API.

Sparse matrix representations supported

This section is based on Saad (1994). In that work, a much more complete and extensive list of formats is described. Here we take only the ones that we think are most useful at the moment.

Coordinate format (COO)

Given an m by n real or complex matrix A containing nnz nonzero elements with each element denoted by a_ij this format represents A using a set of three arrays: values, rows, and columns, as described below.

values A real/complex array of size nnz containing the matrix elements a_ij in any order.

rows An integer array of size nnz containing the row indices of the elements a_ij.

columns An integer array of size nnz containing the column indices of the elements a_ij.

The Sparse_COO_t type

type :: Sparse_COO_t
   complex (kind = prec), allocatable, dimension (:) :: values
   integer, allocatable, dimension (:) :: rows
   columns, allocatable, dimension (:) :: columns
end type Sparse_COO_t

Attributes

values Complex, dynamically allocated, rank 1 array.

The non-zero values of the matrix A in any order.

rows Integer, dynamically allocated, rank 1 array.

The corresponding row indices of the values stored in the array values.

columns Integer, dynamically allocated, rank 1 array.

The corresponding column indices of the values stored in the arra values.

Compressed Sparse Row (CSR)

Given an m by n real or complex matrix A containing nnz nonzero elements with each element denoted by a_ij this format represents A using a set of three arrays: values, ja, and ia, as described below.

values A real/complex array of size nnz containing the matrix elements a_ij stored row by row from row 1 to row n.

ja An integer array of size nnz containing the column indices of the elements a_ij as stored in the array values.

ia An integer array of size n+1 containing the index in the arrays values and ja where each row starts. The value at ia(n+1) always has the value ia(1)+nnz.

Compressed Sparse Column (CSC)

This format is similar to the CSR format described previously. The difference is that instead of storing row values we store column values in the array values. The exact description of this format is given below.

Given an m by n real or complex matrix A containing nnz nonzero elements with each element denoted by a_ij this format represents A using a set of three arrays: values, ja, and ia, as described below.

values A real/complex array of size nnz containing the matrix elements a_ij stored column by column from column 1 to column m.

ia An integer array of size nnz containing the row indices of the elements a_ij as stored in the array values.

ja An integer array of size m+1 containing the index in the arrays values and ia where each column starts. The value at ja(m+1) always has the value ja(1)+nnz.

Sorting

Creational subroutines

Conversion subroutines

Algebraic operations

All the core routines work only with the COO format. All their input/output arguments are in the COO format. On the other the use of the supplied conversion routines and a generic interface makes the use of the core routines transparent for the end user. fig01

interface sparse_matmul
   module procedure sparse_matmul_csr
   module procedure sparse_matmul_ccr
   module procedure sparse_matmul_coo
end interface sparse_matmul

subroutine sparse_matmul_csr (a, b, c)
  ! Arguments
  type (Sparse_CSR_t), intent (in)  :: a, b
  type (Sparse_CSR_t), intent (out) :: c
  ! Local variables
  type (Sparse_COO_t) :: a_coo, b_coo, c_coo

  call Sparse_CSR_to_COO (a, a_coo)
  call Sparse_CSR_to_COO (b, b_coo)

  call Sparse_matmul (a_coo, b_coo, c_coo)
  
  call Sparse_COO_CSR (c_coo, c)

end subroutine sparse_matmul_csr

Level 1 - Vector-vector operations

Function Name

Syntax

Arguments

Return value

Description

Level 2 - Matrix-vector operations

Level 3 - Matrix-matrix operations

Utilities

Input/Output

References

Saad, Y., SPARSKIT: A basic tool kit for sparse matrix computation, 1994.https://www-users.cs.umn.edu/~saad/software/SPARSKIT/

Clone this wiki locally