二阶矩阵快速乘法的一个新的算法集合

文献[1]—[4]从不同角度研究了二阶矩阵快速乘的各种问题,所有算法分属于以S算法与W算法为基础的两个算法集合.本文作者深入研究了算法的结构和性质,通过计算机检索,得到一个不属于上述两集合的算法和相应的包含有1048576个算法的封闭的算法集合.     

三对角与五对角Toeplitz矩阵求逆的算法

提出了一种求三对角与五对角Toeplitz矩阵逆的快速算法,其思想为先将Toeplitz矩阵扩展为循环矩阵,再快速求循环矩阵的逆,进而运用恰当矩阵分块求原Toeplitz矩阵的逆的算法.算法稳定性较好且复杂度较低.数值例子显示了算法的有效性和稳定性,并指出了算法的适用范围.     

求分块三对角矩阵和分块周期三对角矩阵逆矩阵的快速算法

给出了分块三对角矩阵逆矩阵的快速算法,并利用所给算法得到了求分块周期三对角矩阵逆矩阵的快速算法.最后通过算例表示算法的有效性.     

关于线性系统解的对称性算法的强稳定性的探索

关于线性方程解的算法方面,本文在对称非奇异矩阵类和对称正定矩阵类上给出了强稳定性算法.     

简化全局GMRES算法的扩张及收缩

简化的全局GMRES算法作为求解多右端项线性方程组的方法之一,与标准的全局GMRES算法相比,需要较少的计算量,但对应的重启动方法由于矩阵Krylov子空间维数的限制,收敛会较慢.基于调和Ritz矩阵,提出了简化全局GMRES的扩张及收缩算法.数值实验结果表明,新提出的扩张及收缩算法比标准的全局GMRES算法更为快速高效.     

Toeplitz矩阵填充的 $\ell$-步修正增广拉格朗日乘子算法[英文]

基于 Toeplitz矩阵填充(TMC)的修正增广拉格朗日乘子(MALM)算法, 本文给出此算法的一种加速策略, 提出Toeplitz矩阵填充的 $\ell$-步修正增广拉格朗日乘子算法. 该方法通过削减原 MALM算法中每一步迭代的频繁数据传输, 提高算法的运行效率. 同时也证明了新算法的收敛性. 最后以数值实验表明 $\ell$-步修正增广拉格朗日乘子算法比原 MALM算法更有效.     

三对角矩阵求逆的算法

研究了一般的非奇三对角矩阵的求逆,并给出了一个求逆矩阵的简单算法.首先研究了具有Doolittle分解的三对角矩阵的求逆,得到一个求逆的算法,然后将该算法推广到一般的非奇三对角矩阵上.最后给出了该算法与其它求逆方法的比较,可以看到该算法一方面计算量低,另一方面适用于不需任何附加条件的一般的非奇三对角矩阵.     

计算周期三对角矩阵行列式和逆矩阵的新算法

给出了一种计算周期三对角矩阵行列式和逆矩阵的新递推算法,它们的运算复杂度分别为O(n)和O(n2),该算法是文献[5]和[6]中相关算法的拓广.     

求解矩阵方程组的ABS算法

本文基于一类线性空间(Rn,n)n,n,建立求解( )X=B形式的矩阵方程组的ABS算法.讨论基本的ABS算法和两个特殊的ABS算法及其性质.并将其中的Huang算法用于求解带有各种约束(包括对称和稀疏约束)的拟牛顿方程.     

自然数幂和的矩阵算法

用矩阵算法方便地导出自然数幂和公式     

An Arnoldi-Extrapolation algorithm for computing PageRank

The Arnoldi-type algorithm proposed by Golub and Greif [G. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT 46 (2006) 759-771] is a restarted Krylov subspace method for computing PageRank. However, this algorithm may not be efficient when the damping factor is high and the dimension of the search subspace is small. In this paper, we first develop an extrapolation method based on Ritz values. We then consider how to periodically knit this extrapolation method together with the Arnoldi-type algorithm. The resulting algorithm is the Arnoldi-Extrapolation algorithm. The convergence of the new algorithm is analyzed. Numerical experiments demonstrate the numerical behavior of this algorithm.     

An algorithm for local continuous optimization of traffic signals

In this paper, an algorithm for sensitivity analysis for equilibrium traffic network flows with link interferences is proposed. Based on this sensitivity analysis algorithm, a general algorithm is provided for solving the optimal design and management problems for traffic networks. In particular, this algorithm is applied to the optimal traffic signal setting problem. A numerical example is given to demonstrate the effectiveness of our algorithm.     

An improved inexact Newton method

For unconstrained optimization, an inexact Newton algorithm is proposed recently, in which the preconditioned conjugate gradient method is applied to solve the Newton equations. In this paper, we improve this algorithm by efficiently using automatic differentiation and establish a new inexact Newton algorithm. Based on the efficiency coefficient defined by Brent, a theoretical efficiency ratio of the new algorithm to the old algorithm is introduced. It has been shown that this ratio is greater than 1, which implies that the new algorithm is always more efficient than the old one. Furthermore, this improvement is significant at least for some cases. This theoretical conclusion is supported by numerical experiments.      

一个求大规模非负不可约稀疏矩阵的谱半径及特征向量的新算法

本文设计了一个计算非负不可约矩阵的谱半径及其特征向量的新算法,并证明了其收敛性.该算法计算晕不大,占用内存少,有相同的0元模式,从而在大规模稀疏矩阵的计算中优势明显.最后用实例验证了此算法的可行性.     

Global minimization of a generalized linear multiplicative programming

This article presents a simplicial branch and bound algorithm for globally solving generalized linear multiplicative programming problem (GLMP). Since this problem does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving such problem. In this algorithm, a well known simplicial subdivision is used in the branching procedure and the bound estimation is performed by solving certain linear programs. Convergence of this algorithm is established, and some experiments are reported to show the feasibility of the proposed algorithm.     

基于变分不等式的支持向量机优化算法研究

由于标准支持向量机模型是一个二次规划问题,随着数据规模的增大,求解算法过程会越来越复杂.在K-SVCR算法结构的基础上,构造了严格凸的二次规划新模型,该模型的主要特点是可以将其一阶最优化条件转化为变分不等式问题,利用Fischer-Burmeister(FB)函数将互补问题转化为光滑方程组;建立光滑快速牛顿算法求解,并证明了该算法所产生的序列是全局收敛;利用标准数据集测试提出算法的有效性,在训练正确率和运行时间上与K-SVCR算法相比都有较好的表现,实验结果表明该算法可行且有效.     

基于混合单纯形算法的模糊均值图像分割

针对模糊C均值算法用于图像分割时对初始值敏感、容易陷入局部极值的问题,提出基于混合单纯形算法的模糊均值图像分割算法.算法利用Nelder-Mead单纯形算法计算量小、搜索速度快和粒子群算法自适应能力强、具有较好的全局搜索能力的特点,将混合单纯形算法的结果作为模糊C均值算法的输入,并将其用于图像分割.实验结果表明:基于混合单纯形算法的模糊均值图像分割算法在改善图像分割质量的同时,提高了算法的运行速度.     

NURBS曲线曲面拟合数据点的迭代算法

本文推广了文献[1]的结果,将文献[1]中关于B样条曲线曲面拟合数据点的迭代算法推广至有理形式,给出了无需求解方程组反求控制点及权因子即可得到拟合NURBS曲线曲面的迭代方法．该算法和文献[1]的算法本质上是统一的,而后者恰是前者的一种退化形式．文章还给出了收敛性证明以及一些定性分析．文末的数值实例说明该算法简单实用．     

解一类Hessian矩阵亏秩的修正BFGs算法及其局部Q-超线性收敛性

本文对凸函数在极值点的Hessian矩阵是秩亏一的情况下,给出了一类求解无约束优化问题的修正BFGS算法.算法的思想是对凸函数加上一个修正项,得到一个等价的模型,然后简化此模型得到一个修正的BFGS算法.文中证明了该算法是一个具有超线性收敛的算法,并且把修正的BFGS算法同Tensor方法进行了数值比较,证明了该算法对求解秩亏一的无约束优化问题更有效.     

线性分式多乘积规划问题的完全多项式时间近似算法

本文针对线性分式多乘积规划问题,通过Charnes-Cooper转化将原问题转化为一个等价问题,借助此等价问题提出一个获得原问题全局近似最优解的算法,最终证明了算法的收敛性,且提供了算法运算时间的理论分析.