|
Abstract : |
Abstract: We show that over a field of characteristic p the solution to a non-singular system of n linear equations in n unknows, with 2 p! n, whose coefficient matrix is of displacement rank ff and which is given as a sum of ff LU-products of Toeplitz matrices, can be computed in parallel with randomization simultaneously in O((log n) 3) time and a total work of O(maxfffn; p 2 g n \Theta log n loglog n). A time unit represents an arithmetic operation in the coefficient field. Our solution is based on our recursive parallel triangulation technique for processor-efficient parallel linear system solving over fields of characteristic p. In particular, we show that our recursive parallel triangulation technique can be implemented in a way that preserves Toeplitz-likeness., |
