An LDU decomposition algorithm for a block Toeplitz matrix having a parallel and pipelined computing structure (Q1822449)

This paper presents an LDU decomposition algorithm for a block Toeplitz matrix, which is well suited to a parallel and pipelined architecture. Writing the size of one block element as d and the number of the blocks as p, this algorithm requires \(O(p^ 2d^ 3)\) computing time on a sequential computer. Our proposed architecture achieves O(pd) computing time with a two-dimensional array of \(O(pd^ 2)\) processor elements.