P0-矩阵渐近检验及其计算复杂度降低

∈理论计算机科学电子笔记225（2009）195-200www.elsevier.com/locate/entcs一种渐近检验P0-矩阵李磊1，2法政大学电话：184-8584服部晃哉1法政大学电话：184-8584摘要P-矩阵或P-矩阵问题的一个直接方法是求矩阵的所有主子式A使用标准的数值线性代数技术，计算时间复杂度为O（2nn3P-矩阵问题的计算时间复杂度从O（2nn3）降到O（2n）。递归地应用基于Schur互补的P-矩阵的准则。但该算法不能直接应用于P0-矩阵的检验，因为当出现零对角元时，不能计算Schur补.本文提出了一种计算复杂度为O（2n）的P0数值算例表明，该算法对检验P0-矩阵是有效保留字：P-矩阵，复杂度，主从式，P-矩阵.1引言回想一下，矩阵ARn×n被称为P-矩阵，如果它的所有主子式都是正的，而A被称为P0-矩阵，如果它的所有主子式都是非负的。P-矩阵和P0-矩阵出现在各种数学背景和应用中（参见，例如，Berman和Plemmons [1]）。P-矩阵或P0-矩阵问题，即判定给定矩阵A是否为P-矩阵的问题或P0-矩阵，是重要的，在许多这些应用中，特别是在解决线性互补问题。然而，P-矩阵或P0-矩阵问题1这项工作得到了法政大学研究基金的部分支持。2电子邮件：lilei@hosei.ac.jp1571-0661/Crown版权所有© 2008由Elsevier B. V.出版，CC BY-NC-ND许可证下开放访问。doi：10.1016/j.entcs.2008.12.074196L. Li、K.Hattori/Electronic Notes in Theoretical Computer Science 225（2009）195∈∈∈∈似乎不可避免地具有指数时间复杂度。 正如Coxson [2]所示，P-矩阵或P0-矩阵问题是余NP-完全的。众所周知，在数学规划领域中LCP（A，q）：设A Rn×n和q Rn，找到一个或所有实向量z，满足Az + q ≥ 0，z ≥ 0，z T（Az + q）= 0。（一）事实上，P-矩阵问题可以联系到有限个具有唯一解的测试LCP（A，q）[4]。如果A是P0-矩阵，则LCP（A，q）至少有一个解[7]。一个直接的方法来P-矩阵或P0-矩阵的问题是评估所有的主子式的A使用标准的数值线性代数技术与O（2nn3）计算时间复杂度。 在[3]中，计算时间复杂度- 通过递归地应用一个基于Schur补的P-矩阵判定准则，将P-矩阵问题的复杂度从O（2nn3）降到O（2n但该算法不能直接应用于P0-矩阵的检验，因为当出现零对角元时，不能计算Schur补. 本文提出了一种检验P0-矩阵的渐近方法，即用一个足够小的正数ε代替文献[3]中算法中数值算例表明，方法是检验P0-矩阵的有效方法2.P_0-矩阵的渐近逼近定义2.1设矩阵ARn×n，若其所有主子式都非负，则称A为P0-矩阵.定理2.1[6]设矩阵ARn×n，则下列条件相互等价.(1) A的所有主子式都是非负的。(2) 对任意x∈Rn，x0，存在i，1≤i≤n，满足xi（Ax）i≥0，其中（Ax）i是Ax的第i个元素。(3) 对于A及A的所有主子阵，是非负的。(4) 对所有ε>0，A+εIn是P-矩阵.(5) 对所有正对角矩阵D∈Rn×n，A+D是P-矩阵.(6) 对所有正对角矩阵D∈Rn×n，det（A+D）>0.由定理2.1的条件（1）和（4）可知，只要引入一个足够小的正数ε，就可以用文献[3]中的P-矩阵算法来检验P0-矩阵问题当然，它是一个渐近算法。L. Li、K.Hattori/Electronic Notes in Theoretical Computer Science 225（2009）195197=⎛⎞−⎝⎠−11. a11b对于给定的矩阵A∈Rn×n，我们将A=（aij）分块为以下形式哪里A=c B ，b T=（a12，a13，.， a1n），c T=（a21，a31，...，a n1），一个22一个23a2na32a33.a3nB.......... ......你好。 .an2an 3ann取一个足够小的正数ε，当a11实施方式0，定义Schur com-附件a11 =B1cb T.a11在文献[3]所示的P-矩阵算法P（A）的基础上，用一个小的正数ε代替某些可能的零对角元，很容易得到下面的检验P0-矩阵的P0-矩阵算法。但是当a11=0时，如果我们只是用ε代替a11，那么这个误差ε将影响算法中这一步之后的所有其他操作。 这将有助于提高测试算法。 事实上，通过交换A的一些行和行，（等价于乘以置换矩阵P并考虑矩阵PAPT），我们可以有效地降低这种不必要的精度。考虑下面的简单示例。让A=0.01ε，ε = 0。00011 10001因为det（A）= 10，所以A不是P0-矩阵.<但是如果我们不做任何矩阵变换，从a11= 0，用ε代替a11，我们有a11= ε = 0。0001>0，B = a22=10001> 0，A/a11= B − a−1cb T= 10001 − 10000 × 1 = 1> 0。因此，有可能误解A是一个P0-矩阵.考虑做以下矩阵变换，⎛0 1⎞ ⎛0 1价格0 1€PAPT=01 0⎠ ⎝1 10001⎠⎝1 0⎠198L. Li、K.Hattori/Electronic Notes in Theoretical Computer Science 225（2009）195Bc¯电话：+86-10 -8888888传真：+86-10-88888888=10=A=。L. Li、K.Hattori/Electronic Notes in Theoretical Computer Science 225（2009）19519911≤≤⎜⎝⎟⎠⎜⎟A→∈∈从a<$11=10001>0，B<$=a<$22=0≥0，A<$/a<$11=B<$−a<$−1c<$bT= 0−1×1 ×1 = −1<0，10001可以避免上述错误判断10001基于上述讨论，我们提出了以下算法。P0-矩阵算法P0（A）(1) 输入A=（aij）∈Rn×n，以及一个足够小的正数ε.(2) 如果存在i，1i n，aii0，则输出(3) 如果a11=0，则转到步骤（4），否则转到步骤（5）。(4) 如果存在k，k >1且akk>0，则交换第一行和第k行，第一列和第k列，否则设a11=ε。(5) 呼叫P0（B），呼叫P0（A/a11）。(6) 输出我们给出了一个简单的例子，使用上述P0矩阵算法。让⎜⎛0 11⎞⎟A=−10 1，−1 −21因为a11=0，首先，我们交换第一行和第三行，第一行和第三行，得到⎛1 −2 −1⎞1 0−11 1 0所以零元素集中在对角线的右下方a= 1> 0，B=100−1，A/a=102 000。11⎝1 0⎠11⎝3 1⎠但很容易知道BP0和A/a11P0，因此可以得出A是a的P0-矩阵200L. Li、K.Hattori/Electronic Notes in Theoretical Computer Science 225（2009）195∼⎛⎜⎜ 0BCIBB⎟⎜⎝0⎟⎟⎠∈≤A=⎜⎟⎝⎠∼∈. . .P13数值示例当n=15，20，25，30时，用上述P0使用的计算机环境包括CPU Xeon（TM）、2.40GHz，内存1. 5GB，Windows XPpro和Visual C++6。0. 例3.1和例3.2是P0-矩阵，例3.3和例3.4不是P0-矩阵.测试结果表明，该算法是正确和实用的。 运行时间（秒）如表1所示，其中ε = 0。0001.例3.1上三角矩阵A=（a ij）Rn×n，a ij=k，如果ij，否则a ij=0。其中，k是0到9之间的随机整数。很明显，A是一个P0-矩阵.实施例3.2aa···b b b···c c c···其中a，b，c，. . . 是0到9之间的随机整数 很明显，A是一个P0矩阵实施例3.3⎜⎛0 1· · ··· ·1⎞⎟−1- 是的⎟A=.⎜ ⎟⎜⎝−1⎟⎠其中P∈R（n−1）×（n−1）是P-矩阵。很容易知道A不是P0-矩阵.实施例3.4A=nn其中B R2×2是正矩阵（我们假设n是偶数）。很容易A不是P矩阵L. Li、K.Hattori/Electronic Notes in Theoretical Computer Science 225（2009）195201表1测试P0-矩阵的运行时间（秒）n=15n=20n=25n=30实施例3.10.0110.2015.802189.528实施例3.20.0110.2065.983190.256实施例3.30.0050.1052.98295.172实施例3.4-0.001-0.0014结论本文提出了一种检验P0-矩阵的渐近方法，即用一个足够小的正数ε来代替[3]算法中可能的零对角元。数值算例表明，该方法对检验P0-矩阵是有效和实用的引用[1] A.伯曼河J. Plemmons，Nonnegative Matrices in the Mathematical Sciences，SIAM Press，Philadelphia，1994。[2] G. E. Coxson，P-矩阵问题是co-NP-完全的，数学。Programming，64（1994），pp.173比178[3] M. J. Tsatsomeros和Lei Li，P-矩阵的递归检验，BIT，40（2000），pp.410-414[4] M. M. Kostreva，有限测试集和P-矩阵，Proc.Amer. 数学索科，84（1982），pp.104-105[5] S. Kodama和N.苏田，系统控制中的矩阵理论，仪表与控制工程师学会，东京，1978年。[6] K. Nagasaka和Y.Komaki，Linear Algebra in Sciences and Technologies，SHOKABO Pub.有限公司、Ltd.，东京，1999年。[7] X. Chen和Y.叶，关于P0矩阵LCP的平滑方法，SIAM J.优化，11（2000），pp.341-363.