摘要： We present an algorithm that computes an unmixed-dimensional decomposition of an arbitrary algebraic variety V. Each V_i in the decomposition V = V₁ ∩ … ∩ V_m is given by a finite set of polynomials which represents the generic points of the irreducible components of V_i. The basic operation in our algorithm is the computation of greatest common divisors of univariate polynomials over extension fields. No factorization is *** of the main problems in polynomial ideal theory can be solved by means of our algorithm: we show how the dimension of an ideal can be computed, systems of algebraic equations can be solved, and radical membership can be *** algorithm has been implemented in the computer algebra system MAPLE. Timings on well-known examples from computer algebra literature are given.

摘要： We shall describe an algorithm based on an idea of Roggenkamp and Scott (Roggenkamp and Scott, 1993) ) to compute Hom_alg(H, G), where H, G are finite p-groups and H, G are their group algebras over = /p. Using this algorithm it is possible to determine whether two such group algebras are isomorphic. An implementation of the algorithm has been used to show that the groups of order 64 are determined by their modular group algebras over /2.

关键词： LINEAR RECURRENCE PROGRAMS   STATIC ANALYSIS   INDEXED COMPUTATIONS   PROGRAM PARALLELIZATION   MASSIVE PARALLELISM   LOCALIZATION   SCHEDULING  

摘要： We systematically derive a systolic algorithm for the algebraic path problem (APP). We start with an algorithm with (parallel) running time 3n, but whose data dependencies are not local. The first step in obtaining a systolic algorithm is to localize these dependencies. The standard localization (used by all authors till now), forces slow-down the algorithm to the point that it takes 5n - 4 time steps. We show that much of this can be avoided, and give a new localization scheme which reduces the time to 4n - 2 (or 4n - 3 if n is odd). We also introduce a new approach to the problem of scheduling such parallel algorithms: we treat the equations defining the algorithm as an executable specification, but execute it on a non standard value domain. Such an abstract interpretation of the program then computes the optimal schedule of the original algorithm. A closed form can be inferred by observing a trace of this execution. We use this approach to obtain optimal schedules for all the algorithms in the paper-local as well as non-local.

关键词： 步进电动机   磁网络模型   计算方法  

摘要： 本文提出并证明了步进电机磁网络模型节点方程的系数矩阵具有对称正定性质,并用共轭斜量算法取代了以前的拟牛顿迭代法。共轭斜量法的优点是收敛域为全体实数,在角度步长和磁势步长放开的同时方法的收敛速度不受损失,从而使混合式步进电机的计算机辅助分析设计的计算时间大为缩短,为优化设计辅平了道路。另外,本文提出的结论和计算方法,对没有受控源且连通的、不含负电阻的线性和非线性电阻网络都是适用的。

关键词： INTEGER programming   NONLINEAR programming   ALGORITHMS   MATHEMATICAL programming   MATHEMATICAL optimization   OPERATIONS research   NONCONVEX programming  

摘要： Nonconvex mixed integer nonlinear programming problems arise quite frequently in engineering decision problems, in general, and in chemical process design synthesis and process scheduling applications, in particular. These problems are characterized by high dimensionality and multiple local optimal solutions. In this work, a novel approach is developed for determining the global optimum in nonlinear continuous and discrete domains. The mathematical foundations of the feature extraction algorithm are presented and the properties of the algorithm discussed in detail. The algorithm uses a partition and search strategy in which the problem domain is successively partitioned and a statistical approximation approach is used to characterize the objective function values and the constraint feasibility over a partition. Specifically, the general joint distribution function representing the objective function values is relaxed to a separable form and approximated using an expansion in terms of Bernstein functions. The coefficients of the expansion are determined by solving a small linear program. Feasibility is established by computing upper and lower bounds for the inequality constraint functions, while equality constraints are explicitly or numerically eliminated. Estimates of the volume averaged values of objective function and constraint feasibility are used to select efficient partitions for further investigation. These are refined successively so as to focus the search on the most promising decision regions. An alternative, constant resolution partitioning strategy is also developed using a suitably modified genetic search algorithm. Illustrative examples are used to demonstrate the key computational features of the method. [ABSTRACT FROM AUTHOR]

关键词： LINEAR PROGRAMMING   POLYNOMIAL-TIME ALGORITHMS   STRONGLY POLYNOMIAL-TIME ALGORITHMS   CIRCULANT MATRICES   ALGEBRAIC NUMBERS  

摘要： We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.

关键词： MATRIX ALGEBRA   ALGORITHMS  

摘要： The letter presents a new recursive algorithm for solving linear algebraic equations Ax = b. With this algorithm, the ith step recursion can find one solution of the first i equations;the unique solution of the total n equations could be found after the nth step recursion. Because of this recursive property, the algorithm can be used not only in solving ill-conditioned equations but also in recursive identification, signal processing and many other areas.