| Autor: | Barry W. Peyton, John R. Gilbert, Esmond G. Ng, Xiaoye S. Li |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Computer Networks and Communications
Applied Mathematics MathematicsofComputing_NUMERICALANALYSIS Incomplete LU factorization Incomplete Cholesky factorization LU decomposition Congruence of squares Matrix decomposition law.invention QR decomposition Combinatorics Computational Mathematics law Dixon's factorization method Software Sparse matrix Mathematics |
| Zdroj: | Bit Numerical Mathematics. 41:693-710 |
| ISSN: | 0006-3835 |
| DOI: | 10.1023/a:1021943902025 |
| Popis: | We present algorithms to determine the number of nonzeros in each row and column of the factors of a sparse matrix, for both the QR factorization and the LU factorization with partial pivoting. The algorithms use only the nonzero structure of the input matrix, and run in time nearly linear in the number of nonzeros in that matrix. They may be used to set up data structures or schedule parallel operations in advance of the numerical factorization. The row and column counts we compute are upper bounds on the actual counts. If the input matrix is strong Hall and there is no coincidental numerical cancellation, the counts are exact for QR factorization and are the tightest bounds possible for LU factorization. These algorithms are based on our earlier work on computing row and column counts for sparse Cholesky factorization, plus an efficient method to compute the column elimination tree of a sparse matrix without explicitly forming the product of the matrix and its transpose. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink