三角Stein方程的systolic算法

A Systolic Algorithm for the Triangular Stein Equation

提出一种新的ｓｙｓｔｏｌｉｃ实现方法计算三角Ｓｔｅｉｎ方程．可将原复杂性为Ｏ（ｍ２ｎ２）的串行算法在处理器为Ｏ（ｍ２）的ｓｙｓｔｏｌｉｃ阵列上并行计算，时间复杂性降为Ｏ（ｍｎ），而处理器具有很高的利用率．利用文中给出的方法，可以并行求解一大类最优控制中有关矩阵运算的问题，如Ｌｙａｐｕｎｏｖ方程。

A new method of systolic implementation for the triangular Stein equation is presented in this paper. The original sequential algorithm with O(m 2n 2 ) complexity can be pa rallelly solved on a systolic array of O(m 2) processors. The time complexity becomes down to O(mn) and the utilization efficiency of processors is very high. The method can be used to solve a wide class of parallel optimal control problems concerning matrix computation, such as Lyapunov equation and Sylvester equation.