关于矩阵乘法与整数卷积最佳算法运算量的估计

§1.引言 [1]通过构造一个大整数然后作整数乘除法给出了用于有理数矩阵相乘的算法,运算量为O(n~2),达到了矩阵乘法复杂性下界,是最佳算法。[2]曾指出[1]中忽略了不同字长有不同运算量这一事实。但对[1]中算法复杂性未作具体讨论和质疑。最近,[3]—[4]采用类似于[1]中的大整数乘除法分别提出整数向量卷积的算法,并认为运算量级为     

基于遗传算法和半参数回归的神经网络集成股市预测研究

股票时间序列预测在经济和管理领域具有重要的应用前景,也是很多商业和金融机构成功的基础.首先利用奇异谱分析对股市时间序列重构,降低噪声并提取趋势序列.再利用C-C算法确定股市时间序列的嵌入维数和延迟阶数,对股市时间序列进行相空间重构,生成神经网络的学习矩阵.进一步利用Boosting技术和不同的神经网络模型,生成神经网络集成个体.最后采用带有惩罚项的半参数回归模型进行集成,并利用遗传算法选择最优的光滑参数,以此建立遗传算法和半参数回归的神经网络集成股市预测模型.通过上证指数开盘价进行实例分析,与传统的时间序列分析和其他集成方法对比,发现该方法能获得更准确的预测结果.计算结果表明该方法能充分反映股票价格时间序列趋势,为金融时间序列预测提供一个有效方法.     

代数数极小多项式的近似重构

给出了代数数极小多项式近似重构的误差控制条件,进而基于同步整数关系探测算法SIRD,得到一个从代数数近似值重构其准确极小多项式的完备的新算法,从而将“采用近似计算获得准确值”这一思想的适用范围从有理数扩展到代数数.     

六元gcd封闭集上Smith矩阵的整除性

我们给出了关于六元gcd封闭集S的充分必要条件,使得在整数矩阵环M_6(Z)中,定义在S上的e次幂GCD矩阵(S~e)整除e次幂LCM矩阵[S~e].这部分解决了Hong在2002年提出的一个公开问题.     

基于新的Hessian近似矩阵的稀疏重构算法

一般来说,基于二次近似模型的优化算法具有良好的数值表现.然而,当基于二次近似模型的优化算法求解大规模优化问题时,若使用稠密矩阵近似目标函数在迭代点的Hessian矩阵,需要花费大量的计算成本和存储成本,因此设计Hessian矩阵合适的标量近似矩阵特别重要.对于正则化模型,利用最近三次迭代的信息,设计粗糙的标量矩阵,使用拟牛顿公式进行更新,结合近似最优梯度法的思想和梯度法的延迟策略,构造Hessian矩阵新的含有更多二阶信息的标量近似矩阵.结合非单调线搜索,提出基于新的Hessian近似矩阵的稀疏重构算法,并进行收敛性分析.实验结果表明,与经典稀疏重构算法算法相比,基于新的Hessian近似矩阵的稀疏重构算法在重构效果相似的情况下能较大地减少迭代次数和较快地重构信号.     

基于混沌最小二乘支持向量机的时间序列预测研究

为了对这种具有非线性特性的时间序列进行预测,提出一种基于混沌最小二乘支持向量机.算法将时间序列在相空间重构得到嵌入维数和时间延滞作为数据样本的选择依据,结合最小二乘法原理和支持向量机构建了基于混沌最小二乘支持向量机的预测模型.利用此预测模型对栾城站土壤含水量时间序列进行了预测.结果表明,经过相空间重构优化了数据样本的选取,通过模型的评价指标,混沌最小二乘支持向量机的预测模型能精确地预测具有非线性特性的时间序列,具有很好的理论和应用价值.     

基于多元混沌时间序列的油田产量预测模型

油田产量的预测一直是石油工作者研究的重要课题.针对油田产油量、产水量、地层压力和时间之间有着混沌的特征,利用多变量混沌时间序列等方法研究了油田产量的混沌建模和预测问题.用C-C算法确定每一个变量的嵌入维数和延迟时间,重构多元混沌时间序列的相空间;使用基于奇异值分解的主成分分析消除重构相空间的冗余变量和噪声干扰,建立了有较好泛化性能的多元混沌时间序列油田产量预测模型;最后将混沌时间序列预测和Elman神经网络进行耦合,创建了基于主成分分析前馈网络的多元混沌时间序列油田产量预测方法.应研究表明,提出的多变量混沌时间序列预测方法的预测精确度优于单变量预测,它可用于解决具有多变量混沌时间序列的预测问题.     

一类稀疏约束下不适定反问题的求解

矩阵填充是一类稀疏先验下的不适定的反问题.首先阐述了矩阵填充的基本原理,指出只有当待求的矩阵满足不相关特性或秩-受限等距特性时,才有可能精确重构未知矩阵.Jain P等将矩阵的不相关特性与秩-受限等距特性联系起来,提出了仿射-受限等距特性,但没有说明秩-受限等距常数与不相关常数的关系,定理3给出了两者之间的的数值关系,有效的促进了矩阵填充的研究.接下来分析了矩阵填充中常用的几种算法,并在随后的仿真实验中对这几种算法的重构性能做了详细比较.     

关于伽罗瓦数域的正规整基

设 Q 是有理数域,K 是 Q 的 n 次伽罗瓦扩域,再设 K 在 Q 上的伽罗瓦群 Gal(K/Q)={τ_1,τ_2,…,τ_η},如果存在 K 中的代数整数α,使{τ_1(α),τ_2(α),…,τ_n(α)}是 K 的整基,则称 K 具有正规整基。冯克勤同志在文[1]中指出“一个伽罗瓦数域何时具有正规整基,这个问题也有一定的理论价值”.本文给出了解决这一问题的一个方法.作为这一方法     

多变点检测问题的Shape-based BS算法

BS算法是时间序列多变点检测中最经典的算法之一,但是基于全局CUSUM统计量的识别过程会带来过多误判和较高的时间复杂度.BS算法是一种离线的序贯方法,因此没有充分利用数据的时序信息;另一方面,BS算法识别变点的原则是CUSUM统计量最大化,也没有考虑统计量构成序列的形态特性.鉴于此,提出一种基于局部形态识别的BS改进算法,命名为Shape-based BS算法.基于局部形态识别统计量,不仅大大降低计算复杂度,且降低了因变点间的互相干扰而带来的误判率,进而提升变点识别的稳健性.最后,将此算法应用到了电力系统的"场景压缩"问题上,具有满意的实用效果.     

Diophantine Quadratic Equation and Smith Normal Form Using Scaled Extended Integer Abaffy–Broyden–Spedicato Algorithms

Classes of integer Abaffy–Broyden–Spedicato (ABS) methods have recently been introduced for solving linear systems of Diophantine equations. Each method provides the general integer solution of the system by computing an integer solution and an integer matrix, named Abaffian, with rows generating the integer null space of the coefficient matrix. The Smith normal form of a general rectangular integer matrix is a diagonal matrix, obtained by elementary nonsingular (unimodular) operations. Here, we present a class of algorithms for computing the Smith normal form of an integer matrix. In doing this, we propose new ideas to develop a new class of extended integer ABS algorithms generating an integer basis for the integer null space of the matrix. For the Smith normal form, having the need to solve the quadratic Diophantine equation, we present two algorithms for solving such equations. The first algorithm makes use of a special integer basis for the row space of the matrix, and the second one, with the intention of controlling the growth of intermediate results and making use of our given conjecture, is based on a recently proposed integer ABS algorithm. Finally, we report some numerical results on randomly generated test problems showing a better performance of the second algorithm in controlling the size of the solution. We also report the results obtained by our proposed algorithm on the Smith normal form and compare them with the ones obtained using Maple, observing a more balanced distribution of the intermediate components obtained by our algorithm.     

The multiparametric 0–1-integer linear programming problem: A unified approach

We designed an algorithm for the multiparametric 0–1-integer linear programming (ILP) problem with the perturbation of the constraint matrix, the objective function and the right-hand side vector simultaneously considered. Our algorithm works by choosing an appropriate finite sequence of non-parametric mixed integer linear programming (MILP) problems in order to obtain a complete multiparametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems.     

关于整系数多项式有理根求法的注记

现行高等代数教材给出了求整系数多项式有理根的经典方法 ,周仲旺近日撰文又给出了一个新方法 ,称其“要比经典的方法有趣简捷”,但没有给出两个方法运算量的定量分析与比较 .本文先对经典方法从数学原理和算法设计两个方面作较详细明确的描述 ;再给出经典算法与周方法运算量的定量分析 ,比较的结果是周方法运算量比经典算法运算量多得多 .     

COMPUTING TRACE OF FUNCTION OF MATRIX

1 IntroductionIn some applications such as computational phySics, one often computes det~inant Ofmatrix and trace Of function of matrix. For ~ fun~ such as f(x) ~1/x or f(x) In (x) computing tr(f(A) ),i. e. tr(A--' ) or In(det(A) ) respeCtively, may be highly sensitiveproblems. When the matrix she n is small, we can compute these problemS explicits by usaldense ~x computation methods L6J. General speaking, such methods require O(n3) floating point OPerations. However, when n atomes larg…     

A fraction-free unit-circle zero location test for a polynomial with any singularity profile

This paper presents a fraction-free (FF) version of the Bistritz test to determine the zero location (ZL) of a polynomial with respect to the unit circle. The test has the property that when it is invoked on a polynomial with Gaussian or real integer coefficients, it is an efficient integer algorithm completed without fractions over the respective integral domain. The test is not restricted to integers but remains integer preserving (IP) in all possible encounters of abnormalities and singularities. We define a symmetric subresultant polynomial sequence (SSPS) for the Sylvester matrix of two symmetric polynomials. We then show that the sequence of polynomials produced by the FF test coincides with the SSPS of its first two polynomials when the test is normal and the SSPS is strongly nonsingular, or else its polynomials match the non-singular subresultant polynomial and pass over intermediate gaps of singular subresultants in an IP and efficient manner. This relationship (interesting in its own right) is used to show that the test is IP and normally attains integers of minimal size.     

An Arbitrary Starting Variable Dimension Algorithm for Computing an Integer Point of a Simplex

An arbitrary starting variable dimension algorithm is proposed to compute an integer point of an n-dimensional simplex. It is based on an integer labeling rule and a triangulation of Rⁿ. The algorithm consists of two interchanging phases. The first phase of the algorithm is a variable dimension algorithm, which generates simplices of varying dimensions,and the second phase of the algorithm forms a full-dimensional pivoting procedure, which generates n-dimensional simplices. The algorithm varies from one phase to the other. When the matrix defining the simplex is in the so-called canonical form, starting at an arbitrary integer point, the algorithm within a finite number of iterations either yields an integer point of the simplex or proves that no such point exists.     

Fast algorithms for determining the linear complexities of sequences over GF(p~m) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p-1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(pm)(any positive integer m) with the period 3n (n and pm - 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-lmamura algorithm, we can determine the linear complexity of any sequence over GF(pm) with the period 3n (n and pm - 1 are coprime) more efficiently.     

A variable dimension fixed point algorithm and the orientation of simplices

A variable dimension algorithm with integer labelling is proposed for solving systems ofn equations inn variables. The algorithm is an integer labelling version of the 2-ray algorithm proposed by the author. The orientation of lower dimensional simplices is studied and is shown to be preserved along a sequence of adjacent simplices.     

计算幂和多项式的矩阵方法

利用矩阵给出了计算幂和多项式的统一方法.     

Vector and matrix apportionment problems and separable convex integer optimization

The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193–210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure.