LU factorization for matrices in quasiseparable form via orthogonal transformations

摘要

The paper presents a new algorithm to compute the LU-factorization of a matrix represented in a quasiseparable or semiseparable form (i.e., using generators). It obtains the quasiseparable representations of the factors L and U of an N x N block matrix via O(N) arithmetic operations on the block entries. The algorithm uses recursions based exclusively on unitary transformations which provide numerical stability even in singular cases. The method of the paper is based on the theory developed in [1] and provides an alternative to the approach proposed in [7] for strongly regular matrices. The algorithm presented here works also for some matrices with possibly singular principle submatrices. The results of numerical tests show that also for strongly regular matrices the new algorithm is comparable with the previous methods. (C) 2016 Elsevier Inc. All rights reserved.