A DATA STRUCTURE FOR SPARSE QR AND LU FACTORIZATIONS

作     者：GEORGE, A LIU, J NG, E 

作者机构：YORK UNIVDEPT COMP SCIDOWNSVIEW M3J 1P3ONTARIOCANADA UNIV TENNESSEEDEPT COMP SCIKNOXVILLETN 37996 UNIV TENNESSEEDEPT MATHKNOXVILLETN 37996 

出 版 物：《SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING》 (工业与应用数学会科学计算杂志)

年 卷 期：1988年第9卷第1期

页      面：100-121页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：65F05 65F50 68R10 sparse matrix algorithms data structures Gaussian elimination sparse QR partial pivoting 

摘      要：For a general m by n sparse matrix A, a new scheme is proposed for the structural representation of the factors of its sparse orthogonal decomposition by Householder transformations. The storage scheme is row-oriented and is based on the structure of the upper triangular factor obtained in the decomposition. The storage of the orthogonal matrix factor is particularly efficient in that the overhead required is only $m + n$ items, independent of the actual number of nonzeros in the factor. The same scheme is applicable to sparse orthogonal factorization by Givens rotations, and also to the recent implementation of sparse Gaussian elimination with partial pivoting developed by George and Ng (this Journal, 1987, to appear). Experimental results are provided to compare the sparse Gaussian elimination using the new storage scheme with that proposed by George and Ng.