网站地图 | 联系我们 | English | 意见反馈 | 主任信箱
 
首页 中心概况 新闻动态 科研进展 交流合作 人才培养 研究队伍 人才招聘 政策规章 数学交叉科学传播
科研进展
科研成果
研究专题
获奖
现在位置:首页 > 科研进展 > 科研成果
线性特征值问题的优化算法
【打印】【关闭】

2014-12-30 | 编辑:文\材料环境部

材料计算中的基于密度泛函理论的电子结构计算、非线性特征问题等一些重要算法需要在每个迭代步求解一个大规模矩阵的部分特征值分解(也即计算目标矩阵多个最大或最小的特征对);大数据处理中的一些重要数学模型,如高维数据降维、矩阵的低秩逼近、协方差矩阵估计等问题的优化求解算法都会涉及到计算一系列大规模矩阵的奇异值分解,其本质也是部分特征值分解。在求解上面提到的这些科学及工程领域中的数学问题的整体算法中,部分特征值分解往往占据了其主要计算量。也就是说现有的部分特征值分解算法已经制约了这些数学模型在更高规模应用问题中的适用性;另一方面,部分特征值分解计算效率的提升能够带来对上述问题中整体算法效率的改进。

材料环境部刘歆等设计了一种块Krylov子空间方法。区别于经典的特征值分解算法,这种新方法是一种以矩阵为变量的块迭代算法,因此有更好的可扩展性。新算法LMSVD实现了完全自适应的子空间选取方法,并且克服了一般子空间方法在迭代后期子空间条件数逐渐变差的问题。数值实验表明,LMSVD算法与著名的ARPACK和PROPACK软件包中的相关算法,以及同样是基于优化模型的LOBPCG算法相比更高效而稳定。

他们还提出了一种完全不同于已有的收敛性结果的理论分析方法,第一次通过分析正交约束下迹极大化模型的充分上升性建立了一套以矩阵为变量含有正交约束的极大化问题的子空间算法的收敛性理论。这套理论不但可以保证我们新方法的全局收敛性,还解决了LOBPCG悬而未决的全局收敛性,并且对其它非线性目标正交约束的矩阵优化模型的收敛性证明也有重要的参考价值。该工作已经于2013年发表(X. Liu, W. Wen and Y. Zhang, Limited memory block Krylov subspace optimization for computing dominant singular value Decompositions, SIAM Journal on Scientific Computing, 35-3 (2013), A1641-A1668.)。LMSVD的算法源代码自2012年3月在网上公布后已经有八百多次的下载,2014年6月起LMSVD的源代码可以在Mathworks公司(MATLAB的开发公司)的官方平台上公开下载。

针对需求特征对个数较多的情形下,正交化过程的计算代价逐渐取代矩阵向量乘法变成制约部分特征值分解算法效率的新的计算瓶颈,他们还设计了两种无正交约束的新模型,分析了新模型和传统的迹最优化模型的等价性,并设计了相应的梯度算法EIGPEN和高斯牛顿算法SLRPGN。其中EIGPEN还实现了并行化,应用在电子结构计算中,计算效率和并行效率都大大超过了已有算法。SLRPGN实现了无参数化,也就是不用调节任何算法参数,包括步长因子,只需在一个易计算的高斯牛顿方向上使用固定的1步长,即可有非常稳定高效的数值表现,并且他们还对SLRPGN给出了独特的收敛性分析。

图1:三种算法的并行化效率(2-24核),红色柱为整体效率. Andrews和Ga3As3H12都是来自电子结构计算的目标矩阵,大小分别是60000X60000和61349X61349,这里都要求600个最小特征对。

图2:四种算法在计算两类稀疏主成分分析中的部分奇异值分解时的表现。

欢迎访问国家数学与交叉科学中心 
地址:北京海淀区中关村东路55号 邮编:100190 电话: 86-10-62613242 Fax: 86-10-62616840 邮箱: ncmis@amss.ac.cn