Nested Product Decomposition of Quasiseparable Matrices
Tom Bella, Vadim Olshevsky, Michael Stewart · SIAM Journal on Matrix Analysis and Applications · 2013
This paper introduces a nested product decomposition of an $n\times 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^2)$ 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.