边界约束凸二次规划问题的予校正内点法

51．引言本文考虑如下凸二次规划的极小化问题：其中HE＊”””是对称正定（或正半定）矩阵，b入。是＊”中的常数向量，以n一切EB”：匕x三…表示问题（1．1）的可行域．这类问题出现在许多应用领域，如最优控制、工程设计、数值天气预报、边界约束的最小二乘问题及计算具有边界约束非线性规划的于问题的极值等．问题（1．1）是不等式约束凸二次规划的较简单形式，很自然是应用积极集法求解问题（1扑，即需要求解一系列如下形式的干问题：其中Wb是所有积极约束（变量取上或下界值）的下标集合．假设d‘是问题（1．到的。解，Ah是相应的…     

广义特征值问题的多处理机算法

本文给出直接求解广义实对称三对角阵特征值问题Ax=λBx(其中A为对称三对角阵,B为对称正定三对角阵)的多处理机算法。它是对[1]中TREPS1及TREPS2的扩充。类似于EISPACK中的BISECT及TINVIT的计算步骤:分离、紧缩、逆迭代、部分正交化,不过每步均是在推广的意义上进行的。对一个给定区间,使用多分法来分离特征值,使用二分法和Zeroin法来紧缩这些分离的特征值,相应特征向量应用广义逆迭代法可以求得,修正的Gram—Schmidt方法用于正交化向量组。     

离散H∞滤波系统最优范数计算的特征值算法

基于Riccati方程解的存在条件，建立了离散系统H∞江波问题的最优范数γopt与相关的Hamiltonian差分方程一阶特征值，以及矩阵广义特征值问题一阶特征值之间的对应关系，根据这一关系可以用求解特征值问题的算法计算最优H∞范数，由于仅需计算一阶特征值，所以可用扩展Wittrick-Williams算法求解这一问题。     

基于特征分组与特征值最优化的距离度量学习方法

主流的距离度量学习方法都需要求解半正定规划（Semi definite programming, SDP ）问题,而其中每次循环迭代中的矩阵完全 特征分解运算使得现有方法计算复杂度很高,实用性不强,难以应用在大规模数据环境。 本文提出了一种基于特征分组与特征值最优化的距离度量学习方法。引入特征分 组算法,根据特征各维数之间相关性对图像底层特征进行分组。在一定的约束条件下 ,将求解SDP问题转化为特征值最优化问题,在每次循 环迭代中只需计算矩阵最大特征值对应的特征向量。实验结果表明该方法能有效地降低计算 复杂度,减少度量矩阵的学习时间,并且能取得较好的分类结果。     

计算实对称矩阵广义特征值问题的并行算法

矩阵广义特征值问题是科学计算与工程应用中的一个重要的研究课题。文章探讨了近年来计算对称矩阵广义特征值问题的并行算法,并着重介绍了二分法、分治算法、同伦连续法和迭代算法。     

解高阶Hermitian矩阵特征值问题的并行块消去迭代法

§1．引言在现代计算物理、计算化学、计算生物以及许多科学研究与工程计算中都涉及很高阶的Hermitian矩阵特征值问题．对这个问题已有许多的研究成果和计算方法，但是现有的方法或者是不能并行执行或者是仅能计算少量的特征值．对于很高阶的矩阵，要求不是太少量的特征值的问题还没有一个好的并行算法．本文工作的目的是给出一个粗粒度的并行算法，能充分利用高性能大规模分布式存贮的并行计算机巨大潜力解决实际应用的计算问题．本文给出的并行分块消去迭代法把在单处理器上串行求解矩阵特征值问题的解算器看作“黑盒子”来使用，解算器…     

离散H∞滤波系统最优范数计算的特征值算法

基于Riccati方程解的存在条件,建立了离散系统H_∞滤波问题的最优范数γopt与相关的Hamiltonian差分方程一阶特征值,以及矩阵广义特征值问题一阶特征值之间的对应关系.根据这一关系可以用求解特征值问题的算法计算最优H_∞范数.由于仅需计算一阶特征值,所以可用扩展Wittrick-Williams算法求解这一问题.     

矩阵平衡及策略

矩阵平衡是一般矩阵求解特征值问题的一个重要处理过程。它不仅可以提高求解的全程效率,而且可以改善计算结果的精度。本文论述了矩阵平衡的算法结构及实施策略,并对其充要条件给予证明。该算法在YH-2 EISPACK中得以应用。     

高阶Sylvester矩阵方程的解析通解

给出了矩阵方程Am1 VJm1+…+A1VJ+A0V=Bm2 WJm2+…+B1WJ+BoW的3种完全解析参数通解.这些解由一组参数向量给出,这些参数向量提供了问题的全部自由度.求解算法不要求矩阵J具有不同的特征值,或者和A(s)的特征值不同.这些通解仅包含数值矩阵计算,为工程应用计算提供了方便.算例说明本文所给方程通...     

通过符号计算准确实现矩阵的Lanczos过程

通过相似变换化矩阵Ａ为三对角线矩阵Ｌ的过程（方法）称为Ｌａｎｃｚｏｓ过程（方法）【‘」．由此得到的等式ＡＴ—ＴＬ或Ｔ－‘ＡＴ—Ｌ称为矩阵Ａ的Ｌａｎｃｚｏｓ分解．这里Ｔ是某个已知的变换矩阵．在等式＊－‘＊Ｔ—Ｌ中除要求Ｔ已知外还要求＊－‘也是己知的．本文首先阐明通过符号计算准确实现矩阵Ｌａｎｃｚｏｓ分解＊－‘＊Ｔ一Ｌ的理论根据,然后给出准确的Ｌａｎｃｚｏｓ过程在求矩阵的不变因子与解矩阵方程ＡＸ—ＸＢ＝Ｃ中的应用．引．矩阵的Ｌａｎｃｚｏｓ分解设ＡＥ＊”””,（ｘｌ,…,１一表不由向量１１,··,１。…     

无穷扇形区域调和边值问题的重叠型区域分解法

51．引言边界元方法在力学和科学工程计算中有着广泛的应用问．它特别适合求解无界区域上的问题［‘’，‘’1．边界元和有限元耦合［‘，＼以及作适当的人工边界处理后再在有界区域上应用有限元技术＊＼都是处理无界区域问题时常用的方法．另一方面，近年发展起来的区域分解法不仅为并行计算提供了有效手段＊’］，也为边界元方法在无界区域问题上的应用提供了新的途径．其中，无界区域上基于自然边界归化的重叠型和不重叠型区域分解算法＊’，“－‘’］，同时具备了边界元法和区域分解法的优点．它将无界区域n分解为一个很小的有界区域01…     

用Lanczos方法解高阶稀疏矩阵广义特征值问题的某些经验

考虑n阶实对称矩阵偶K,M的广义特征值问题 Ky=ω~2My,(0.1)其中K是非负半定阵,M为对称正定矩阵。问题(0.1)的特征值分布为:0≤ω_1~2≤ω_2~2≤…≤ω_n~2。通常需要求解(0.1)的前k个特征解,即ω_1~2,ω_2~2,…,ω_k~2及其对应的特征向量     

求解实对称带状矩阵特征值问题的一种分治算法

gi．引言考虑矩阵特征值问题AX二AX，其中A是半带宽为则1＜，＜＜。）的。Xu实对称带状矩阵，表示如下：即a；j二民当k－j＞，求解上述问题的经典算法是：先用稳定的正交变换（Householder变换或Gi、us变换）将带状矩阵三对角化，然后，用QR算法求对称三对角矩阵的特征对．经典算法的缺点是并行实现困难，尤其是分布式并行机上难度更大．文＊3］提出的同伦分治算法速度快，并行效率高，但它仅适合对称三对角矩阵．本文推广K3］的结果，提出求解实对称带状矩阵特征值问题的一种同伦分治算法．92．算法的理论背景把矩阵A划分如下：其中A…     

有限元特征值计算中的子空间二次解耦算法

解线性方程组预条件子算法已在求解偏微分方程(PDE)的离散代数系统的高性能计算中取得巨大成功.相比之下,PDE特征值问题本身的高效快速并行的潜力目前远未发挥.根据代数基本定理可知,通过因式分解,任意一个一元n次实特征多项式可分解为若干个低次实多项式(如二次)或一次实多项式的乘积,因此,利用PDE方程的特征变换(如Fourier变换等)作预变换有可能把离散的高阶广义特征值问题直接解耦分解为一批低阶广义矩阵特征值的并行计算.本文以三次Hermite插值有限元为例,提出求解一类离散椭圆PDE广义特征值的二次解耦算法。新算法不但降低了常规算法(先把广义特征值问题化为普通特征值问题,再分解为n个一次多项式乘积)的计算复杂度,性能提升明显,而且能有效判别与防止伪特征值的出现(Spurious free无伪解).     

解实对称矩阵特征值问题的并行算法

51．二分／多分法二分／多分法（BS／MS）是当前最常用的解实对称矩阵特征值问题的并行算法．这个算法也可解Hermitian矩阵的特征值问题、实对称矩阵和Hermitain矩阵的广义特征值问题，更适用于解实对称三对角线矩阵特征值问题．丑．1实对称三对角经矩阵特征值问题假设实对称三对角线矩阵T为T的A矩阵T－Al的各级前生子式p朴），i二01，2，…，。可用三项递推公式产生其中见由一det（T－Al）．序列只（A），i一01，…，n具有Sturm序列性质；即序列的相邻项符号不同数等于T的小于人的特征值个数．在实际计算时，因为只（A）容易上、下…     

基于原型超平面的多类最接近支持向量机

基于广义特征值的最接近支持向量机（proximal support vector machine via generalized eigenvalues,GEPSVM）摒弃了传统意义下支持向量机典型平面的平行约束,代之以通过优化使每类原型平面尽可能接近本类样本,同时尽可能远离它类样本的准则来解析获得原型平面;从而避免了SVM的二次规划,其分类性能达到甚至超过了SVM．但GEPSVM仍存在如下不足：①仅对两分类问题而提出,无法直接求解多分类问题;②存在正则化因子的选择问题;③求解原型平面的广义特征值问题中所涉及的矩阵一般仅为半正定,容易导致奇异性问题．通过定义新的准则,构建了一个能直接求解多个原型超平面的多分类方法,称之为基于原型超平面的多类最接近支持向量机,较之GEPSVM,该方法优势在于：①无正则化因子选择的困扰;②可同时求解多个超平面,对两分类问题,分类性能达到甚至优于GEPSVM;③超平面的选择问题转化为简单特征值而非广义特征值求解问题;④原型平面的选择只依赖于本类样本,故不必考虑多分类情形时的数据不平衡问题．     

基于小波变换的全局最优独立分量分离算法

提出一种利用小波变换的低频系数作为滑动因子的盲源分离算法,通过建立以分母作为预测误差的信噪比目标函数,优化过程导致广义特征值求解,广义特征值构成的特征向量就是要求的分离矩阵,求解过程无需迭代。通过实验证明:计算量小,分离精度高,相似系数分别到达了1和0.9998,同时,可根据需要灵活选择小波基。     

广义稠密对称特征问题标准化算法在GPU集群上的有效实现

广义稠密对称特征问题的求解是许多应用科学和工程的主要任务,并且是计算电磁学、电子结构、有限元模型和量子化学等计算中的重要部分。将广义对称特征问题转化为标准对称特征问题是求解广义稠密对称特征问题的关键计算步骤。针对GPU集群,文中给出了广义稠密对称特征问题标准化块算法在GPU集群上基于MPI+CUDA的实现。为了适应GPU集群的架构,广义对称特征问题标准化算法将正定矩阵的Cholesky分解与传统的广义特征问题标准化块算法相结合,降低了标准化算法中不必要的通信开销,并且增强了算法的并行性。在基于MPI+CUDA的标准化算法中,GPU与CPU之间的数据传输操作被用来掩盖GPU内的数据拷贝操作,这消除了拷贝所花费的时间,进而提高了程序的性能。同时,文中还给出了矩阵在二维通信网格中行通信域和列通信域之间完全并行的点对点的转置算法和基于MPI+CUDA的具有多个右端项的三角矩阵方程BX=A求解的并行块算法。在中科院计算机网络信息中心的超级计算机系统“元”上,每个计算节点配置2块Nvidia Tesla K20 GPGPU卡及2颗Intel E5-2680 V2处理器,使用多达32个GPU对不同规模矩阵的基于MPI+CUDA的广义对称特征问题标准化算法进行测试,取得了较好的加速效果与性能,并且具有良好的可扩展性。当使用32个GPU对50000×50000阶的矩阵进行测试时,峰值性能达到了约9.21 Tflops。     

基于广义逆矩阵的B样条曲线节点消去算法研究

为了能运用广义逆矩阵理论来研究B样条曲线的节点消去问题，以解决在B样条曲线曲面拟合过程中产生的冗余节点数据，提出了一种基于广义逆矩阵的B样条曲线节点消去算法，该算法首先利用广义逆矩阵在处理奇异性问题上的独特作用来获得B样条曲线的节点可以消去的充要条件；然后在此基础上，又提出了消去多个节点的算法，算法对每个可以消去的节点都可计算相应的广义逆矩阵，而且仅进行一次矩阵的相乘即可得到由消去这个节点而产生的新的控制顶点和节点。实验表明，该算法的精度优于或近似于现有的Tiller算法，而时间效率则同于或近似于Tiller的算法。由于通过调整算法中的误差阈值，可以有效地控制消去节点后的曲线与原来曲线的误差，因此算法可以用于工程实践。     

基于融合邻域寻优与θ-PSO算法的矩阵特征值求解

提出一种融合邻域寻优与θ-PSO算法的矩阵特征值求解新方法,将矩阵特征值的求解问题转化为最优化问题。与需要多次运行程序分别求解不同范围的特征值算法相比,该方法可以一次性求出矩阵的全部特征根。仿真实验表明,该算法编程实现方便,对于不同类型的矩阵均可以应用,求解精度高,收敛速度快,大概在10~15代左右就可以收敛,完全可以满足工程实践运算中对精度和速度的要求。