Skip to Main content Skip to Navigation
Habilitation à diriger des recherches

Partitioning, matching, and ordering: Combinatorial scientific computing with matrices and tensors

Abstract : This HDR investigates three classes of problems at the interplay of discrete algorithms, combinatorial optimization, and numerical methods. The three problem classes are that of partitioning, matching, and ordering. Partitioning problems arise in task decomposition for parallel computing, where load balance and low communication cost are two objectives. We discuss acyclic partitioning of directed acyclic graphs and hypergraphs. While our contributions for the former problem concern combinatorial tools for the desired partitioning objectives and constraints, those for the second problem concern the use of hypergraph partitioning tools for efficient tensor decomposition in distributed memory systems. Matching problems arise in settings where agents compete for exclusive access to resources. We present approximation algorithms for matchings in graphs and effective heuristics for finding matchings in hypergraphs. We also investigate the problem of finding Birkhoff--von Neumann decompositions with a small number of permutation matrices and present complexity results and theoretical insights into this problem. Ordering problems arise when one wants to permute sparse matrices and tensors into desirable forms. We propose heuristics to permute sparse matrices into special forms to reduce the height of the resulting elimination tree. We also propose heuristics to cluster nonzeros of a given sparse tensor around the diagonal in order to improve the performance of certain tensor operations. The general research area is called combinatorial scientific computing (CSC). In CSC, the contributions have practical and theoretical flavor. For all problems discussed in this document, we have the design, analysis, and implementation of algorithms along with many experiments. The theoretical results are included in this document, some with proofs; the reader is invited to the original papers for the omitted proofs. A similar approach is taken for presenting the experiments. While most results for observing theoretical findings in practice are included, the reader is referred to the original papers for some other results (e.g., run time analysis).
Document type :
Habilitation à diriger des recherches
Complete list of metadata

Cited literature [225 references]  Display  Hide  Download

https://hal.inria.fr/tel-02377874
Contributor : Bora Uçar <>
Submitted on : Sunday, November 24, 2019 - 4:41:03 PM
Last modification on : Tuesday, November 26, 2019 - 1:36:22 AM
Long-term archiving on: : Tuesday, February 25, 2020 - 2:06:23 PM

File

bu_hdr_hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-02377874, version 1

Collections

Citation

Bora Uçar. Partitioning, matching, and ordering: Combinatorial scientific computing with matrices and tensors. Computer Science [cs]. ENS de Lyon, 2019. ⟨tel-02377874⟩

Share

Metrics

Record views

159

Files downloads

686