The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond
The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond
复制标题
DOI：
10.1007/s11075-008-9253-0
复制
发表时间：
2008-11
影响因子：
2.1
通讯作者：
Dario Bini;B. Meini
中科院分区：
文献类型：
--
作者：
Dario Bini;B. Meini
循环约简是G. H. Golub和R. W. Hockney在20世纪60年代中期发明的一种算法，用于求解与矩形泊松方程的有限差分离散化有关的线性系统。在Gene Golub的算法中，它是有史以来最通用和最强大的算法之一。近年来，它已被应用于解决不同领域的不同问题。本文综述了循环约简的主要特征，将其与解析函数的性质联系起来，回顾了它在求解更一般的有限和无限线性系统以及各种非线性矩阵方程（包括代数Riccati方程）中的推广，并在马尔可夫链、排队模型和输运理论中的应用。在很弱的假设条件下，证明了循环约简收敛性及其适用性的一些新结果。给出了克服击穿的新公式。
Cyclic reduction is an algorithm invented by G. H. Golub and R. W. Hockney in the mid 1960s for solving linear systems related to the finite differences discretization of the Poisson equation over a rectangle. Among the algorithms of Gene Golub, it is one of the most versatile and powerful ever created. Recently, it has been applied to solve different problems from different applicative areas. In this paper we survey the main features of cyclic reduction, relate it to properties of analytic functions, recall its extension to solving more general finite and infinite linear systems, and different kinds of nonlinear matrix equations, including algebraic Riccati equations, with applications to Markov chains, queueing models and transport theory. Some new results concerning the convergence properties of cyclic reduction and its applicability are proved under very weak assumptions. New formulae for overcoming breakdown are provided.