Probe a Load (PaL)

Defined in algorithms/probe_a_load.hpp

namespace sarma::probe_a_load

Functions

template<typename Ordinal, typename Value>
std::vector<Ordinal> probe(const Matrix<Ordinal, Value> &A, const Value L, std::vector<Ordinal> *UB = nullptr)

Implements the Probe a Load algorithm. This algorithm applies a greedy probe algorithm on diagonal direction by running binary searches over the possible range of maximum load targets.

Return

a cut vector

Parameters

• A: Matrix

• P: number of parts

Template Parameters

• Ordinal: data-type of indptr and indices structures in sarma::Matrix

• Value: data-type of data structure in sarma::Matrix

template<typename Ordinal, typename Value>
auto partition(const Matrix<Ordinal, Value> &A, const Ordinal P)

Implements the dual of the Probe a Load (PaL) algorithm using Bound a Load procedure and applying PaL as the mNC algorithm. This algorithm applies a greedy probe algorithm on diagonal direction by running binary searches over the possible range of maximum load targets.

Return

a cut vector

Parameters

• A: Matrix

• P: number of parts