USING ZOLOTAREV ’ S RATIONAL APPROXIMATION FOR COMPUTING THE POLAR , SYMMETRIC EIGENVALUE , AND SINGULAR VALUE DECOMPOSITIONS
USING ZOLOTAREV ’ S RATIONAL APPROXIMATION FOR COMPUTING THE POLAR , SYMMETRIC EIGENVALUE , AND SINGULAR VALUE DECOMPOSITIONS
复制标题
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
R. Freund
中科院分区：
文献类型：
--
作者：
R. Freund
极分解A=UPH有着广泛的应用，它是计算对称特征值分解和奇异值分解的基本工具。考虑到计算机体系结构的最新趋势，这些分解的传统算法是次优的，这需要最大限度地减少通信和算术成本。频谱分治算法递归地将问题分解为两个较小的子问题，可以同时满足这两个要求。对于计算极分解，比例牛顿迭代和QDWH迭代是最流行的两种算法，因为它们是向后稳定的，分别在最多9次和6次迭代中收敛。在这一框架下，本文发展了极分解的QDWH迭代的高阶变种。该算法的核心思想来源于逼近理论：我们对1877年Zolotarev提出的标量符号函数使用最佳有理逼近。该算法利用符号函数所具有的特殊性质，通过适当组合低次Zolotarev函数即可得到高次Zolotarev函数(最佳有理逼近)。这使得算法在双精度算法中只需两次迭代就能收敛，惊人的收敛速度为17%。得到的对称特征值和奇异值分解算法比基于QDWH的算法具有更高的运算量，但更适合于并行计算，并表现出良好的数值后向稳定性。
The polar decomposition A = UpH finds many uses in applications, and it is a fundamental tool for computing the symmetric eigenvalue decomposition and the singular value decomposition via a spectral divide-and-conquer process. Conventional algorithms for these decompositions are suboptimal in view of recent trends in computer architectures, which require minimizing communication together with arithmetic costs. Spectral divide-and-conquer algorithms, which recursively decouple the problem into two smaller subproblems, can achieve both requirements. For computing the polar decomposition, the scaled Newton and QDWH iterations are two of the most popular algorithms, as they are backward stable and converge in at most nine and six iterations, respectively. Following this framework, in this paper, we develop a higher-order variant of the QDWH iteration for the polar decomposition. The key idea of this algorithm comes from approximation theory: we use the best rational approximant for the scalar sign function due to Zolotarev in 1877. The algorithm exploits the extraordinary property enjoyed by the sign function that a high-degree Zolotarev function (best rational approximant) can be obtained by appropriately composing low-degree Zolotarev functions. This lets the algorithm converge in just two iterations in double-precision arithmetic, with the whopping rate of convergence seventeen. The resulting algorithms for the symmetric eigenvalue and singular value decompositions have higher arithmetic costs than the QDWH-based algorithms, but are better-suited for parallel computing and exhibit excellent numerical backward stability.