This paper investigates some of the ideas and algorithms developed for exploiting the structure of quasiseparable matrices. The case of purely scalar generators is considered initially. The process by which a quasiseparable matrix is represented as the product of matrices comprised of its generators is explained. This is done clearly in the scalar case, but may be extended to block generators. The complete factoring approach is then considered. This consists of two stages: inner-outer factorization followed by inner-coprime factorization. Finally, the stability of the algorithm is investigated. The algorithm is used to factor various quasiseparable matrices R created first using minimal generators, and subsequently using non-minimal generators. The result is that stability of the algorithm is compromised when non-minimal generators are present.

This research introduces a row compression and nested product decomposition of an nxn hierarchical representation of a rank structured matrix A, which extends the compression and nested product decomposition of a quasiseparable matrix. The hierarchical parameter extraction algorithm of a quasiseparable matrix is efficient, requiring only O(nlog(n))operations, and is proven backward stable. The row compression is comprised of a sequence of small Householder transformations that are formed from the low-rank, lower triangular, off-diagonal blocks of the hierarchical representation. The row compression forms a factorization of matrix A, where A = QC, Q is the product of the Householder transformations, and C preserves the low-rank structure in both the lower and upper triangular parts of matrix A. The nested product decomposition is accomplished by applying a sequence of orthogonal transformations to the low-rank, upper triangular, off-diagonal blocks of the compressed matrix C. Both the compression and decomposition algorithms are stable, and require O(nlog(n)) operations. At this point, the matrix-vector product and solver algorithms are the only ones fully proven to be backward stable for quasiseparable matrices. By combining the fast matrix-vector product and system solver, linear systems involving the hierarchical representation to nested product decomposition are directly solved with linear complexity and unconditional stability. Applications in image deblurring and compression, that capitalize on the concepts from the row compression and nested product decomposition algorithms, will be shown.