Search NASA⌕ Search

DOE OSTI · 970310

Improved parallel data partitioning by nested dissection with applications to information retrieval.

Abstract

The computational work in many information retrieval and analysis algorithms is based on sparse linear algebra. Sparse matrix-vector multiplication is a common kernel in many of these computations. Thus, an important related combinatorial problem in parallel computing is how to distribute the matrix and the vectors among processors so as to minimize the communication cost. We focus on minimizing the total communication volume while keeping the computation balanced across processes. In [1], the first two authors presented a new 2D partitioning method, the nested dissection partitioning algorithm. In this paper, we improve on that algorithm and show that it is a good option for data partitioning in information retrieval. We also show partitioning time can be substantially reduced by using the SCOTCH software, and quality improves in some cases, too.

Explore related subjects

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Wolf, Michael M, Chevalier, Cedric, Boman, Erik Gunnar. 2008-12-01. Improved parallel data partitioning by nested dissection with applications to information retrieval.. https://www.osti.gov/biblio/970310

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related reports

Fire Protection Design

The purpose of this project is to design the demolition and installation of a deluge valve swap from a DV-5 to a DV-5A valve.

99 GENERAL AND MISCELLANEOUS↗