Fast parallel linear equation solvers based on textured decomposition

A fast linear equation solver based on recursive textured decompositions is introduced in this paper. The computational time complexity for solving problems of N unknown variables is in the order of one if N processors are available. It is faster than the multigrid method, so far known as the fastest available method for two dimensional Poisson equation, which has time complexity of O(log N). The basic difference between this approach, and classical iterative algorithms, is that different approximations of the system matrix are used in round-robin fashion while one fixed approximation is used in the classical approach. We show that, with proper choice of approximation compositions, the spectral radius of error dynamic is reduced drastically; and with proper decomposition size, the spectral radius will approach to a constant strictly less than one, even if the dimension of the problem tends to infinity. This enables us to devise a parallel algorithm with order one time complexity.