An Algorithm for the Generalized Singular Value Decomposition on Massively Parallel Computers

A new algorithm for computing the generalized singular value decomposition that diagonalizes two matrices is introduced. First, two existing algorithms are studied, one due to Paige and the other to Han and Veselic. The former requires only orthogonal plane transformations, resulting in two matrices with parallel rows. The latter employs nonsingular (not necessarily orthogonal) transformations to directly diagonalize the two data matrices. For many applications, it is preferable to be given both the diagonal matrices and the transformation matrices explicitly. Our algorithm has the advantages that the nonsingular transformation is readily available, computation of transformations is simple, and the convergence test is efficient in a parallel computing environment. We present implementation results, obtained on a Connection Machine 2, to compare our new algorithm with that of Paige.     

一种最小二乘／奇异值分解算法

针对预失真技术中存在记忆非线性放大器预失真的问题,分析数字预失真器的结构和常用预失真器的识别算法,对经典最小二乘／奇异值分解（LS／SVD）算法进行改进,以较少资源获得较高性能。仿真结果表明,改进的LS／SVD算法能实现记忆非线性放大器的快速、高效线性化,提高记忆非线性放大器的性能。     

基于奇异值分解的固定区间平滑新方法*

本文提出一种基于奇异值分解（ＳＶＤ）的固定区间平滑新方法，该方法基于Ｒａｕｃｈ－Ｔｕｎｇ－Ｓｔｒｉｅｂｅｌ固定区间平滑方法，利用奇异值分解作为计算工具，将原算法中协方差阵进行奇异值分解，不仅具有很好的数值稳定性和鲁棒性，而且避免了矩阵的求逆，此外，采用ＳＶＤ分解，具有明显的物理意义。仿真计算结果证明了本文方法的有效性和优越性。     

Parallel Approaches for Singular Value Decomposition as Applied to Robotic Manipulator Jacobians

The system of equations that govern kinematically redundant robotic manipulators is commonly solved by finding the singular value decomposition (SVD) of the corresponding Jacobian matrix. This can require a considerable amount of time to compute, thus a parallel SVD algorithm reducing execution time is sought. The approach employed here lends itself to parallelization by using Givens rotations and information from previous decompositions. The key contribution of this research is the presentation and implementation of parallel SVD algorithms to compute the SVD for a set of Jacobians that represent various different joint failure scenarios. Results from implementation of the algorithm on a MasPar MP-1, an IBM SP2, and the PASM prototype parallel computers are compared. Specific issues considered for each implementation include: how data is mapped to the processing elements, the effect that increasing the number of processing elements has on execution time, the type of parallel architecture used, and trade-offs between modes of parallelism.     

一种基于模糊聚类和奇异值分解的水印算法

提出一种新的基于模糊聚类和奇异值分解的水印算法.利用人类视觉系统(HVS)的掩蔽效应,在载体图像空域进行模糊聚类(FCM)寻找图像纹理复杂的子区域来作为嵌入水印的位置,再用奇异值分解(SVD)实现水印的嵌入.实验表明,该算法有效地平衡了水印的鲁棒性和视觉上的不可见性之间的矛盾.     

Cholesky分解细粒度并行算法

本文提出了一种Cholesky分解细粒度流水线并行算法,该算法可以处理任意规模的数据,可以充分开发FP-GA加速器提供的细粒度并行。实验表明,该算法具有很好的可扩展性,在Xilinx XC5 VLX330 FPGA上能够集成36个处理单元(PE),当矩阵的阶为16384、运行频率为200MHz时性能达到14.3GFLOPS。     

一种基于奇异值分解的图像匹配算法

图像匹配技术在计算机视觉、遥感和医学图像分析等领域有着广泛的应用背景.针对传统的相关匹配算法计算量大、对图像旋转敏感等问题,提出一种新的基于奇异值分解的图像匹配算法.首先在待匹配图像中分别提取带主方向的角点作为特征点,通过计算特征点间经旋转补偿的归一化互相关值建立特征点相似度矩阵,然后利用奇异值分解算法生成特征点匹配矩阵并获得特征点间的一一对应关系.在复杂自然图像上的实验结果表明,算法能够匹配任意角度旋转的图像,对局部遮挡、光照变化、随机噪声等具有较强的健壮性,并具有较快的计算速度和较高的匹配精度.此外,该算法易于和其他匹配技术进行融合并获得性能提升,其与SIFT描述子结合的匹配实验结果表明,该算法具有良好的扩展性和实用性.     

基于奇异值分解的三维网格模型零水印算法

研究版权保护问题,针对传统水印嵌入算法为避免模型失真,只能降低水印嵌入强度,但会造成水印鲁棒性下降,采用零水印方法则可以有效的解决水印透明性和鲁棒性之间的矛盾问题,提出了一种基于奇异值分解的三维网格模型零水印算法.不对模型数据进行任何改动,将模型按拓扑数据分割为若干子块,在各子块内进行奇异值分解,提取奇异值向量的前若干项,作为图像特征,进行零水印构造.实验结果表明,算法可避免模型失真,构造的水印可以抵抗多种常见的攻击手段.在提取水印时无需原始网格模型参与,模型具有较好的鲁棒性,并为设计提供科学依据.     

基于奇异值分解的量化水印盲检算法

提出了一种基于奇异值分解的量化水印盲检算法.利用图像矩阵的奇异值稳定性好且最大奇异值远远大于其他奇异值的特点,首先时分块图像最大奇异值进行量化,再结合其奇偶性将二值水印嵌入量化后的奇异值中.实验结果表明,水印算法在满足较好的不可见性和较强的鲁棒性的同时;还可实现水印的盲提取.     

基于奇异值分解的二维码加密算法

随着移动互联网和智能手机的快速发展,人们对网络中信息传输的安全性的要求越来越高。二维码作为一种存储和识别信息的技术已经在很多领域有着广泛的应用。但是二维码编码算法是公开的且未实现信息加密,在一些领域中存在信息安全问题。文中通过研究二维码编码规则及加密算法,提出一种基于奇异值分解的改进算法来对编码数据信息加密。通常,计算机存储数字化的图像文件是通过矩阵的方式,因此,图像对应的坐标像素的值都可以用矩阵的元素表示,计算机对数字图像的处理过程就是对这些非负矩阵进行运算。解密是加密的逆过程,即对图片矩阵进行奇异值分解加密,以及加密解出明文信息。实验证明,所提方法加、解密的效率高,安全性好。     

矩阵奇异值分解在计算技术中的应用

奇异值是矩阵的一个良好特征。本文通过对矩阵奇异值分解的分析，对计算机图像压缩和数字水印技术方面的应用方法进行了描述，同时提供了部分应用例子。     

采用奇异值分解设计广义系统的最优滤波器

本文讨论广义离散随机线性系统的状态估计问题，通过矩阵奇值分解，本文给出了一种设计降阶最优滤波器的实用方法，该方法同时还得到了动态系统和量测系统的干扰噪声的估计。     

融合信任传播和奇异值分解的社会化推荐算法

针对用户信任矩阵中的数据稀疏问题,设计用户信任关系的传播规则,根据该规则计算用户之间的信任度,填充用户信任矩阵。在此基础上,结合用户信任传播算法和奇异值分解模型,提出一种社会化推荐算法,将用户评分矩阵与信任关系矩阵相结合,提高推荐系统的预测准确率。在Epinions和Filmtrust公开数据集上的实验结果表明,该算法相比传统推荐算法具有更高的推荐质量。     

一种基于奇异值分解的改进图像水印算法

数字水印作为一种新型的信息隐藏技术而成为目前业界研究的热点。本文提出了一种基于奇异值分解的图像水印改进算法。该改进算法具有如下特点：（1）在水印嵌入时,对原始图像以块为单位进行奇异值分解,在得到的奇异值中直接嵌入水印;（2）在水印提取时,不需要原始图像数据或原始水印数据。改进后的算法更加简便、快捷。实验
表明,与DCT算法相比较,本文所提出的方法在抵抗各种常规数据处理和攻击（如高斯噪声、JPEG压缩、滤波、裁剪等）方面具有良好的性能。     

A Parallel Algorithm for Computing Polygon Set Operations

We present a parallel algorithm for performing boolean set operations on generalized polygons that have holes in them. The intersection algorithm has a processor complexity of O(m²n²) processors and a time complexity of O(max(2log m, log²n)), where m is the maximum number of vertices in any loop of a polygon, and n is the maximum number of loops per polygon. The union and difference algorithms have a processor complexity of O(m²n²) and time complexity of O(log m) and O(2log m, log n) respectively. The algorithm is based on the EREW PRAM model. The algorithm tries to minimize the intersection point computations by intersecting only a subset of loops of the polygons, taking advantage of the topological structure of the two polygons. We believe this will result in better performance on the average as compared to the worst case. Though all the algorithms presented here are deterministic, randomized algorithms such as sample sort can be used for the sorting subcomponent of the algorithms to obtain fast practical implementations.     

有向图并行计算中一种新的结点调度算法

在基于有向图的并行计算中,给定图剖分后,如何设计结点调度方案使得并行执行时间最短,是典型的NP完全问题.针对此问题,文中提出一种新的基于顺逆交替迭代技术的启发式调度算法,并给出该算法的并行实现.严格的理论推导证明,新算法在一定的假设条件下,从任何初始调度方案出发,均可以单调收敛.在数百个处理器上的并行数值实验表明,与常用的调度算法相比,新算法可在付出很少的开销代价下显著提高整体并行效率.     

基于加权矩阵的多维广义特征值并行分解算法

针对串行广义特征值分解算法实时性差的缺点, 提出基于加权矩阵的多维广义特征值分解算法. 与串行算法不同, 所提算法能够在一次迭代过程中并行地估计出多维广义特征向量. 平稳点分析表明: 当且仅当算法中状态矩阵等于所需的广义特征向量时, 算法达到收敛状态. 通过对比相邻时刻的状态矩阵模值证明了所提算法的自稳定特性. 所提算法参数选取简单, 实际实施较为容易. 数值仿真和实例应用进一步验证了算法的并行性、自稳定性和实用性.     

基于LU分解和交替最小二乘法的分布式奇异值分解推荐算法

针对当前分布式潜在因子推荐算法存在时间复杂度较高、运行时间较长的问题,文中提出基于LU分解和交替最小二乘法(ALS)的分布式奇异值分解推荐算法,利用ALS利于分布式求解目标函数的特点,提出网格状分布式粒度分割策略,获取相互独立不相关的特征向量.在更新特征矩阵时,使用LU分解求逆矩阵,加快算法的运行速度.在KDD CUP 2012 Track1中的腾讯微博数据集上的实验表明,文中算法在确保一定推荐精度的前提下,大幅提升推荐速度和算法效率.