Nested Product Decomposition of Quasiseparable Matrices

This paper introduces a nested product decomposition of an n× n quasiseparable matrix A. The nested product is formed from small Householder transformations and very sparse matrices with only a few nonzeros isolated to a single column. The decomposition is computed by the direct application of Householder transformations and requires O(n²) operations. Once the matrix has been decomposed, matrix-vector products can be formed and linear systems can be solved with $O(n)$ operations. An error analysis shows that the algorithm is backward stable.