Multiplying two sparse matrices (SpGEMM) is a common computational primitive used in many areas including graph algorithms, bioinformatics, algebraic multigrid solvers, and randomized sketching. distributed-memory par...
详细信息
ISBN:
(数字)9798350352917
ISBN:
(纸本)9798350352924;9798350352917
Multiplying two sparse matrices (SpGEMM) is a common computational primitive used in many areas including graph algorithms, bioinformatics, algebraic multigrid solvers, and randomized sketching. distributed-memory parallel algorithms for SpGEMM have mainly focused on sparsity-oblivious approaches that use 2d and 3d partitioning. Sparsity-aware 1d algorithms can theoretically reduce communication by not fetching nonzeros of the sparse matrices that do not participate in the multiplication. Here, we present a distributed-memory 1d SpGEMM algorithm and implementation. It uses MPI RdMA operations to mitigate the cost of packing/unpacking submatrices for communication, and it uses a block fetching strategy to avoid excessive fine-grained messaging. Our results show that our 1d implementation outperforms state-of-the-art 2d and 3d implementations within CombBLAS for many configurations, inputs, and use cases, while remaining conceptually simpler.
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. The problem is known to be QMA-complete, even for one-dimensional Hamiltonians [1]. This means that we do not even ex...
详细信息
ISBN:
(纸本)9781450326988
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. The problem is known to be QMA-complete, even for one-dimensional Hamiltonians [1]. This means that we do not even expect that there is a sub-exponential size description of the ground state that allows efficient computation of local observables such as the energy. In sharp contrast, the heuristic density matrix renormalization group (dMRG) algorithm invented two decades ago [5] has been remarkably successful in practice on one-dimensional problems. The situation is reminiscent of the unexplained success of the simplex algorithm before the advent of ellipsoid and interior-point methods. Is there a principled explanation for this, in the form of a large class of one-dimensional Hamiltonians whose ground states can be provably efficiently approximated? Here we give such an algorithm for gapped one-dimensional Hamiltonians: our algorithm outputs an (inverse-polynomial) approximation to the ground state, expressed as a matrix product state (MPS) of polynomial bonddimension. The running time of the algorithm is polynomial in the number of qudits n and the approximation quality δ, for a fixed local dimension d and gap Δ > 0.A key ingredient of our algorithm is a new construction of an operator called an approximate ground state projector (AGSP), a concept first introduced in [2] to derive an improved area law for gapped one-dimensional systems [3]. For this purpose the AGSP has to be efficiently constructed; the particular AGSP we construct relies on matrix-valued Chernoff bounds [4]. Other ingredients of the algorithm include the use of convex programming, recently discovered structural features of gapped1d quantum systems [2], and new techniques for manipulating and bounding the complexity of matrix product states.
暂无评论