---
abstract: 'We present a recursive way to partition hypergraphs which creates and exploits hypergraph geometry and is suitable for many-core parallel architectures. Such partitionings are then used to bring sparse matrices in a recursive Bordered Block Diagonal form (for processor-oblivious parallel LU decomposition) or recursive Separated Block Diagonal form (for cache-oblivious sparse matrix–vector multiplication). We show that the quality of the obtained partitionings and orderings is competitive by comparing obtained fill-in for LU decomposition with SuperLU (with better results for $8$ of the $28$ test matrices) and comparing cut sizes for sparse matrix–vector multiplication with Mondriaan (with better results for $4$ of the $12$ test matrices). The main advantage of the new method is its speed: it is on average $21.6$ times faster than Mondriaan.'
author:
- 'B. O. Fagginger Auer[^1]'
- 'R. H. Bisseling[^2]'
bibliography:
- 'refs.bib'
title: A Geometric Approach to Matrix Ordering
---

hypergraphs, k-means, LU decomposition, nested dissection, partitioning, sparse matrices, visualization

05C65, 05C70, 65F05, 65F50, 65Y05

Introduction {#sec:intro}
============

With the increased development and availability of many-core processors (both CPUs and GPUs) it is important to have algorithms that can make use of these architectures. To this end, we present a new recursive hypergraph 