Achieving Numerical Accuracy and High Performance using Recursive Tile LU Factorization
type: Dataset
description: The LU factorization is an important numerical algorithm for solving systems of linear equations in science and engineering, and is characteristic of many dense linear algebra computations. It has even become the de facto numerical algorithm implemented within the LINPACK benchmark to rank the most powerful supercomputers in the world, collected bt the TOP500 website. In this context, the challenge in developing new algorithms for the scientific community resides in the combination of two goals: achieving high performance and maintaining the accuracy of the numerical algorithm. This paper proposes a novel approach for computing the LU factorization in parallel on multicore architectures, which not only improves the overall performance, but also sustains the numerical quality of the standard LU factorization algorithm with partial pivoting. While the update of the trailing submatrix is computationally intensive and highly parallel, the inherently problematic portion of the LU factorization is the panel factorization due to its memory-bound characteristic as well as the atomicity of selecting the appropriate pivots. Our approach uses a parallel fine-grained recursive formulation of the panel factorization step and implements the update of the trailing submatrix with the tile algorithm. Based on conflict-free partitioning of the data and lockless synchronization mechanisms, our implementation lets the overall computation flow naturally without contention. The dynamic runtime system called QUARK is then able to schedule tasks with heterogeneous granularities and to transparently introduce algorithmic lookahead. The performance results of our implementation are competitive compared to the currently available software packages and libraries. In particular, it is up to 40% faster when compared to the equivalent Intel MKL routine and up to 3-fold faster than LAPACK with multithreaded Intel MKL BLAS.
issued: 2026-05-11T15:06:23.247292
language: en
modified: 2026-05-11T15:06:23.247297
contact point: Organization
  fn: CCSD
keyword: infoeu-reposemanticsreport
keyword: infoinfo-dccomputer-science-csdistributed-parallel-and-cluster-computing-csdc
keyword: reports
landing page: https://inria.hal.science/hal-00809765

Achieving Numerical Accuracy and High Performance using Recursive Tile LU Factorization
type: Distribution
format: HTML
issued: 2026-05-11T15:06:23.252367
modified: 2026-05-11T15:06:23.241689
access URL: https://inria.hal.science/hal-00809765

test_moissonnage_selune
type: Agent