Sparse Prefix Sum

Defined in data_structures/sparse_prefix_sum.hpp

template<typename Int, typename Value>
class sarma::sparse_prefix_sum

Subclassed by sparse_prefix_sum_wrapper

Public Functions

inline auto getN() const
inline auto getM() const
inline auto size() const

return the maximum of row or column of the underlying matrix

sparse_prefix_sum() = default
inline sparse_prefix_sum(const Matrix<Int, Value> &A_)

Constructor to construct sparse prefix sum data structure for a given matrix.

Parameters

  • A_: the input matrix

inline Value query(Int i, Int j) const

Queries the rectangle whose bottom right corner is given.

Parameters

  • i: the row of the bottom right corner

  • j: the column of the bottom right corner

inline Value query(std::pair<Int, Int> upper_left, std::pair<Int, Int> lower_right) const

Queries the rectangle whose upper left and bottom right corners are given.

Parameters

  • upper_left: holds the row and column in this order

  • lower_right: holds the row and column in this order

inline Value total_load() const

Returns the sum of all nonzeros in the underlying matrix.

inline std::vector<std::vector<Value>> compute_loads(const std::vector<Int> &p, const std::vector<Int> &q) const

Given two cut vectors, returns the tile loads implied by the cut vectors.

Parameters

  • p: the cut vector along rows

  • q: the cut vector along columns

inline Value compute_maxload(const std::vector<Int> &p, const std::vector<Int> &q) const

Given two cut vectors, returns the maximum load implied by the cut vectors.

Parameters

  • p: the cut vector along rows

  • q: the cut vector along columns

inline auto compute_maxload(const std::vector<Int> &p, const std::vector<Int> &q, const Int idx, bool col = false) const

Given two cut vectors, returns the maximum load of either idx’th row or column depending on the col parameter implied by the cut vectors.

Parameters

  • p: the cut vector along rows

  • q: the cut vector along columns

  • idx: the row or column index in the tile load matrix

  • col: whether idx is for rows or columns