Separators and structure prediction in sparse orthogonal factorization

Autor:	Barry W. Peyton, Esmond G. Ng, John R. Gilbert
Rok vydání:	1997
Předmět:	Discrete mathematics Sequence Numerical Analysis Algebra and Number Theory Intersection graph Upper and lower bounds Combinatorics Matrix (mathematics) Factorization Discrete Mathematics and Combinatorics Orthogonal matrix Geometry and Topology Folk theorem Sparse matrix Mathematics
Zdroj:	Linear Algebra and its Applications. 262:83-97
ISSN:	0024-3795
DOI:	10.1016/s0024-3795(97)80024-9
Popis:	In the factorization A = QR of a sparse matrix A , the orthogonal matrix Q can be represented either explicitly (as a matrix) or implicitly (as a sequence of Householder vectors). A folk theorem states that the Householder vectors are much sparser than Q in practice. In this paper we make this folk theorem precise: we prove tight upper and lower bounds on the nonzero counts of the two representations in terms of the quality of separators in the column intersection graph of A . We conclude that the folk theorem is true when A is nearly square, but not when A has many more rows than columns.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e4d89bbd4ca65729f47f68c9341ec115 Zobrazit plný text záznamu Full Text from ScienceDirect