求解大规模问题的多核学习正则化路径算法

多核学习在处理异构、不规则和分布不平坦的样本数据时表现出良好的灵活性和可解释性.针对精确正则化路径算法难以处理大规模样本数据的问题,文中提出正则化路径近似算法.根据采样分布函数进行抽样,在原始核矩阵的基础上生成近似矩阵,同时在拉格朗日乘子向量中抽取对应行,实现矩阵乘积的近似计算,提高多核学习正则化路径的求解效率.最后分析多核学习正则化路径近似算法的近似误差界和计算复杂性.在标准数据集上的实验验证文中算法的合理性和计算效率.     

基于CUR矩阵分解的多核学习正则化路径近似算法

多核学习在解决不规则、大规模数据问题时表现出良好的优越性。正则化路径是一种多次求解多核学习,选择最优模型的措施。针对多核学习正则化路径算法处理大规模数据时,核矩阵规模较大,计算代价高,影响优化模型效率的问题,提出一种基于CUR矩阵分解的多核学习正则化路径近似算法(Multiple kernel learning regularization path approximation algorithm with CUR, MKLRPCUR)。该算法首先采用CUR算法获得核矩阵的低秩近似矩阵的多个分解矩阵,然后在求解过程中利用低维的分解矩阵相乘替代核矩阵,调整相关矩阵计算的顺序,从而简化算法中核矩阵和拉格朗日乘子向量乘积的计算。 MKLRPCUR算法降低了矩阵的计算规模,优化了矩阵计算,提高了精确算法的计算效率。 从理论上分析低秩近似矩阵的相对误差和算法的时间复杂度,验证了近似算法的合理性。同时,在UCI数据集、ORL和COIL图像数据库上的实验结果表明,本文提出的近似算法不仅保证了学习的准确率,并且降低了算法的运行时间,提高了模型的效率。     

基于正则化路径的支持向量机近似模型选择

模型选择问题是支持向量机的基本问题.基于核矩阵近似计算和正则化路径,提出一个新的支持向量机模型选择方法.首先,发展初步的近似模型选择理论,包括给出核矩阵近似算法KMA-α,证明KMA-α的近似误差界定理,进而得到支持向量机的模型近似误差界.然后,提出近似模型选择算法AMSRP.该算法应用KMA-α计算的核矩阵的低秩近似来提高支持向量机求解的效率,同时应用正则化路径算法来提高惩罚因子C参数调节的效率.最后,通过标准数据集上的对比实验,验证了AMSRP的可行性和计算效率.实验结果显示,AMSRP可在保证测试集准确率的前提下,显著地提高支持向量机模型选择的效率.理论分析与实验结果表明,AMSRP是一合理、高效的模型选择算法.     

求逆矩阵的一个近似算法

一、前言计算逆矩阵A~(-1),原则上可以通过求解几个特殊的线性方程组来实现。所以,解线性方程组的方法都可以用来计算逆矩阵。笔者在[1]中给出了一个解线性代数方程组的快速迭代法,在此基础上得到一个求逆矩阵的近似算法。其逼近速度是指数级的。一般只需做几次、十几次矩阵乘法即可得到相当精度的结果。使用本方法编制程序也比较简单。     

正则化HSS预处理鞍点矩阵的多尺度算法

针对鞍点求解结果收敛速度慢、CPU消耗时间较长等问题,提出一种正则化HSS预处理鞍点矩阵的多尺度算法.运用最优正则化方法确定正则参数,得到计算最优正则参数公式;通过HSS方法完成系数矩阵预处理,得到新的预处理子NHSS;为了更加具体地分析预处理后的鞍点矩阵多尺度算法特征值分布形态,择优选取预处理子参数,确保算法收敛速率.通过仿真,结果表明所提算法可以提升鞍点矩阵方程求解的收敛速率,减少计算过程的CPU占用率,具有较好的鲁棒性,在大规模线性方程运算中可进行广泛应用.     

求多输入多输出有理传递函数的最小实现的一种算法

本文叙述了多输入多输出有理传递两数到状态方程的最小实现的方法,在所述的算法中用SVD分解求得最小实现的维数,再求解一系列相当于系数矩阵为上三角阵的线性方程组,得出最小实现的状态方程系数矩阵A、B、C。     

求解三对角线性方程组的迭代对角占优算法

针对并行求解三对角线性方程组的对角占优(PDD)算法,在系数矩阵为弱对角占优时,近似处理引入误差较大的问题,提出了一种PDD算法的迭代方案。该方案在解的修正值计算中采用迭代方法,计算精度得到了提高;通过对算法的误差分析,导出了算法在给定误差下迭代次数的估算式;数值实验说明了算法的有效性。通过对迭代与非迭代的PDD算法的复杂性分析,迭代算法的计算复杂性增加很小,但通信复杂性随迭代次数成倍增加。     

路径交叉检测与消除方法和邻节点置换方法改进TSP的解

针对当前算法在求解规模较大的TSP时得到的近似解中常常存在路径交叉这一不足,提出了一种路径交叉检测与消除方法,可以完全消除路径交叉从而提高近似解的质量;通过分析近似解的结构,发现一些相邻节点相互交换位置也可以有效提高解的质量,因此提出了一种邻节点置换方法。实验表明提出的方法可以有效改进模拟退火算法求得的TSP近似解。     

禁忌结合遗传结果对配送路径优化的应用研究

在建立物流配送路径优化问题数学模型的基础上,构造了求解该问题的混合算法,并进行了实验计算.计算结果表明,用混合算法进行物流配送路径优化,可以方便有效地求得问题的最优解或近似最优解,结果稳定性高.     

基于GPU-CUDA的共轭斜量法实现及性能对比

偏微分方程数值解法(包括有限差分法、有限元法)以及大量的数学物理方程数值解法最终都会演变成求解大型线性方程组。因此,探讨快速、稳定、精确的大型线性方程组解法一直是数值计算领域不断深入研究的课题且具有特别重要的意义。在迭代法中,共轭斜量法(又称共轭梯度法)被公认为最好的方法之一。但是,该方法最大缺点是仅适用于线性方程组系数矩阵为对称正定矩阵的情况,而且常规的CPU算法实现非常耗时。为此,通过将线性方程组系数矩阵作转换成对称矩阵后实施基于GPU-CUDA的快速共轭斜量法来解决一般性大型线性方程组的求解问题。试验结果表明:在求解效率方面,基于GPU-CUDA的共轭斜量法运行效率高,当线性方程组阶数超过3000时,其加速比将超过14;在解的精确性与求解过程的稳定性方面,与高斯列主元消去法相当。基于GPU-CUDA的快速共轭斜量法是求解一般性大型线性方程组快速而非常有效的方法。     

设备定位问题局部搜索算法的实验

讨论设备问题的局部搜索近似算法及其在实际计算中表现出的新性质。主要讨论局部搜索算法中初始解的产生方法,设备价值与服务价值大小对算法求解性能的影响。实验表明：约有99%以上的实例可直接利用局部搜索算法求得最优解;贪心算法产生初始解的局部搜索算法求解时间明显短于随机算法产生初始解的方法,但两者求解质量相当;设备价值和服务价值数值范围越大,局部搜索算法越容易求得最优解。     

旅行商问题优化解之间关系的分析

旅行商问题是经典的组合优化NP难题之一,学术界一直致力于建立在合理的计算时间内精确或近似求解问题的算法.近似算法常求得的高质量近似优化解与全局最优解之间边交集不为空,建立了两者之间及与全局最优解之间的特定关系,通过数学分析建立量化关系模型,利用实验确立模型中相关参数的先验概率.据此建立的随机TSP裁减过程大幅度裁减问题的求解规模;在求解过程中亦能高概率确定属于全局最优解的边,以提高问题求解效率和质量.     

适用于两种特定数据结构的CG算法与SOR算法

许多科学、工程计算问题都归结为大型线性方程组的求解.共轭斜量法与逐次超松弛方法是最常用的迭代法,它们或直接用于线性方程组的求解,或用于对直接法求出的近似解进行磨光.在上述两种迭代方法中,系数矩阵与列向量的乘积占很大计算量.因此,减少寻找运算数据所占用的时间,特别是对于大型稀疏方程组,系数矩阵分块存在外存贮器的情况下,减少寻址和数据I/O次数,对提高运行效率是举足轻重的.本文给出的是适用于两种常见数据结构的CG算法与SOR算法.它们几乎节省一半的寻址时间和更多的I/O时间,特别是在有大量I/O的情况下。     

求解弱非比例阻尼系统实模态解的阻尼矩阵摄动法

提出了一种求解弱非比例阻尼振动系统实模态解的摄动方法和将非比拟阻尼矩阵分解为比例阻尼矩阵和余项阻尼矩阵的方法.对于弱非比例阻尼振动系统,通过同时对阻尼矩阵和响应矢量进行小参数摄动,将原非比例阻尼系统分解为一系列的比例阻尼振动系统,在此基础上用正则模态变换将各阶比例阻尼的摄动方程解耦,从而求得原非比例阻尼振动系统的近似解析解.计算实例表明,此方法的结果与数值计算结果十分吻合.     

一类n×n矩阵博弈的Nash均衡的近似计算

给出了一种求解某类n×n矩阵博弈Nash均衡的近似解的算法。通过剖分单纯形,将混合策略空间离散化,利用初始的单纯形根据标号函数和替换规则求出此类矩阵博弈Nash均衡的近似解。并分析了其最优解与近似解的计算误差。     

三角网格表面任意两点间并行近似测地线算法

为降低求解三角网格表面任意两点间近似测地线长度和路径问题的时间开销,提出一种基于局部细分法的并行近似测地线算法。采用类矩阵乘最短路径并行算法求解点对间初始最短路径,并用源分割法映射子网格数据;所有处理器并行执行,对其所拥有点对之间的初始最短路径周围三角面片上的边进行细分操作;最后基于局部细化后的细分图并行,求得所有点对间的近似测地线长度和路径。实验结果表明,该并行近似测地线算法能够有效降低求解该类问题的计算时间,计算效率大大提高。     

飞翼飞行器嵌入式大气数据传感系统算法研究

介绍了嵌入式大气数据传感(FADS)系统的测压孔布局和压力模型;分析了超定线性方程组的解法,并用广义逆矩阵A+计算其最小二乘解;建立了形压系数ε与马赫数M∞、迎角α和侧滑角β的确切的函数模型;提出了故障点的处理方法;并用神经网络实现对动压、静压的求解。计算结果表明:飞翼飞行器的FADS系统的算法能够满足设计要求。     

局域网上求解线性方程组的一种并行Gauss-Seidel迭代算法

针对网络并行环境的计算能力强而通信相对较慢的实际情况,给出了一种局域网上求解线性方程组的并行Gauss-Seidel迭代算法.该算法将线性方程组的系数矩阵及右端项按行分块,然后将分块的系数矩阵及右端项按卷帘方式存储在各处理机,每次迭代通过循环传送已求出的部分解分量以减少处理机间的通信开销,提高并行算法的效率.试验结果表明该算法具有较高的并行效率和加速比.     

基于压缩存储技术求解压力Poisson方程的BiCGSTAB算法

基于投影算法所得压力Poisson方程进行数值离散,对离散系统形成的稀疏线性方程组,由于线性方程组的系数矩阵存在大量的零元素,为降低内存存储,本文以一维稀疏存储结构对大规模的系数矩阵进行压缩处理,只存储非零元素。同时,以具有优化性质的BiCGSTAB算法求解压力Poisson方程,显著的提高了计算效率。在相同初始条件下,利用Fortran90完成超松弛迭代法的程序求解压力Poisson方程数值离散所得到的线性方程组进行求解对比。结果表明基于压缩存储的BiCGSTAB算法在求解稀疏线性方程组具有明显的优势,该算法求解速度快、高效、可靠。     

求解Richardson迭代方程的快速配置法

本文依据多尺度快速配置法求解第一类Fredholm积分方程的Richardson迭代正则化方程.该方法得到了离散Richardson迭代正则化方程的快速解,在积分算子是弱扇形紧算子时,利用改进的迭代停止准则,给出了Richardson迭代正则化方法所得近似解的收敛率.最后,数值例子说明了算法的有效性.