对称张量特征值问题的一种预处理迭代算法

顾传青,李龙

(上海大学理学院,上海 200444)

•快报•

对称张量特征值问题的一种预处理迭代算法

顾传青,李龙

(上海大学理学院,上海 200444)

移位对称高阶幂法(shifted symmetric high order power method,SS-HOPM)是一种求解张量Z-特征值的著名迭代算法.用Newton法对该算法实施初值预条件处理,得到了对称张量特征值问题的一种Newton预条件移位对称高阶幂法(preconditioning SS-HOPM, PSS-HOPM).用两个数值例子验证并得出,与SS-HOPM相比,该算法在几乎不增加计算时间的条件下能计算出更多的特征值.

移位对称高阶幂法;Newton法;Newton预处理方法

最近,张量特征值问题由于与大数据及其应用直接相关[1],在国内外受到了广泛的关注[2-3].张量特征值[4]的定义如下.

定义1假设A是一个m阶n维的实对称张量,则对任何n维向量x,定义

则λ∈R是张量A的一个特征值.如果存在x∈Rn,使得

则向量x是对应的特征向量,(λ,x)称为一个特征对.

定义2定义1的张量Z-特征值问题是由齐利群[5-6]和Lim[7]提出的.特别地,Lim[7]指出任何特征对(λ,x)是一个非线性优化问题的Karush-Kuhn-Tucker(KKT)点,即一个约束的不动点.

1 Newton法和移位对称高阶幂法

1.1 Newton法[8]

为了求解张量特征值问题(2),Newton法将其转化为以下等价的非线性方程组:若(n+1)维向量(x∗,λ∗)为非线性方程组(3)的解,则(x∗,λ∗)为张量A的Z-特征对.

为了利用Newton法解问题(3),假设已知A为m阶n维实对称张量,则F(x,λ)的Jacobian矩阵F′(x,λ)是对称矩阵,其计算公式(证明过程见文献[9])为

算法1Newton法

上述算法是局部收敛的,即只有初始点选在收敛域内才能保证收敛.

1.2 移位对称高阶幂法

Kolda等[10]提出了移位对称高阶幂法(shifted symmetric high order power method,SSHOPM),计算格式如下.

SS-HOPM是改进对称高阶幂法(S-HOPM)后得到的.S-HOPM仅在满足某些特定条件下才会收敛,而SS-HOPM则在S-HOPM基础上添加位移因子α,使得文献[10]中式(4.1)成为凸多项式或者凹多项式,这样便可保证乘幂法的收敛性.

2 对称张量特征值问题的一种Newton预处理迭代算法

结合Newton法和移位对称高阶幂法,本工作提出求解张量特征值问题的一种Newton预处理迭代算法.本算法的基本思想是:首先任意给定一个初始向量,给定一个合适的精度,然后利用Newton法得到一个粗糙的解,最后将该粗糙解作为移位的对称高阶幂法的初始解向量,执行移位对称高阶幂法,直到达到收敛精度.本算法中,利用参数ε1控制Newton法向SS-HOPM转换,ε2为SS-HOPM结束达到的精度.Newton预条件移位对称高阶幂法(preconditioning SS-HOPM,PSS-HOPM)的具体计算格式如式(5)所示,将计算格式xi+1=xi−F−1(xi)f(xi)迭代运算一定次数后得到的xk值作为式(5)的初值x0.

算法2预条件移位对称高阶幂法(PSS-HOPM)

由于本工作给出的PSS-HOPM是先由Newton法对初始向量实施优化,得到的向量再作为SS-HOPM的初始向量,故其收敛性可由下面SS-HOPM的收敛性定理保证.

定理1[10]设A∈R[m,n]是对称张量,且对于α>β(A)(β(A)由文献[10]中定义),算法2产生的迭代序列{λk,xk}满足如下性质:①序列{λk}单调不减,且存在λ∗,使得λk→λ∗;②序列{xk}有一个聚点;③对于每一个聚点x∗,每对{λ∗,x∗}都是张量A的一个特征对;④如果A的特征对为有限个,则存在x∗,使得xk→x∗.

3 数值实验

本工作使用文献[10]给出的两个数值算例来说明预条件移位对称高阶幂法(PSSHOPM)的有效性.考虑A∈R[3,3]和A∈R[4,3]分别为奇数阶和偶数阶的情况,位移α分别取2和1,向量残差的2-范数作为算法的停止准则,计算精度ε1=0.01,ε2=10−6.本工作在文献[10]中的例1.1和例1.2所描述的实验条件下用SS-HOPM和PSS-HOPM分别测试了100次,实验结果如表1和2所示.

表1 由100个随机初始点通过SS-HOPM(凸)计算得到的特征值Table 1 Eigenvalues obtained by SS-HOPM(convex)calculation of 100 random initial points

表2 由100个随机初始点通过PSS-HOPM(凸)计算得到的特征值Table 2 Eigenvalues obtained by PSS-HOPM(convex)calculation of 100 random initial points

从表1和2的数值例子可以看出,本工作给出的PSS-HOPM可以算出比SS-HOPM更多的特征对(λ,x),且所用的时间没有明显的增加,其中SS-HOPM计算两个例子的时间分别为0.315 718和0.197 564 s,PSS-HOPM计算两个例子的时间分别为0.444 903和0.214 983 s.对于奇数阶和偶数阶对称张量的情况,计算出的特征对均增加了6到7个,可见PSS-HOPM对于计算实对称张量Z-特征值的效果非常明显,其中Newton法预条件的计算精度ε1对算法的作用显著.

[1]DIAMOND R.A note on the rotational superposition problem[J].Acta Crystallogr Sect A,1988, 44(2):211-216.

[2]DELATHAuWER L,DEMOOR B,VANDEWALLE J.On the best rank-1 and rank-(R1,R2,…,RN) approximation of higher-order tensors[J].SIAM J Matrix Anal Appl,2000,21(4):1324-1342.

[3]KOFIDIs E,REGALIA P A.On the best rank-1 approximation of higher-order supersymmetric tensors[J].SIAM J Matrix Anal Appl,2002,23(3):863-884.

[4]QI L.Eigenvalues and invariants of tensors[J].J Math Anal Appl,2007,325(2):1363-1377.

[5]QI L.Eigenvalues of a real supersymmetric tensor[J].J Symbolic Comput,2005,40(6):1302-1324.

[6]QI L.Rank and eigenvalues of a supersymmetric tensor,the multivariate homogeneous polynomial and the algebraic hypersurface it defnes[J].Journal of Symbolic Computation,2006, 41(2):1309-1327.

[7]LIM L H.Singular values and eigenvalues of tensors:a variational approach[C]//Proceeding of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing.2005:129-132.

[8]DuPONT T F,SCOTT L R．The power method for tensor eigenproblems and limiting directions of Newton iterates[J].Numerical Linear Algebra with Applications,2013,20(6):956-971.

[9]周会晓,倪勤,曾梅兰.求实对称张量Z-特征值的牛顿法[J].淮北师范大学学报(自然科学版), 2014,35(3):10-12.

[10]KOLDA T G,MAYO J R.Shifted power method for computing tensor eigenpairs[J].Siam J Matrix Anal,2010,32(4):1095-1124.

A preconditioning iterative algorithm for eigenvalue problem of symmetric tensor

GU Chuanqing,LI Long
(College of Sciences,Shanghai University,Shanghai 200444,China)

Shifted symmetric high order power method(SS-HOPM)is a well-known iterative algorithm for solving tensor Z-eigenvalue.In this paper,the Newton method is used to deal with the initial condition of the algorithm.A Newton preconditioning SS-HOPM (PSS-HOPM)for the symmetric tensor eigenvalue problem is obtained.Two numerical examples are used to illustrate that,compared with the SS-HOPM algorithm,this algorithm can calculate more eigenvalues with little increase of computation time.

shifted symmetric high order power method(SS-HOPM);Newton method; Newton preconditioned method

O 241

A

1007-2861(2017)01-0068-05

10.3969/j.issn.1007-2861.2016.07.009

2016-12-05

国家自然科学基金资助项目(11371243);上海市教委创新基金资助项目(13ZZ068);上海市重点学科建设资助项目(S30104)

顾传青(1955—),男,教授,博士生导师,博士,研究方向为数值逼近、数值代数及其应用. E-mail:cqgu@shu.edu.cn