Download havrabstract.pdf

Contents : Solving Rank De cient Linear-Least Squares Problems using Sparse QR Haim Avron Tel Aviv University We address the problem of solving linear least-squares problems min Ax b when A is a sparse m-by-n rank de cient or highly ill-conditioned matrix. When A is rank de cient there is an entire subspace of minimizers. When A is full rank but highly ill-conditioned there is a single minimizer but there are many x s that give almost the same residual norm. Of these minimizers or almostminimizers the user usually prefers a solution with a small norm. When A has full rank the problem can be solved e ciently using a direct solver based on the QR factorization. When A is rank-de cient or highly illconditioned the factorization A QR is not useful because the computed R is ill-conditioned. This usually leads to a solution with a huge norm. The singular-value decomposition (SVD) and rank-revealing QR factorizations can produce minimal-norm solutions but they are di cult to compute in the sparse case. Currently there are no sparse SVD algorithms and sparse rank-revealing QR factorizations can lead to excessive ll and only few implementations are available. We have developed a new method that uses a regular QR factorization instead of a rank-revealing QR factorization 1 . The idea is to build a QR factorization of a perturbed matrix A0 instead of A. We perturb by dynamically adding rows to A in such a way that (1) A0 is well conditioned and (2) The R factor of A has the same non-zero structure as the R factor of A. The R factor of A0 is used as a preconditioner to solve the least-squares problem using LSQR 2 . Theoretical analysis in 1 shows that the number of iterations is bounded by the number of rows added. We are now implementing and testing the algorithm proposed in 1 in an high performance QR factorization. We have already implemented a sparse multifrontal Householder QR factorization code. The code is based on the ideas presented in 3 although some of the details are di erent. We compare our code to MATLAB s implementation of sparse QR (which is based on the rowmerge algorithm of George and Heath 4 ). The results of the comparison will be presented. We plan to integrate our row-addition algorithm into the code in the near future. References: 1 Haim Avron Esmond Ng and Sivan Toledo. Using perturbed QR factorizations to solve linear least-squares problems. Submitted to SIAM Journal on Scienti c Computing 2007. 2 Christopher C. Paige and Michael A. Saunders. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8(1):43 71 1982. 1 3 Szu-Min Lu and Jesse L. Barlow.Multifrontal computation with the orthogonal factors of sparse matrices. SIAM J. on Matrix Analysis and Applications 17(3):658-679 1996. 4 A. George and M. T. Heath. Solution of sparse linear least squares problems using Givens rotations. Lin. Alg. and Its App. 34:69 83 1980. 2

INFO HASH : d59ce635cfe50b96f9999384afc3cdc5cd68cce9

Download now

File Size: 34.1 kb