English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate sparse matrix bipartitioning -- a problem where we minimizethe communication volume in parallel sparse matrix-vector multiplication. Weprove, by reduction from graph bisection, that this problem is$\mathcal{NP}$-complete in the case where each side of the bipartitioning mustcontain a linear fraction of the nonzeros.  We present an improved exact branch-and-bound algorithm which finds theminimum communication volume for a given matrix and maximum allowed imbalance.The algorithm is based on a maximum-flow bound and a packing bound, whichextend previous matching and packing bounds.  We implemented the algorithm in a new program called MP (Matrix Partitioner),which solved 839 matrices from the SuiteSparse collection to optimality, eachwithin 24 hours of CPU-time. Furthermore, MP solved the difficult problem ofthe matrix cage6 in about 3 days. The new program is on average more than tentimes faster than the previous program MondriaanOpt.  Benchmark results using the set of 839 optimally solved matrices show thatcombining the medium-grain/iterative refinement methods of the Mondriaanpackage with the hypergraph bipartitioner of the PaToH package produces sparsematrix bipartitionings on average within 10% of the optimal solution.

An improved exact algorithm and an NP-completeness proof for sparse matrix bipartitioning