pic_csr Module

A compressed sparse row matrix: the standard layout for sparse linear algebra and, identically, for adjacency lists of weighted graphs. pic_graph builds its shortest-path algorithms directly on this type.

### Layout

A csr_t holds the usual triple, all of it one-based:

  • row_ptr(1:nrow+1) - row_ptr(i) is the index in col_idx/values of the first stored entry of row i, and row_ptr(i+1) - 1 the index of its last. row_ptr(1) is always 1 and row_ptr(nrow+1) is nnz + 1.
  • col_idx(1:nnz) - column index of each stored entry, sorted ascending within every row.
  • values(1:nnz) - the matching real(dp) values.

An empty row i is represented by row_ptr(i) == row_ptr(i+1), which makes every row loop do k = row_ptr(i), row_ptr(i+1) - 1 iterate zero times. That case is explicitly supported and tested.

### Duplicate coordinate entries are summed

build_from_coo accepts coordinate triplets in any order. Repeated (i, j) coordinates are summed, which is the conventional finite-element assembly semantics and makes the builder usable directly as an assembly routine. Duplicates are not an error.

### Components are public on purpose

The three arrays and the shape are public components so that consumers such as pic_graph can walk rows without copying. Writing to them by hand can produce a structurally broken matrix, which is exactly what is_valid exists to detect; matvec, transpose and row_slice call it before touching any index, so a malformed matrix produces an error_t rather than an out-of-bounds access.

### Usage

 type(csr_t) :: a
 type(error_t) :: err
 real(dp) :: y(2)

 call a%build_from_coo(2_default_int, 2_default_int, &
                       [1_default_int, 2_default_int], &
                       [2_default_int, 1_default_int], &
                       [3.0_dp, 4.0_dp], err)
 call a%matvec([1.0_dp, 1.0_dp], y, err)

Uses

  • module~~pic_csr~~UsesGraph module~pic_csr pic_csr module~pic_error pic_error module~pic_csr->module~pic_error module~pic_types pic_types module~pic_csr->module~pic_types module~pic_error->module~pic_types module~pic_global_definitions pic_global_definitions module~pic_error->module~pic_global_definitions iso_c_binding iso_c_binding module~pic_types->iso_c_binding iso_fortran_env iso_fortran_env module~pic_types->iso_fortran_env module~pic_global_definitions->module~pic_types

Used by

  • module~~pic_csr~~UsedByGraph module~pic_csr pic_csr module~pic_graph pic_graph module~pic_graph->module~pic_csr

Derived Types

type, public ::  csr_t

Compressed sparse row matrix with real(dp) values.

Components

Type Visibility Attributes Name Initial
integer(kind=default_int), public, allocatable :: col_idx(:)

Column index of every stored entry, ascending within each row
integer(kind=default_int), public :: ncol = 0

Number of columns; prefer the n_cols accessor when reading
integer(kind=default_int), public :: nrow = 0

Number of rows; prefer the n_rows accessor when reading
integer(kind=default_int), public, allocatable :: row_ptr(:)

Row start offsets, size nrow + 1, one-based
real(kind=dp), public, allocatable :: values(:)

Value of every stored entry, parallel to col_idx

Type-Bound Procedures

procedure, public :: build_from_coo => csr_build_from_coo
procedure, public :: destroy => csr_destroy
procedure, public :: is_valid => csr_is_valid
procedure, public :: matvec => csr_matvec
procedure, public :: n_cols => csr_n_cols
procedure, public :: n_rows => csr_n_rows
procedure, public :: nnz => csr_nnz
procedure, public :: row_slice => csr_row_slice
procedure, public :: transpose => csr_transpose

Functions

private function csr_is_valid(self, err) result(ok)

Check that the stored triple is structurally consistent.

Read more…

Arguments

Type IntentOptional Attributes Name
class(csr_t), intent(in) :: self
type(error_t), intent(out), optional :: err

Return Value logical

.true. when the matrix is structurally sound

private pure function csr_n_cols(self) result(n)

Number of columns of the matrix.

Arguments

Type IntentOptional Attributes Name
class(csr_t), intent(in) :: self

Return Value integer(kind=default_int)

private pure function csr_n_rows(self) result(n)

Number of rows of the matrix.

Arguments

Type IntentOptional Attributes Name
class(csr_t), intent(in) :: self

Return Value integer(kind=default_int)

private pure function csr_nnz(self) result(n)

Number of stored entries, including any explicitly stored zeros.

Arguments

Type IntentOptional Attributes Name
class(csr_t), intent(in) :: self

Return Value integer(kind=default_int)


Subroutines

private subroutine csr_build_from_coo(self, n_rows, n_cols, rows, cols, vals, err)

Build the matrix from coordinate (COO) triplets.

Read more…

Arguments

Type IntentOptional Attributes Name
class(csr_t), intent(inout) :: self
integer(kind=default_int), intent(in) :: n_rows

Number of rows of the assembled matrix
integer(kind=default_int), intent(in) :: n_cols

Number of columns of the assembled matrix
integer(kind=default_int), intent(in) :: rows(:)

Row coordinate of each triplet
integer(kind=default_int), intent(in) :: cols(:)

Column coordinate of each triplet
real(kind=dp), intent(in) :: vals(:)

Value of each triplet
type(error_t), intent(out), optional :: err

private subroutine csr_destroy(self)

Release all storage and reset the matrix to an empty 0 by 0 one.

Arguments

Type IntentOptional Attributes Name
class(csr_t), intent(inout) :: self

private subroutine csr_matvec(self, x, y, err)

Sparse matrix-vector product y = A*x.

Read more…

Arguments

Type IntentOptional Attributes Name
class(csr_t), intent(in) :: self
real(kind=dp), intent(in) :: x(:)

Input vector of length n_cols
real(kind=dp), intent(out) :: y(:)

Output vector of length n_rows
type(error_t), intent(out), optional :: err

private subroutine csr_row_slice(self, i, cols, vals, err)

Copy out the column indices and values stored in row i.

Read more…

Arguments

Type IntentOptional Attributes Name
class(csr_t), intent(in) :: self
integer(kind=default_int), intent(in) :: i

Row to read, in 1:nrow
integer(kind=default_int), intent(out), allocatable :: cols(:)

Column indices of row i, ascending
real(kind=dp), intent(out), allocatable :: vals(:)

Values of row i, parallel to cols
type(error_t), intent(out), optional :: err

private subroutine csr_transpose(self, at, err)

Build the transpose of this matrix into at.

Read more…

Arguments

Type IntentOptional Attributes Name
class(csr_t), intent(in) :: self
type(csr_t), intent(out) :: at

Receives the transpose
type(error_t), intent(out), optional :: err

private pure subroutine fail(err, message)

Set err to ERROR_VALIDATION with message, when err is present.

Arguments

Type IntentOptional Attributes Name
type(error_t), intent(out), optional :: err
character(len=*), intent(in) :: message

Human-readable description of the violation

private pure subroutine sort_row(cols, vals, lo, hi)

Insertion-sort one row segment lo:hi by column index.

Read more…

Arguments

Type IntentOptional Attributes Name
integer(kind=default_int), intent(inout) :: cols(:)
real(kind=dp), intent(inout) :: vals(:)
integer(kind=default_int), intent(in) :: lo
integer(kind=default_int), intent(in) :: hi