Naslov
On the failure of rank revealing QR factorization software : a case study

Autori
Drmač, Zlatko ; Bujanović, Zvonimir

Izvornik
ACM Transactions on Mathematical Software (0098-3500) 35 (2008), 2; 12:1-12:28

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
QR factorization; column pivoting; rank revealing

Sažetak
This paper reports an unexpected and rather erratic behavior of the LAPACK software implementation of the QR factorization with Businger--Golub column pivoting. It is shown that, due to finite precision arithmetic, the software implementation of the factorization can catastrophically fail to produce properly structured triangular factor, thus leading to potentially severe underestimate of a matrix's numerical rank. The 30 year old problem, dating back to LINPACK, has (undetected) badly affected many computational routines and software packages, as well as the study of rank revealing QR factorizations. We combine computer experiments and numerical analysis to isolate, analyze and fix the problem. Our modification of the current LAPACK xGEQP3 routine is already included in the LAPACK 3.1.0 release. The modified routine is numerically more robust and with a negligible overhead. We also provide a new, equally efficient and provably numerically safe, partial column norm updating strategy.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

Napomena
Http://www.cs.kent.ac.uk/projects/toms/cgi/TOMSbibget.cgi?Drmac:2008: Preliminarni report je objavlen u LAPACK Working Notes, broj 176, kao tehnički izvještaj u okviru projekta LAPACK. Rezultat rada je i doprinos u obliku softwarea - novi programi za QR faktorizaciju sa pivotiranjem koji su već uključeni u novu inačicu LAPACKa.

POVEZANOST RADA