Skip to Main content Skip to Navigation
Journal articles

Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic

Abstract : We consider the LU factorization of an $n\times n$ matrix $A$ represented as a block low-rank (BLR) matrix: most of its off-diagonal blocks are approximated by matrices of small rank $r$, which reduces the asymptotic complexity of computing the LU factorization of A down to $O(n^2r)$. In this article, our aim is to further reduce this complexity by exploiting fast matrix arithmetic, that is, the ability to multiply two $n\times n$ full-rank matrices together for $O(n^\omega)$ flops, where $\omega<3$. This is not straightforward: simply accelerating the intermediate operations performed in the standard BLR factorization algorithm does not suffice to reduce the quadratic complexity in $n$, because these operations are performed on matrices whose size is too small. To overcome this obstacle, we devise a new BLR factorization algorithm that, by recasting the operations so as to work on intermediate matrices of larger size, can exploit more efficiently fast matrix arithmetic. This new algorithm achieves an asymptotic complexity of $O(n^{(\omega+1)/2} r^{(\omega-1)/2})$, which represents an asymptotic improvement compared to the standard BLR factorization as soon as $\omega<3$. In particular, for Strassen's algorithm, $\omega\approx 2.81$ yields a complexity of $O(n^{1.904} r^{0.904})$. Our numerical experiments are in good agreement with this analysis.
Complete list of metadata

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/hal-02008666
Contributor : Theo Mary <>
Submitted on : Thursday, November 28, 2019 - 2:34:47 PM
Last modification on : Friday, June 25, 2021 - 3:40:05 PM

File

FastBLR.pdf
Files produced by the author(s)

Identifiers

Citation

Claude-Pierre Jeannerod, Théo Mary, Clément Pernet, Daniel Roche. Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic. SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2019, 40 (4), pp.1478-1496. ⟨10.1137/19M1255628⟩. ⟨hal-02008666v4⟩

Share

Metrics

Record views

519

Files downloads

1530