QR Factorization of Tall and Skinny Matrices in a Grid Computing Environment

Emmanuel Agullo 1, 2, 3 Camille Coti 4, 5 Jack Dongarra 1 Thomas Herault 1, 4, 5 Julien Langou 6
2 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
5 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : To exploit the potential of multicore architectures, recent dense linear algebra libraries have used tile algorithms, which consist in scheduling a Directed Acyclic Graph (DAG) of tasks of fine granularity where nodes represent tasks, either panel factorization or update of a block-column, and edges represent dependencies among them. Although past approaches already achieve high performance on moderate and large square matrices, their way of processing a panel in sequence leads to limited performance when factorizing tall and skinny matrices or small square matrices. We present a new fully asynchronous method for computing a QR factorization on shared-memory multicore architectures that overcomes this bottleneck. Our contribution is to adapt an existing algorithm that performs a panel factorization in parallel (named Communication-Avoiding QR and initially designed for distributed-memory machines), to the context of tile algorithms using asynchronous computations. An experimental study shows significant improvement (up to almost 10 times faster) compared to state-of-the-art approaches. We aim to eventually incorporate this work into the Parallel Linear Algebra for Scalable Multi-core Architectures (PLASMA) library.
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/inria-00548900
Contributor : Emmanuel Agullo <>
Submitted on : Tuesday, December 21, 2010 - 9:39:58 AM
Last modification on : Friday, July 26, 2019 - 1:50:07 PM
Long-term archiving on : Monday, November 5, 2012 - 2:41:56 PM

File

grid-QR-IPDPS-2010.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : inria-00548900, version 1

Citation

Emmanuel Agullo, Camille Coti, Jack Dongarra, Thomas Herault, Julien Langou. QR Factorization of Tall and Skinny Matrices in a Grid Computing Environment. 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Apr 2010, Atlanta, United States. ⟨inria-00548900⟩

Share

Metrics

Record views

841

Files downloads

555