On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms (Q865451)

A matrix \(A\in\mathbb{C}^{N\times N}\) is said to be quasiseparable of order \(p\) if all submatrices which do not cross the diagonal have rank less than or equal to \(p\). The proposed algorithm uses \(N-2\) unitary similarity transformations to reduce \(p\)-order quasiseparable matrices to their upper Hessenberg form \(B\). The computational cost is reduced to \(O(N^{2})\) flops and \(O(N)\) memory storage. In case \(A\) is Hermitian, then \(B\) turns out to be tridiagonal and the procedure out performs known fast \(QR\) algorithms.