Crate smawk

source ·
Expand description

This crate implements various functions that help speed up dynamic programming, most importantly the SMAWK algorithm for finding row or column minima in a totally monotone matrix with m rows and n columns in time O(m + n). This is much better than the brute force solution which would take O(mn). When m and n are of the same order, this turns a quadratic function into a linear function.

Examples

Computing the column minima of an m ✕ n Monge matrix can be done efficiently with smawk::column_minima:

use smawk::Matrix;

let matrix = vec![
    vec![3, 2, 4, 5, 6],
    vec![2, 1, 3, 3, 4],
    vec![2, 1, 3, 3, 4],
    vec![3, 2, 4, 3, 4],
    vec![4, 3, 2, 1, 1],
];
let minima = vec![1, 1, 4, 4, 4];
assert_eq!(smawk::column_minima(&matrix), minima);

The minima vector gives the index of the minimum value per column, so minima[0] == 1 since the minimum value in the first column is 2 (row 1). Note that the smallest row index is returned.

Definitions

Some of the functions in this crate only work on matrices that are totally monotone, which we will define below.

Monotone Matrices

We start with a helper definition. Given an m ✕ n matrix M, we say that M is monotone when the minimum value of row i is found to the left of the minimum value in row i' where i < i'.

More formally, if we let rm(i) denote the column index of the left-most minimum value in row i, then we have

rm(0) ≤ rm(1) ≤ ... ≤ rm(m - 1)

This means that as you go down the rows from top to bottom, the row-minima proceed from left to right.

The algorithms in this crate deal with finding such row- and column-minima.

Totally Monotone Matrices

We say that a matrix M is totally monotone when every sub-matrix is monotone. A sub-matrix is formed by the intersection of any two rows i < i' and any two columns j < j'.

This is often expressed as via this equivalent condition:

M[i, j] > M[i, j']  =>  M[i', j] > M[i', j']

for all i < i' and j < j'.

Monge Property for Matrices

A matrix M is said to fulfill the Monge property if

M[i, j] + M[i', j'] ≤ M[i, j'] + M[i', j]

for all i < i' and j < j'. This says that given any rectangle in the matrix, the sum of the top-left and bottom-right corners is less than or equal to the sum of the bottom-left and upper-right corners.

All Monge matrices are totally monotone, so it is enough to establish that the Monge property holds in order to use a matrix with the functions in this crate. If your program is dealing with unknown inputs, it can use monge::is_monge to verify that a matrix is a Monge matrix.

Modules

  • monge
    Functions for generating and checking Monge arrays.

Traits

  • Matrix
    Minimal matrix trait for two-dimensional arrays.

Functions