A generalized Schur-type algorithm for the joint factorization of a structured matrix and its inverse

A Schur-type algorithm is presented for the simultaneous triangular factorization of a given (non-degenerate) structured matrix and its inverse. The algorithm takes the displacement generator of a Hermitian, strongly regular matrixR as an input, and computes the displacement generator of the inverse matrixR−1 as an output. From these generators we can directly deduce theLD−1L* (lower-diagonal-upper) decomposition ofR, and theUD−1U* (upper-diagonallower) decomposition ofR−1. The computational complexity of the algorithm isO(rn2) operations, wheren andr denote the size and the displacement rank ofR, respectively. Moreover, this method is especially suited for parallel (systolic array) implementations: usingn processors the algorithm can be carried out inO(n) steps.