两分块K－循环Toeplitz矩阵相乘的快速算法

两分块Ｋ－循环Ｔｏｅｐｌｉｔｚ矩阵相乘的快速算法余品能（南京工程兵工程学院）ＡＦＡＳＴＡＬＧＯＲＩＴＨＭＦＯＲＣＯＭＰＵＴＩＮＧＴＨＥＰＲＯＤＵＣＴＳＯＦＢＬＯＣＫＫ－ＣＩＲＣＵＬＡＮＴＴＯＥＰＬＩＴＺＭＡＴＲＩＣＥＳ￥ＹｕＰｉｎｎｅｎｇ（Ｉｎｓｔｉ...     

R-循环分块矩阵求逆的快速傅里叶算法

§１．引言 循环矩阵及循环系统的求解在线性预测、误差控制码、自回归滤波器设计领域内起着重要的作用［１－３］．而循环分块矩阵在计算机时序分析、自回归时序模型波滤中也经常出现 ［４］,文［５］对循环矩阵与循环分块矩阵作了较全面和深刻的研究．对这类矩阵求逆问题的快速算法早就引起了人们的重视［５－７］．本文试图对Ｒ－循环分块矩阵［８］求逆进行研究,提供了一种快速傅里叶算法,其计算复杂性为 Ｏ（ｍｎｌｏｇ２ｍｎ）． §２．引理和算法推导 定义１．具有如下形式的ｎ阶矩阵称为ｒ－循环矩阵,记作ＡＣｉｒｃｒ（ａ０,…     

基于最小冗余线阵的谱相关波达方向估计算法

根据均匀线阵输出的共轭循环相关矩阵具有很大的冗余特性，提出了基于最小冗余线阵的谱相关共轭循环MUSIC算法。该算法利用了信号的时域和空域联合特征，并引入了伪数据矩阵，使算法的性能远优于其他方法。理论分析和计算机仿真实验均表明，与基于最小冗余线阵的共轭循环MUSIC算法相比，该算法具有良好的波这方向估计性能，扩展了阵列孔径，抗噪能力强，分辨率高，能用较少的阵元估计更多的信号源方向。     

稀疏带状矩阵行列式的一类算法

§１．引言 求行列式的算法要比解线性方程组的算法少得多．通常都是用高斯消去法或者其变形（如三角分解等）来计算行列式的值．对于一般矩阵,为了计算的稳定性,还得选全主元或部分主元．设带状矩阵的阶数为ｎ,半带宽为ｍ,则用列主元消去法计算行列式一般需（１～ ２）ｍ２ｎ＋ Ｏ（ｎ）次乘除法和同样多的加减法运算;再加上要选主元,所以机时耗费较多．文［１］提出了用图论的方法来求行列式,但是这种算法当矩阵元素较多时,消耗机时较大．本文提出一种求一类稀疏带状矩阵行列式的算法,它不需选主元,利用矩阵的稀疏性,根据矩阵…     

可重构造的网孔机器上的k-选择

对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵,文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法,其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ）,而对于一般的ｌ元集,文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ,该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地,当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数）,则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．     

用最优通路矩阵实现超立方体多处理机系统的容错路由

针对拓扑结构为超立方体的多处理机系统提出了最优通路矩阵（ＯＰＭ）的概念,并约出了一个基于最优通路矩阵的路由算法。存储于超产方体各节点中的最优通路矩阵记录系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路（长度等于两节点间Ｈａｍｍｉｎｇ距离的通路）。对于ｎ维超方立体,每个节点所需的存储开销为ｎ＾２个字,基于最优通路矩阵的路由算法所选的通路的长度不超过两点间的Ｈａｍｍｉｎｇ距离加２。     

Toeplitz矩阵广义逆的递推算法

研究以奇异的Ｔｏｅｐｌｉｔｚ矩阵ＲＮ为系数矩阵的线性方程组ＲＮＳ＝［ｒ１，ｒ２，…，ｒＮ＋１］Ｔ的递推解法及ＲＮ＋的递推算法。它既能自动识别方程组是相容方程组还是矛盾方程组，还能快速递推计算其最小范数解或最小范效最小二乘解，同时获得ＲＮ＋。     

LogP模型上一类蝶式计算的通信策略

本文研究ＬｏｇＰ模型上一类蝶式计算中的通信问题。以ＦＦＴ的并行计算为例，通过仔细安排消息的发送顺序，使得由有限带宽引起的延迟与局部计算重叠，在ｇ－ｌｏｇｇ＋１≤ｌｏｇｐ（ｐ为处理器数，ｇ为带宽因子）的条件下，只要输入长度ｎ满足最基本的要求（ｎ≥２ｐ＾２），ｇ便被完全隐含于局部计算中，算法时间复杂度可达到最优。最后与文献［１］的结果比较，分析了它们的优缺点及各自的适用范围。     

关于两投影运动估计中E矩阵的刚性分解性质

利用２Ｄ点对应由两透视投影恢复刚体３Ｄ运动和结构的８点线性算法中的本质参数矩阵Ｅ可分解为一个反对称矩阵Ｓ与另一个旋转阵Ｒ的乘积，称此形式的分解为刚性分解．Ｈｕａｎｇ，Ｔ．Ｓ．和Ｆａｕｇｅｒａｓ，Ｏ．Ｄ．得出了３×３矩阵可作刚性分解的一个充要条件．本文证明了３×３矩阵的刚性分解具有对偶性质，即若Ｅ＝ＳＲ≠０，Ｓ＝（Ｓｉｊ）３×３，则Ｅ有且仅有一个对偶的刚性分解Ｅ＝（－Ｓ）Ｒ’，其中和ｒｉ’（ｉ＝１，２，３）分别表示Ｒ和Ｒ’的三个列向量，并给出计算３×３矩阵的两个对偶刚性分解的简单公式；得到了Ｎ×Ｎ（Ｎ≥２）矩阵可作刚性分解的充要条件，并证明矩阵刚性分解的对偶性是Ｎ＝２或３时的特有性质．最后，给出本文结果在运动分析中的应用．     

最短路径树的计算与修改算法

在有向赋权图Ｇ＝（Ｖ，Ｅ，ＣＯＳＴ）上，给出了求解以每个顶点为根的向前／向后最短路径树（ＦＢＳＰＴ）算法。当Ｇ中的边被删除或边权增加时，证明了在这种情况下，不可能存在高效的对ＦＢＳＰＴ的修改算法；而对边添加和边权减少的情况，本文给出时间复杂性为Ｏ（ｎ￣２）的修改算法。此外，本文也讨论了对上述算法的并行实现问题。     

近似三对角Toeplitz方程组的快速分布式并行算法

利用近似三对角Toeplitz矩阵的特殊结构，提出了一种新的求解近似三对角Toeplitz方程组的快速算法．在三对角Toeplitz矩阵的近似LU分解的基础上，利用“分而治之”的思想，并结合秦九韶技术和特殊的数学技巧减少大量的冗余计算，提出了求解近似Toeplitz三对角方程组的快速分布式并行算法，并在理论上证明了算法具有近似于线性的加速比．最后通过数值实验证明，新的并行算法具有较高的并行效率，并且当矩阵阶数n足够大时，算法的加速比趋近于线性加速比．     

Toeplitz矩阵之逆矩阵的新分解式及快速算法

本文利用线性方程组是否有解给出了Toeplitz矩阵可逆的条件,表明Toeplitz矩阵的逆矩阵可以表示为循环矩阵与下三角Toeplitz矩阵的乘积之和,给出了其逆矩阵列的递推公式,得到了求Toeplitz矩阵之逆矩阵的快速算法,计算复杂性为O(n2),一般n阶矩阵求逆的计算复杂性为O(n3).     

分块K—循环Toeplitz矩阵求逆的快速付氏变换算法

本文讨论了分块K－循环Toeplitz系统,导出分块K－循环Toeplitz矩阵求逆的一种快速付氏变换算法,其算法复杂性为O（mnlog2mn）。     

A multicore solution to Block–Toeplitz linear systems of equations

There exist algorithms, also called “fast” algorithms, which exploit the special structure of Toeplitz matrices so that, e.g., allow to solve a linear system of equations in O(n ²) flops. However, some implementations of classical algorithms that do not use this structure (O(n ³) flops) highly reduce the time to solution when several cores are available. That is why it is necessary to work on “fast” algorithms so that they do not lose track of the benefits of new hardware/software. In this work, we propose a new approach to the Generalized Schur Algorithm, a very known algorithm for the solution of Toeplitz systems, to work on a Block–Toeplitz matrix. Our algorithm is based on matrix–matrix multiplications, thus allowing to exploit an efficient implementation of this operation if it exists. Our algorithm also makes use of the thread level parallelism featured by multicores to decrease execution time.     

一类Toeplitz三对角方程组的一种分布式并行算法

文中提出一类Toeplitz三对角方程组的一种分布式并行算法。该算法以系数矩阵的分解为基础,充分利用了系数矩阵结构的特殊性,算法因并行化而引入的冗余计算量非常少,算法的通信机制简单,通信量仅与处理 机台数p有关,与方程组规模n无关,算法具有很高的并行效率,理论分析和数值试验表明,其加速比Sp(n)→p(n→ ∞）,此为线性加速比的理想情况。文中给出了算法在分布存储多计算机系统上的数值试验结果。     

Fast parallel and sequential computations and spectral properties concerning band Toeplitz matrices

We exhibit fast computational methods for the evaluation of the determinant and the characteristic polynomial of a (2k+1)-diagonal Toeplitz matrix with elements in the complex field, either for sequential or for parallel computations. A fast algorithm, to achieve one step of Newton's method, is shown to be suitable to compute the eigenvalues of such a matrix. Bounds to the eigenvalues and necessary and sufficient conditions for positive definiteness, which are easy to check, are given either for matrices with scalar elements or for matrices with blocks. In the case in which the blocks are themselves band Toeplitz matrices such conditions assume a very simple form. Dedicated to Prof. Aldo Ghizzetti on his 75 th birthday     

一类Toeplitz循环三对角方程组的一种分布式并行算法

提出一类Toeplitz循环三对方程组的一种分布式并行算法,在求解由一阶线性双曲型方程（如迁移方程）在一定边界条件下导出的隐式差分方程组时,要重复地求解此类Toeplitz循环三对角方程组。算法基于对系数矩阵的分解,贯彻并行算法设计中“分而治之”的原则,充分利用了系数矩阵结构的特殊性。算法实现中通过秦九韶公式的运用,避免了不必要的冗余计算;理论分析和数值试验表明,算法是数值稳定的,且当方程组规模充分大时,该算法加速比趋近线性加速比的理想情况。给出了算法在某分布存储多计算机系统上的数值试验结果。     

Solving certain queueing problems modelled by toeplitz matrices

By using the concept of generating function associated with a Toeplitz matrix, we analyze existence conditions for the probability invariant vector π of certain stochastic semi-infinite Toeplitz-like matrices. An application to the shortest queue problem is shown. By exploiting the functional formulation given in terms of generating functions, we devise a weakly numerically stable algorithm for computing the probability invariant vector π. The algorithm is divided into three stages. At the first stage the zeros of a complex function are numerically computed by means of an extension of the Aberth method. At the second stage the first k components of π are computed by solving an interpolation problem, where k is a suitable constant associated with the matrix. Finally, at the third stage a triangular Toeplitz system is solved and its solution is refined by applying the power method or any other refinement method based on regular splittings. In the solution of the triangular Toeplitz system and at each step of the refinement method, special FFT-based techniques are applied in order to keep the arithmetic cost within the O(n log n) bound, where n is an upper bound to the number of the computed components. Numerical comparisons with the available algorithms show the effectiveness of our algorithm in a wide set of cases.     

基于Toeplitz矩阵的酉变换波达角估计算法

为提高Toeplitz矩阵重构算法的估计性能、降低计算量,提出了基于Toeplitz矩阵的酉变换DOA估计算法UHT-MUSIC。该算法在保持估计性能不变的前提下,先将Toeplitz型协方差矩阵变换为Hermition矩阵,然后利用酉变换将其转换为实数矩阵。在此基础上利用MUSIC算法进行DOA估计,其特征值分解及谱峰搜索的计算量降低到同条件下TOEP-MUSIC算法的1/4。同时该算法还有效降低了信源的相关系数,从而提高了算法的分辨性能。仿真实验验证了该算法的正确性。     

GPU上循环矩阵的快速求逆算法

循环矩阵是一种特殊类型的Toeplitz矩阵,在很多专业领域尤其是图像和数字信号处理中有广泛的应用。计算其逆矩阵的快速算法由三个步骤组成:(1)使用离散傅立叶变换将矩阵的第一行元素转换到频率空间;(2)计算转换后的频谱中每个幅度的倒数;(3)在调整过的频谱上施加傅立叶反变换,获得逆矩阵的第一行元素,从而构建原始循环矩阵的逆矩阵。此算法的特点是每个数据元素的计算过程完全相同,同时独立于其它元素的计算,因而非常适合在GPU上运行。本文在GPU上实现了上述循环矩阵求逆的快速算法,将其转换为一个正方形的图形绘制。实验结果表明,该算法在GPU上的运行速度比在CPU上提高了大约10倍。