Parallel complexity of householder QR factorization

Mauro Leoncini, Giovanni Manzini, Luciano Margara

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Ganssian Elimination with Partial Pivoting and Householder QR factorization are two very popular methods to solve linear systems. Implementations of these two methods are provided in state-of-the-art numerical libraries and packages, such as LAPACK and MATLAB. Ganssian Elimination with Partial Pivoting was already known to be Pcomplete. Here we prove that the Householder QR factorization is likely to be inherently sequential as well. We also investigate the problem of speedup vs non degeneracy and accuracy in numerical algorithms.

Original languageEnglish
Title of host publicationAlgorithms - ESA 1996 - 4th Annual European Symposium, Proceedings
EditorsJosep Diaz, Maria Serna
PublisherSpringer Verlag
Pages290-301
Number of pages12
ISBN (Print)3540616802, 9783540616801
DOIs
Publication statusPublished - 1996
Externally publishedYes
Event4th European Symposium on Algorithms, ESA 1996 - Barcelona, Spain
Duration: 25 Sept 199627 Sept 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1136
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th European Symposium on Algorithms, ESA 1996
Country/TerritorySpain
CityBarcelona
Period25/09/9627/09/96

Fingerprint

Dive into the research topics of 'Parallel complexity of householder QR factorization'. Together they form a unique fingerprint.

Cite this