零维代数簇的分解及其应用

本文利用Groebner基，给出了一种分解零维代数簇的方法，并且讨论了这种方法在理想的准素分解以及几何定理机器证明中的应用．     

代数方程组相关性的一个判准及其在定理机器证明中的应用

本文在吴-Ritt 整序原理基础上,给出了检验一多项式在一给定的代数簇上是否消没的充要条件,检验方法是切实可行的,且不依赖于代数簇的分解.     

参系数零维分片代数簇的实零点

分片代数簇是一些多元样条函数的公共零点集. 文中表明: 解参系数分片代数簇问题可转化为解有限个包含严格不等式的参系数多项式系统. 利用半代数系统的正则分解和柱形代数分解方法, 提出了计算零维参系数分片代数簇无挠实零点数的上确界, 以及达到上确界时实零点在各个胞腔内的数目分布情形的算法. 该算法同时能产生达到上确界的充要条件, 以及达到上确界时实零点数在各个$n$维胞腔内 取得某种分布的充要条件. 也给出了另一算法, 用于产生零维分片代数簇在$n$维复形中的 各个$n$维胞腔内恰有指定数目的相异无挠实零点的充分必要条件.     

双正交小波滤波器簇代数结构及构造

研究了一类向量多项式两种特殊分解结构,由此引进了与双正交小波滤波器簇相应的多相向量概念,分析了多相向量分解代数结构,得到了在低通滤波器给定条件下,满足任意阶可和规则的对偶低通滤波器构造方法.分析并证明了双正交滤波器簇对应多相向量至多具有的3种代数分解结构,根据其分解的形式得到了双正交小波基构造的新方法,该方法便于双正交小波构造计算机程序化.     

几何定理机器证明的结式矩阵法

本文提出了一种不必预先分解升列为不可约于列而克服所谓“可约性困难”的方法．由于使用了吴除法及子结式计算，我们也称这种方法为ＷＲ分解算法．     

代数簇上的陈省身示性系

任一复流形M有一组陈省身示性类。如果M同时是一个没有奇点的代数簇,则Gamkrelidze与陈省身曾证明了都是代数的,卽中有上闭链对偶于以M的代数子簇为代表的下闭链。这自然引起了如何从代数几何方法对代数簇引入与陈省身示性类相仿的概念的问题。在[3]中,Grothendieck(以及Washnitzer在[6]中)引进了代数簇的陈省身示性系,但须假定代数簇是没有奇点的。这个没有奇点的限制似乎是难以避免的,因为:第一,他的方法须借助于流形的切丛,但在有奇点时,切丛则无从定义;第二,他的方法须用到代数流形上的(有理等价)交截环,而在有奇点时,这个环也没有圆     

微分算子环的素理想

本文利用代数的方法与基本结果，对钟家庆关于微分算子理想的结构基于Ｈ．Ｍａａｓｓ的调和齐式分解所得到的结果，在复系数情形给出了一个纯代数的简短证明，在证明中不需要关于微分算子的齐次性假设     

序群上的Toeplitz算子代数

设（G，G~＋）为序群，定义了（G，G~＋）上Toeplitz算子代数所对应的广群并研究其单位空间的结构.作为一个推论，得到相应的广群C~*－代数的分解．     

Rota-Baxter簇系统与Gr\"obner-Shirshov基

从Yang-Baxter簇方程和Volterra积分方程得到的Rota-Baxter簇代数的概念出发,我们引入Rota-Baxter簇系统的概念,推广了Brzezinski提出的Rota-Baxter系统.我们证明这个概念也与结合Yang-Baxter簇对和pre-Lie簇代数有关.此外,作为Rota-Baxter簇系统的一个类比,我们引入平均簇系统的概念,并证明平均簇系统会得到dialgebra簇结构.我们还研究dendriform代数上的Rota-Baxter簇系统,并展示它们如何诱导quadri簇代数结构.最后,我们用Gr\"obner-Shirshov基的方法给出Rota-Baxter簇系统的一个线性基.     

李三系分解的唯一性

李三系是从黎曼对称空间产生的三元运算的代数体系，近来得到许多数学家的重视．但是至今为止，李三系的研究集中在半单与单李三系上．本文主要讨论中心为零的李三系的一些基本问题，特别是分解唯一性问题．我们的结果包含了半单李三系的分解唯一性．     

A generic auction algorithm for the minimum cost network flow problem

In this paper we broadly generalize the assignment auction algorithm to solve linear minimum cost network flow problems. We introduce a generic algorithm, which contains as special cases a number of known algorithms, including the -relaxation method, and the auction algorithm for assignment and for transportation problems. The generic algorithm can serve as a broadly useful framework for the development and the complexity analysis of specialized auction algorithms that exploit the structure of particular network problems. Using this framework, we develop and analyze two new algorithms, an algorithm for general minimum cost flow problems, called network auction, and an algorithm for thek node-disjoint shortest path problem.     

关于整数向量卷积的一个算法的时间复杂度

众所周知,两个n维整数向量循环卷积的常规算法(即按定义计算)的时间复杂度为O(n~2),现在已有时间复杂度为O(nlog_2n)的快速算法,[1]中提出一个新算法,称其时间复杂度为O(n),因而是最佳的。 本文首先指出[1]的错误原因,再根据算法分析理论得出[1]中算法的时间复杂度不低于O(n~2log_2n),因而比常规算法的运算量还大。     

A quasi quadratic time algorithm for hyperelliptic curve point counting

We describe an algorithm to compute the cardinality of Jacobians of ordinary hyperelliptic curves of small genus over finite fields with cost . This algorithm is derived from ideas due to Mestre. More precisely, we state the mathematical background behind Mestre’s algorithm and develop from it a variant with quasi-quadratic time complexity. Among others, we present an algorithm to find roots of a system of generalized Artin-Schreier equations and give results that we obtain with an efficient implementation. Especially, we were able to obtain the cardinality of curves of genus one, two or three in finite fields of huge size. 2000 Mathematics Subject Classification Primary—11S40, 14H42, 11G20, 11G15, 94A60     

Minimization of equilibrium problems,variational inequality problems and fixed point problems

In this paper, we devote to find the solution of the following quadratic minimization problem

$\min_{x\in \Omega}\|x\|^2,$

where Ω is the intersection set of the solution set of some equilibrium problem, the fixed points set of a nonexpansive mapping and the solution set of some variational inequality. In order to solve the above minimization problem, we first construct an implicit algorithm by using the projection method. Further, we suggest an explicit algorithm by discretizing this implicit algorithm. Finally, we prove that the proposed implicit and explicit algorithms converge strongly to a solution of the above minimization problem.

     

A generalized elastic net regularization with smoothed $$\ell _{q}$$ penalty for sparse vector recovery

In this paper, we propose an iterative algorithm for solving the generalized elastic net regularization problem with smoothed \(\ell _{q} (0<q \le 1)\) penalty for recovering sparse vectors. We prove the convergence result of the algorithm based on the algebraic method. Under certain conditions, we show that the iterative solutions converge to a local minimizer of the generalized elastic net regularization problem and we also present an error bound. Theoretical analysis and numerical results show that the proposed algorithm is promising.     

An Accelerated Inexact Proximal Point Algorithm for Convex Minimization

The proximal point algorithm is classical and popular in the community of optimization. In practice, inexact proximal point algorithms which solve the involved proximal subproblems approximately subject to certain inexact criteria are truly implementable. In this paper, we first propose an inexact proximal point algorithm with a new inexact criterion for solving convex minimization, and show its O(1/k) iteration-complexity. Then we show that this inexact proximal point algorithm is eligible for being accelerated by some influential acceleration schemes proposed by Nesterov. Accordingly, an accelerated inexact proximal point algorithm with an iteration-complexity of O(1/k ²) is proposed.     

An $$\ell _{2}$$-neighborhood infeasible interior-point algorithm for linear complementarity problems

In this paper, we propose an infeasible interior-point algorithm for linear complementarity problems. In every iteration, the algorithm constructs an ellipse and searches an \(\varepsilon \)-approximate solution of the problem along the ellipsoidal approximation of the central path. The theoretical iteration-complexity of the algorithm is derived and the algorithm is proved to be polynomial with the complexity bound \(O\left(n\log \varepsilon ^{-1}\right)\) which coincides with the best known iteration bound for infeasible interior-point methods.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

Polynomiality of infeasible-interior-point algorithms for linear programming

Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal—dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interior points, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. In this paper, we show that a modification of the Kojima—Megiddo—Mizuno algorithm solves the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, we develop anO(nL)-iteration complexity result for a variant of the algorithm.The original title was Polynomiality of the Kojima—Megiddo—Mizuno infeasible-interior-point algorithm for linear programming.Research performed while visiting Cornell University (April 1992 – January 1993) as an Overseas Research Scholar of the Ministry of Science, Education and Culture of Japan.