大型M-矩阵Sylvester方程的分而治之方法

Divide-and-Conquer Method for Large-Scale M-Matrix Sylvester Equation

本文研究了大型M-矩阵Sylvester方程(MSE)的数值方法。利用分而治之的思想,将大型矩阵方程分解为低阶矩阵方程和低秩矩阵方程分别求解,利用递归将两部分的解胶合成原问题的解。证明了递归层对应的低阶矩阵方程和低秩矩阵方程都是M-矩阵Sylvester方程。利用MSE的保结构加倍算法分别求解低阶和低秩MSE问题,从而提高了求解原MSE问题的速度。数值实验结果表明,本文提出的分而治之方法对求解大型M-矩阵Sylvester方程是有效的。

In this paper,we consider the numerical methods for large-scale M-matrix Sylvester equation(MSE).Based on the idea of divide-and-conquer method,the large-scale matrix equation is split into low-order matrix equations and low-rank matrix equations,and the solutions of the two parts are recurriely combined into the solutions of the original MSE problem.It is proved that the low-order matrix equations and the low-rank matrix equations corresponding to the recursive layers are M-matrix Sylvester equations.The speed of solving original MSE is accelerated by using the structure-preserving doubling algorithms to solve low-order and low-rank MSEs.Numerical experiments show that the divide-and-conquer method is effective for solving large-scale M-matrix Sylvester equations.