一种改进的XL算法

对XL算法中的方程组约简过程进行改进,提出一种更有效的求解算法。改进算法中充分利用各单项式之间的约束关系对方程组进行约简,消去其中次数较高的单项式。采用分步扩展及约简的思想消去扩展过程中添加的冗余等式,有效降低XL算法的计算复杂度及存储复杂度。此外,改进的算法还可用于构建布尔函数的低次零化子。     

关于HFE密码系统的密钥问题研究

多变量密码系统的设计与分析在理论探索与实际应用中扮演着重要的角色.在现有的多变量密码系统中,由Partarin在1996年提出的HFE密码系统被认为是最有前途的.在许多应用中,因HFE密码系统快速的公钥加密等原因,它还是一个很有前途的公钥密码.它的安全性是基于有限域F上的多元二次方程组的求解问题.在HFE公钥密码系统中,密钥问题是一个很重要的问题,但目前还没有映射φ:K-Fn[其中K是F的n次扩展,F的特征为2]及其逆的作用下,对每一个非平凡公钥都有qn(n 1)n/Ⅱi=1(qi-1)2个非平凡私钥与之相对应,同时得出结论:求有限域F上的任意二次方程组的解[方程的个数优小于等于变元的个数n]都可转化求有限域K(K是有限域F的"次扩展)上多项式方程的根,另外还给出了有限域F上HFE密码系统的两类弱密钥.这些结果不但能加深对HFE密码系统的理解,而且也可能产生对HFE密码系统的新的攻击.     

用参数法求一些特殊的线性代数方程组的数值解

本文将求解线性方程组数值解的双参数法进行推广,得到(?)种求解一些特殊的线性方程组的较为(?)般的方法-参数法,并具体给出利用三组参数求解拟二对角方程组和拟Hessen-berg方程组的算法.此算法具有明显的优越性.比如,在求解拟二对角方程组时,和利用LU分解法相比,乘除运算的次数由11n-16变为9n+20,所需要设定的向量组由5个降为4个.在求解拟Hessenberg方程组时,和Gauss消去法相比,除法运算的次数由1/2n(n+1)变为3n-4.这对求解大型的拟三对角方程组和拟Hessenberg方程组非常有利.当然,此种方法还可以用来求解其它一些方程组。     

实系数二元二次方程组实根分类求解方法

为了提高平面二次曲线求交结果的精度和拓扑稳定性,提出一种基于二次曲线分类的二元二次方程组实根求解方法.首先将二元二次方程组的2个方程依照系数判断出其在x-y平面上的曲线类型,并根据不同的曲线类型分类情况,应用曲线的参数方程将原方程组转化为一元四次方程;然后求解出一元四次方程的解,并依此求出原二元二次方程组的解.实验结果表明,与吴消元法相比,该方法有效地提高了二元二次方程组求解的精度.     

冗余方程对基于Minisat的代数攻击影响

分析基于Minisat软件的代数攻击方法,发现由该代数攻击方法对某些密码算法所建立的方程组中存在冗余方程,研究去除所有冗余方程的预处理方法,基于该方法提出先去除冗余方程,再利用Minisat软件求解无冗余方程组的代数攻击方法。实验结果表明,对CTC算法,新的攻击方法的攻击时间平均缩短了1/2,冗余方程的存在降低了基于Minisat软件的代数攻击的效率。     

结构方程模型的约束最小二乘解与确定性算法

研究了结构方程模型（SEM）的约束最小二乘解（CLS）,从分析SEM的观测方程组入手,发现了这个不定方程组的结构变量与观测变量必须满足的最小二乘关系,在对结构变量有固定模长参数约束的条件下,求出它的一组模长约束最小二乘解（MCLS）,MCLS可以作为求解结构方程组的偏最小二乘（PLS）迭代初值,在求得MCLS以后,在观测方程组中改变结构变量的模长,使得每个结构变量所对应的与观测变量的路径系数满足配方条件,是更为合理的约束,它可以保证结构变量与所辖的观测变量同质,尽管观测方程组是不定方程组,但是根据误差平方和最小以及对路径系数的配方约束,使得MCLS求解为合理的确定性算法,然后再对结构方程组直接求解,也是确定性算法,这就解决了结构方程模型求解的唯一性问题。     

一种设计分解的正确性证明

二维变量化设计系统可以用含有n个未知数、m个方程的非线性方程组表示．通过设计分解可以提高几何约束求解的效率和数值稳定性．给出了一种基于图论的设计分解方法及其正确性证明．该方法可以（1）处理结构欠约束系统的分解;（2）检测出冗余约束．分解算法在有限步内终止,其结果是结构相容的     

Improving Coarse-Grained Arc Consistency Algorithms in Solving Constraint Satisfaction Problems

约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3 frame ARR改进后的算法最多可以节省80％的修正检查次数和40％的求解耗时.     

改进求解约束满足问题粗粒度弧相容算法

约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.     

求组合电路无冗余覆盖的立方有序扩展法

本文提出一种直接求组合电路无冗余覆盖的立方有序扩展算法。算法根据预定要求达到的目标,制订了相应的处理策略,对立方的可扩展组元(变量)排出次序,并按次序逐个对立方的可扩展组元(变量)进行扩展。本算法比以往的对扩展变量任意排序的简单立方扩展法有更优化的运算结果。     

On a general optimal algorithm for multirate output feedbackcontrollers for linear stochastic periodic systems

A modified optimal algorithm for multirate output feedback controllers of linear stochastic periodic systems is developed. By combining the discrete-time linear quadratic regulation (LQR) control problem and the discrete-time stochastic linear quadratic regulation (SLQR) control problem to obtain an extended linear quadratic regulation (ELQR) control problem, one derives a general optimal algorithm to balance the advantages of the optimal transient response of the LQR control problem and the optimal steady-state regulation of the SLQR control problem. In general, the solution of this algorithm is obtained by solving a set of coupled matrix equations. Special cases for which the coupled matrix equations can be reduced to a discrete-time algebraic Riccati equation are discussed. A reducable case is the optimal algorithm derived by H.M. Al-Rahmani and G.F. Franklin (1990), where the system has complete state information and the discrete-time quadratic performance index is transformed from a continuous-time one     

大规模结构化二次规划并行算法

在内点算法(IPM)框架基础上,分析具有分块带边结构系数矩阵与箭形结构二次项的二次规划(QP)问题,导出其既约与最简既约修正方程.对既约修正方程系数矩阵进行置换,使其具有箭形分块结构,并结合该结构与解耦技术给出修正方程的并行求解算法,设计QP问题的并行IPM结构.在集群环境下的数值实验结果表明,该算法具有较好的加速比和...     

视觉传感网中基于二次规划的图像压缩感知

为降低视觉传感网络中图像压缩感知算法的计算复杂度,提出一种基于二次规划的网络图像恢复算法。该算法将压缩感知重构中的欠定线性方程组求解问题,转化为有界约束二次规划问题,在此基础上结合阿米霍步长准则,设计一种压缩感知图像恢复算法,通过求解二次规划问题对网络图像数据进行恢复。理论分析和仿真结果表明,与传统图像压缩感知算法相比,该算法可减少约1/3的图像数据恢复运算时间,且图像重构质量提高3 dB~6 dB,有效提高了视觉传感器网络图像恢复算法的实时性。     

稀疏结构化最小二乘双支持向量回归机

最小二乘双支持向量回归机（LSTSVR）通过引入最小二乘损失将双支持向量回归机（TSVR）中的二次规划问题简化为两个线性方程组的求解,从而大大减少了训练时间。然而,LSTSVR最小化基于最小二乘损失的经验风险易导致以下不足：（1）“过学习”问题;（2）模型的解缺乏稀疏性,难以训练大规模数据。针对（1）,提出结构化最小二乘双支持向量回归机（S-LSTSVR）以提升模型的泛化能力;针对（2）,进一步利用不完全Choesky分解对核矩阵进行低秩近似,给出求解S-LSTSVR的稀疏算法SS-LSTSVR,使模型能有效地训练大规模数据。人工数据和UCI数据集中的实验证明SS-LSTSVR不但可以避免“过学习”,而且能够高效地解决大规模训练问题。     

多个二元序列的二次复杂度研究

针对Rizomiliotis提出的多序列二次复杂度计算问题(IEEE Transations on Information Theory, 2005, No.5),利用相应线性方程系统的特殊分块结构,通过重新排列系数矩阵,设计一种求多序列二次复杂度的算法。复杂度分析表明,该算法可以在O(tn2)次运算操作中计算出给定多序列的二次复杂度。     

基于自适应模拟退火遗传算法的非线性方程组求解

将非线性方程组的求解问题转化为函数的优化问题。针对传统的遗传算法（GA）容易早熟的不足,对其进行了两方面改进,采用自适应交叉比例产生交叉后代和变异后代,并融合模拟退火算法（SA）的思想,建立了自适应模拟退火遗传算法（ASAGA）。数值实验表明,该算法提高了遗传算法的全局搜索能力,是求解非线性方程组的一种有效算法。     

A stabilization algorithm for a class of uncertain linear systems

This paper presents an algorithm for the stabilization of a class of uncertain linear systems. The uncertain systems under consideration are described by state equations which depend on time-varying unknown-but-bounded uncertain parameters. The construction of the stabilizing controller involves solving a certain algebraic Riccati equation. Furthermore, the solution to this Riccati equation defines a quadratic Lyapunov function which is used to establish the stability of the closed-loop system. This leads to a notion of ‘quadratic stabilizability’. It is shown that the stabilization procedure will succeed if and only if the given uncertain linear system is quadratically stabilizable.The paper also deals with a notion of ‘overbounding’ for uncertain linear systems. This procedure enables the stabilization algorithm to be applied to a larger class of uncertain linear systems. Also included in the paper are results which indicate the degree of conservativeness introduced by this overbounding process.     

The recursive reduced-order numerical solution of the singularlyperturbed matrix differential Riccati equation

Under stability-observability conditions imposed on a singularly perturbed system, an efficient numerical method for solving the corresponding matrix differential Riccati equation is obtained in terms of the reduced-order problems. The order reduction is achieved via the use of the Chang transformation applied to the Hamiltonian matrix of a singularly perturbed linear-quadratic control problem. An efficient numerical recursive algorithm with a quadratic rate of convergence is developed for solving the algebraic equations comprising the Chang transformation     

EPnL:一种高效且精确的PnL问题求解算法EI北大核心CSCD

现有Perspective-n-line (PnL)问题求解算法无法在获得高求解精度的同时保证高求解效率.为解决这个缺点,提出了同时兼具求解效率和求解精度算法EPnL.该方法首先将PnL问题转换为求二次曲面方程组交点的问题,然后利用单位四元数中变量不同时为零的特性,分类参数化PnL问题中的旋转矩阵.最后,为克服常规优化方法可靠性和效率较低的问题,同时兼具求解效率和求解精度算法利用二次曲面方程组自身的结构信息,采用低次项参数化高次项的方式将二次曲面方程组的求解问题转换为单变量多项式的求解问题.实验表明,相比于现有算法,该算法在具有高求解精度的同时也兼具有高求解效率.     

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

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