Rutishauser's modified method for computing the eigenvalues of symmetric matrices

The purpose of this paper is to present a new procedure for the Rutishauser method (LR-method) of computing eigenvalues of symmetric matrices. This procedure is useful for real symmetric matrices with small band-widths. Shifts of origin are required for accelerating the process of convergence that may lead to indefinite matrices for which the classical approach is not applicable. The present approach demands only that the leading principal minors of the matrices operated have non-zero values. This paper compares this approach with the classical approach based on Cholesky factorizations and with the QR-method. The numerical results presented show the great effectiveness of the former.     

基于网络拓扑图的树的代数连通度

代数图谱理论方法在网络设计中发挥重要作用。网络拓扑图的Laplacian矩阵的谱与网络的同步能力有关,代数连通度就是一个刻画同步能力的重要参数。采用移接变形方法,讨论了树的代数连通度和直径之间的关系,获得了下面的结论：当树的顶点数固定时,树的代数连通度随着树的直径的增加而减少。进一步地,讨论了树的代数连通度的上界和下界。     

多智能体网络系统的能控性代数条件

能控性是多智能体系统研究的核心问题,主要包括结构可控性和精准可控性。对多智能体系统的模型和能控性代数条件进行了总结。在相对协议和绝对协议条件下,运用图论和矩阵论的知识系统分析了多智能体系统能控性的代数条件。按照同质多智能体到异质多智能体的顺序,对现有的多智能体系统模型和代数条件进行了梳理,并在已有结论的基础上对多智能体系统能控性的代数条件进行了改善,进一步提出了新的代数条件。多智能体能控性代数条件的改进大大简化了能控性的计算量。     

一类H布尔函数的代数次数、相关免疫性与代数免疫性的关系

以布尔函数的导数和自定义的e-导数为研究工具,研究了一类特定Hamming重量的H布尔函数的代数次数、代数免疫性、相关免疫性之间的关联问题.得出H布尔函数的组成部分e-导数的代数次数决定了H布尔函数的代数次数;H布尔函数的e-导数与H布尔函数的代数免疫阶的大小紧密关联;H布尔函数的e-导数可将H布尔函数的代数免疫性、零化子、相关免疫性、代数次数联系到一起等.同时,导出了公式法和级联法两类求解H布尔函数最低代数次数零化子的不同方法.     

Constructing quantitative models using monotone relationships

Constructing quantitative models typically requires characterizing a system in terms of algebraic relationships and then using these relationships to compute quantitative values from numerical data. For real-life systems, such as computer operating systems, an algebraic characterization is often difficult, if not intractable. The paper proposes a statistical approach to constructing quantitative models using monotone relationships. Referred to as nonparametric interpolative-estimation for monotone functions (NIMF), our approach uses monotone relationships to search historical data for bounds that provide a desired level of statistical confidence. NIMF makes no assumption about the algebraic form of the monotone relationship, not even continuity. We present two examples of applying NIMF to computer measurements, and compare NIMF's confidence intervals with those of least-squares regression, a traditional technique that requires specifying an algebraic relationship. Our results suggest that when an algebraic characterization is not known with precision, using NIMF with an accurate monotone relationship can produce more accurate confidence intervals than employing least-squares regression with a polynomial approximation to the unknown algebraic relationship     

Algebra of Systems: A Metalanguage for Model Synthesis and Evaluation

This paper represents system models as algebraic entities and formulates model transformation activities as algebraic operations. We call this modeling framework ldquoalgebra of systemsrdquo (AoS). To show that AoS can automate complex model reasoning tasks in system design projects, we implemented the abstract algebraic specification as an executable metalanguage named object-process network, which serves as a tool for automatic model transformation, enumeration, and evaluation. A case study of the Apollo lunar landing mission design is developed using this algebraic modeling approach.     

代数次数的求解算法及其在SIMON-like算法中的应用

代数次数作为布尔函数重要的密码学指标,在密码算法的设计与分析中有着重要的应用.主要研究布尔函数代数次数的求解及其在分组密码SIMON-like算法中的应用.首先,在利用真值表求解代数正规型算法的基础上建立了基于CUDA的并行求解架构,协同利用CPU和GPU的计算资源,极大地缩短了求解代数次数的时间,在较短的时间内求解了SIMON32算法和SIMECK32算法任意轮数的代数正规型和代数次数;其次,在Cube攻击理论的基础上,根据代数次数和超多项式取值之间的关系,设计了估计代数次数的概率算法,估计了一般SIMON-like算法布尔函数的代数次数;最后,从布尔函数代数次数的角度出发,给出了SIMON-like算法在选择不同循环移位参数表现的差异性,进而给出循环移位参数的选取依据.实验结果表明,SIMON算法在原始参数下,达到最大代数次数所需的轮数最短,原始参数具有更高的安全性.     

Some new results on the algebraic characterizations of an equality constrained optimization problem equivalent to the transportation problem

An equality constrained optimization problem equivalent to the transportation problem with m sources and n destinations is described. The optimality condition and some algebraic characterizations of the problem are investigated using its Hessian matrix. In addition, several algebraic characterizations of an equivalent case of the transportation problem are given using the spectral decomposition and generalized inverses of its coefficient matrix. It is shown that the transportation problem and its equivalent case have common algebraic characterizations.     

多值逻辑网络的输出跟踪牵制控制

本文利用代数状态空间方法,研究了多值逻辑控制网络的输出跟踪牵制控制.首先利用矩阵的半张量积给出了带牵制控制的多值逻辑控制网络的代数表示.其次基于该代数表示,定义了一组合适的能达集,并建立了多值逻辑控制网络输出跟踪牵制控制器的设计方法.再次,利用多值逻辑哑算子的性质,给出了多值逻辑控制网络分布式输出跟踪控制问题可解的充要条件.最后将所得的理论结果应用于网络演化博弈的演化行为分析.     

基于有向距离场的代数B-样条曲线重建

提出了一种以代数B-样条曲线为表达形式、基于有向距离场的隐式曲线重建方法.首先给定一个表示封闭曲线、可能带有噪音且分布不均匀的平面点云,采用移动最小平方(moving least square,简称MLS)方法对点云去噪、重采样,得到一个低噪音、分布均匀的"线状"点云,再通过Level Set方法建立该"线状"点云的离散几何距离场,最后用一个代数B-样条函数光顺拟合该离散距离场,代数函数的零点集即为重建曲线.曲线重建过程可以归结为求解线性方程组问题.这种重建方法不仅可以得到高质量的重建曲线,还可以得到曲线周围的距离场信息.同时,避免了隐式曲线重建中经常出现的多余分支问题.     

Solving systems of algebraic equations by a general elimination method

A method of factorisation of a U-resultant into linear factors is given. Using this method we can obtain solutions and their multiplicities of a system of algebraic equations, provided the system of algebraic equations has finitely many solutions. We directly calculate a matrix à which gives all solutions of the system by using a Gröbner basis of the ideal generated by the polynomials of the system of algebraic equations.     

Automatic parameterization of rational curves and surfaces III: Algebraic plane curves

We present algorithms to compute the genus and rational parametric equations, for implicitly defined irreducible plane algebraic curves of arbitrary degree. Rational parameterizations exist for all irreducible algebraic curves of genus 0. The genus is computed by a complete analysis of the singularities of plane algebraic curves, using affine quadratic transformations. The rational parameterization techniques, essentially, reduce to solving symbolically systems of homogeneous linear equations and the computation of polynomial resultants.     

Application of Symbolic Computation Methods for Investigation of Stationary Motions of an Axisymmetric Satellite

With the help of computer algebra methods properties of the algebraic system that determines stationary motions of an axisymmetric satellite moving along a circular orbit subject to gravitational and active damping moments are investigated. The main attention is paid to the study of the conditions for the existence of stationary satellite motions. Computer algebra methods based on the algorithm for the construction of Gröbner bases are applied to reduce the satellite stationary motion system of six algebraic equations in six variables to a single algebraic equation in one variable that determines all stationary motions of the satellite. A classification of domains with equal numbers of stationary solutions is carried out using algebraic methods for constructing discriminant hypersurfaces. The effectiveness of various algorithms for constructing Gröbner bases for the solution of the problem under consideration was compared.     

Views of queues

Starting from an algebraic specification of the data type QUEUE several variants of communicating agents representing queues are studied. It is demonstrated how new issues such as exceptions, robustness, and concurrency can be considered, when going from a purely algebraic view of queues to queues used in the framework of communicating systems. Nevertheless the verification of the communicating agents can be done by classical techniques for proving implementations correct, developed in the framework of algebraic specification. Finally the design of infinite networks representing queues and their verification is demonstrated. Although shown only for a simple example a general method is aimed at for the development of interactive and concurrent programs from algebraic specification using applicative programming styles.     

An Algorithm for Computing an Integral Basis in an Algebraic Function Field

Algorithms for computing integral bases of an algebraic function field are implemented in some computer algebra systems. They are used e.g. for the integration of algebraic functions. The method used by Maple 5.2 and AXIOM is given by Trager in [Trager, 1984]. He adapted an algorithm of Ford and Zassenhaus [Ford, 1978], that computes the ring of integers in an algebraic number field, to the case of a function field.It turns out that using algebraic geometry one can write a faster algorithm. The method we will give is based on Puiseux expansions. One can see this as a variant on the Coates' algorithm as it is described in [Davenport, 1981]. Some difficulties in computing with Puiseux expansions can be avoided using a sharp bound for the number of terms required which will be given in Section 3. In Section 5 we derive which denominator is needed in the integral basis. Using this result 'intermediate expression swell' can be avoided.The Puiseux expansions generally introduce algebraic extensions. These extensions will not appear in the resulting integral basis.     

4 bit S盒输入及输出低次代数关系分析

随着4 bit S盒在轻量级密码算法中的广泛应用,如何捕获这些4 bit S盒输入及输出的代数关系成为了目前的研究热点之一。根据S盒的输入及输出关系,提出了◢n◣ bit S盒的非线性回路代数关系的通用求解算法。针对4 bit S盒设计了高效的非线性回路代数关系求解算法,并对国际公认的16类最优4 bit S盒及多个著名的轻量级密码算法中的S盒进行了测试分析。同时,还对上述轻量级密码算法中S盒所属等价类进行了检测。研究结果表明：16类S盒代表元中只有3类不存在二次回路代数关系;同属等价类S盒可能会有不同的二次回路代数关系;MANTIS、PRIDE、Marvin等轻量级算法的S盒存在多个二次回路代数关系。即这些包含低次回路代数关系的S盒存在潜在的安全缺陷。     

Garment中的归约语义

文中用代数方法研究了Ｇａｒｍｅｎｔ中程序设计语言的归约语义，首先给出了归约语义在形式语言理论中的含义，然后提出了Ｇａｒｍｅｎｔ中语言的代数模型。在此代数模型下讨论了归约语义及其性质，并给出了语言可归的充分条件。     

基于矩阵方法的Banzhaf值的计算及应用

在合作博弈中,Banzhaf值提供了每个参与者形成大联盟的预期边际贡献,因此Banzhaf值的求解是一个重要的研究内容.本文首先回顾合作博弈及Banzhaf值的定义,并且运用矩阵半张量积,给出合作博弈特征函数的代数表示.然后给出了Banzhaf值的等价的代数形式和简捷的计算方法.最后将所得结果应用于生物网络中,用Banzhaf值度量遗传疾病基因相关性的可能性,确定与遗传疾病发病高度相关的基因.     

基于逻辑方程求解的网络故障定位规则的验证与实现

随着互联网的普及与快速发展,网络服务质量成为了最受关注的问题之一.本文利用矩阵半张量积方法,研究互联网网络中的故障定位问题.首先,利用矩阵半张量积给出网络中路径的代数表示.其次,基于该代数表示,将故障定位问题对应的逻辑方程转化为等价的代数方程,通过分析代数方程的解,确定网络中发生故障的链接.最后,通过例子说明所得理论结果的有效性.     

Representation of piecewise continuous algebraic surfaces in terms of B-splines

A method for representing shape using portions of algebraic surfaces bounded by rectangular boxes defined in terms of triple product Bernstein polynomials is described and some of its properties are outlined. The method is extended to handle piecewise continuous algebraic surfaces within rectangular boxes defined in terms of triple products of B-spline basis functions. Next, two techniques for sculptured shape creation are studied. The first is based on geometric manipulation of existing primitives and the second on approximation/interpolation of lower dimensional entities using least-squares techniques based on singular value decomposition. In addition, several interrogation techniques, such as contouring, ray tracing and curvature evaluation, used in the design and analysis of piecewise continuous algebraic surfaces are discussed.