A nonstandard cyclic reduction method, its variants and stability

A nonstandard cyclic reduction method is introduced for solving the Poisson equation in rectangular domains. Different ways of solving the arising red uced systems are considered. The partial solution approach leads to the so- called partial solution variant of the cyclic reduction (PSCR) method, whil e the other variants are obtained by using the matrix rational polynomial f actorization technique, including the partial fraction expansions, the fast Fourier transform (FFT) approach, and the combination of Fourier analysis and cyclic reduction (FACR) techniques. Such techniques have originally bee n considered in the standard cyclic reduction framework. The equivalence of the partial solution and the partial fraction techniques is shown. The com putational cost of the considered variants is O (N log N) operations, excep t for the FACR techniques for which it is O (N log log N). The stability es timate for the considered method is constructed, and the stability is demon strated by numerical experiments.