CONCURRENT ITERATIVE ALGORITHM FOR TOEPLITZ-LIKE LINEAR-SYSTEMS

Suppose that a nonsingular n x n, matrix A is given with its short dis placement generator and thus has small displacement rank bounded by a fixed constant. (The class of such matrices generalizes Toeplitz matri ces.) Furthermore, suppose that a good initial approximation to a shor t displacement generator for A-1 is readily available (as in the case of updating the solution to the linear system Ax = b in real time). Th en we show how to refine this approximation and numerically compute a displacement generator of A-1 and the solution vector x = A-1b to a li near system Ax = b by using O(log2n) parallel arithmetic steps and n p rocessors. The techniques of our earlier work enable us to extend thes e results to some other important classes of dense structure matrices.