Cache-oblivious Matrix Multiplication for Exact Factorisation
For researchers working on exact linear algebra over finite fields, this work improves cache efficiency in a specific algorithmic context.
The authors present a cache-oblivious matrix multiplication method for exact factorization over finite fields, achieving orders of magnitude runtime improvement despite recursion overhead.
We present a cache-oblivious adaptation of matrix multiplication to be incorporated in the parallel TU decomposition for rectangular matrices over finite fields, based on the Morton-hybrid space-filling curve representation. To realise this, we introduce the concepts of alignment and containment of sub-matrices under the Morton-hybrid layout. We redesign the decompositions within the recursive matrix multiplication to force the base case to avoid all jumps in address space, at the expense of extra recursive matrix multiplication (MM) calls. We show that the resulting cache oblivious adaptation has low span, and our experiments demonstrate that its sequential evaluation order demonstrates orders of magnitude improvement in run-time, despite the recursion overhead.