Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On Symmetric Rectilinear Matrix Partitioning   Even distribution of irregular workload to processing units is crucial for
efficient parallelization in many applications. In this work, we are concerned
with a spatial partitioning called rectilinear partitioning (also known as
generalized block distribution) of sparse matrices. More specifically, in this
work, we address the problem of symmetric rectilinear partitioning of a square
matrix. By symmetric, we mean the rows and columns of the matrix are
identically partitioned yielding a tiling where the diagonal tiles (blocks)
will be squares. We first show that the optimal solution to this problem is
NP-hard, and we propose four heuristics to solve two different variants of this
problem. We present a thorough analysis of the computational complexities of
those proposed heuristics. To make the proposed techniques more applicable in
real life application scenarios, we further reduce their computational
complexities by utilizing effective sparsification strategies together with an
efficient sparse prefix-sum data structure. We experimentally show the proposed
algorithms are efficient and effective on more than six hundred test matrices.
With sparsification, our methods take less than 3 seconds in the Twitter graph
on a modern 24 core system and output a solution whose load imbalance is no
worse than 1%.

16
The categories of this paper are: stat
18
The categories of this paper are: econ
29
The categories of this paper are: funct-an
4
The categories of this paper are: cond-mat
35
The categories of this paper are: mtrl-th
33
The categories of this paper are: plasm-ph
22
The categories of this paper are: chao-dyn
13
The categories of this paper are: quant-ph
20
The categories of this paper are: acc-phys
15
The categories of this paper are: nucl-ex
21
The categories of this paper are: adap-org
0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
10
The categories of this paper are: q-bio
34
The categories of this paper are: chem-ph
2
The categories of this paper are: math