Efficient Matrix Partitioning Strategies for Accelerated Computation

Supervised by: Kalvin Dobler

If you are interested in this topic or have further questions, do not hesitate to contact kalvin.dobler@unibe.ch.

Context

The objective of this project is to investigate various matrix partitioning techniques to enhance computational efficiency in cost/distance matrices. These matrices frequently arise in optimization problems such as those in operations research, machine learning, or network analysis. Direct computation on large matrices can be computationally expensive and time-consuming. By partitioning these matrices into smaller sub-matrices and performing localized sub-optimizations, we aim to significantly reduce computation time while maintaining comparable solution accuracy.

Goal(s)

To explore different methods for partitioning matrices into smaller sub-matrices.
To evaluate the impact of partitioning on the runtime computation and overall performance of optimization algorithms.
To implement a framework for solving these sub-optimizations in parallel, where applicable, to further improve runtime computation.

Approach

Literature Review: begin by studying existing matrix partitioning techniques, including row/column splitting/reduction/clustering, block partitioning, sparsity, threshold etc.
Matrix Partitioning Methods: implement several strategies from uniform partitioning to hierarchical partitioning.
Optimization on Sub-Matrices: apply different optimization algorithms and investigate how they affect the computational efficiency and solution accuracy.
Parallelization: explore parallelization to further enhance the computation runtime and investigate its efficiency depending on the original matrix size, structure, sparsity etc.
Evaluation: conduct experiments on provided matrices from benchmark data sets.

Required Skills

Good programming skills
Basic statistics and a bit of graph theory and algorithms
Willingness to explore and learn more about these topics