Title: Parallel complexity of householder QR factorization
Abstract: Gaussian 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. Gaussian Elimination with Partial Pivoting was already known to be P-complete. 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.
Publication Year: 1996
Publication Date: 1996-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 3
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot