Linear complexity parallel algorithms for linear systems of equations with recursive structure (Q578844)

The paper contains descriptions of fast algorithms for implementation on parallel processors for the solution of linear algebraic equations, the triangular factorization and inversion of matrices. These matrices are assumed to be strongly regular (i.e. with non-singular principal submatrices) and to have what is called here a recursive structure. Algorithms were given in a previous paper by the first three authors [Efficient solutions of linear systems of equations with recursive structure, ibid. 80, 81-113 (1986)], these are re-written here so as to avoid the calculation of inner products. The general treatment is illustrated by a consideration of Levinson's algorithm for strongly regular symmetric Toeplitz matrices which aims at calculating the UDL factorization and the inverse of a matrix. The authors define in the next section structured extensions and other concepts which are needed in the remainder of the paper. This is devoted to algorithms for the solution of equations when the matrix is Toeplitz, Hankel, Close-to-Hankel, Hilbert type and Vandermonde type as well as, in most cases, methods for their factorization and inversion. The authors pay close attention to operation counts and to the complexity of the methods. The paper ends with a short discussion of the non-strongly- regular case which is followed by some numerical examples to demonstrate the stability of some of their methods.