Sequential and Parallel Algorithms for the Inverse Toeplitz Singular Value Problem
Sequential and Parallel Algorithms for the Inverse Toeplitz Singular Value Problem
复制标题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
P. Alonso;G. Becerra;A. Vidal
中科院分区：
文献类型：
--
作者：
P. Alonso;G. Becerra;A. Vidal
当逆加法奇异值问题（IASVP）涉及Toeplitz型矩阵时，可以利用这种特殊的结构来减少执行时间。本文提出了两种局部和全局收敛的迭代算法（MIIIT和LPT），有效地解决了矩阵为Toeplitz时的IASVP（IASVPT）。正如将要证明的那样，它可以实现比那些不利用Toeplitz类结构的算法低一个数量级的渐进复杂度。此外，我们已经实现了这两种算法的并行版本，称为PMIIIT和PLPT，分别大大减少了执行时间的顺序算法在视线的实验。关键词-并行程序设计，奇异值反问题，Toeplitz矩阵，牛顿型方法，最小二乘问题
When the Inverse Additive Singular Value Problem (IASVP) involves Toeplitz–type matrices it is possible to exploit this special structure to reduce the execution time. In this paper, we present two iterative local and global convergent algorithms (MIIIT and LPT) to solve efficiently the IASVP when the matrix is Toeplitz (IASVPT). As it will be shown, it can be achieved an asymptotic complexity one order of magnitude less than those algorithms that do not exploit the Toeplitz–like structure. Furthermore, we have implemented a parallel version of these both algorithms, called PMIIIT and PLPT, respectively, that highly reduce the execution time of the sequential algorithm at sight of the experiments. Keywords– Parallel programming, Inverse Singular Value Problem, Toeplitz matrices, Newton type methods, Least squares problem