共查询到20条相似文献,搜索用时 128 毫秒
1.
特征列算法是吴方法的核心算法,为了提高吴方法的计算效率,分析吴方法计算中的特征列计算和多项式因式分解,采用粗粒度并行计算的方法,给出基于分布Maple系下的吴方法计算的特征列计算以及多项式因式分解的并行化算法,为吴方法计算的并行化研究提供方法. 相似文献
2.
潘晓辉 《计算机技术与发展》2014,(5):125-128,133
为了解决串行部分选主元的高斯消去算法不能充分利用多核处理器的问题,提出并实现了并行多线程的部分选主元的高斯消去算法,并将整个算法进行了分析和优化,使数据的存储布局和算法的访存模式匹配,从而大幅提高了程序的性能。通过对本地Linux服务器以及美国亚马逊EC2云的多种平台上的实验结果的比较和分析,确定了部分选主元的高斯消去算法受缓存影响较大,所以在CPU和内存/缓存配置较为均衡的平台上运行性能最好。文中展现了一种高效率、扩展性好的多线程并行部分选主元的高斯消去算法以及将一般性串行算法进行并行化和优化的方法。 相似文献
3.
时段演算是描述和推导嵌入式实时系统和混成系统性质的一种区间时态逻辑.扩展线性时段不变式是时段演算的重要子集.针对实时自动机,提出一种连续时间语义下扩展线性时段不变式的有界模型检验方法.该方法将扩展线性时段不变式的有界模型检验问题转化为量词线性算术公式的正确性问题,从而可以采用量词消去技术进行求解.首先,运用符号化的思想,在实时自动机上利用深度优先搜索找到所有满足观测时长约束的符号化路径片段;然后,将每条符号化路径片段转化为一个量词线性算术公式;最后,利用量词消去工具求解.与已有工作相比,基于实时自动机设计了验证算法.另外,降低了验证复杂度,并且加速了验证过程的实际速度. 相似文献
4.
一种层次的、混合并行离散事件仿真算法 总被引:5,自引:0,他引:5
并行仿真算法是并行离散事件仿真中心的核心问题,对于具体的应用系统,采用不同的并行仿真算法将导致其仿真性能大的差异,提出了一种针对于分布环境中特定应用系统仿真的层次的,混合并行离散事件仿真算法,测试和应用表明,和通常的保守机制或者乐观机制相比,能够较大地提高仿真效率,并且具有良好的可扩展性,首先给出了在通信开销不可忽略的环境下,保守机制和乐观机制的性能测试结果和两者适用情况的分析,然后根据测试结果和具体应用系统的特点,提出了层次的,混合并行离散事件仿真算法,给出了LP级和组级算法算,最后对算法进行了测试和性能分析。 相似文献
5.
6.
并行数据库上的进行CMD—Join算法 总被引:1,自引:1,他引:1
并行数据库在多处理机之间的分布方法对并行数据 算法的性能影响很大,如果在设计并行数据操作算法时充分利用数据分布方法的特点,可以得到十分有效的并行算法。本研究如何充分利用数据分布方法的特点,设计并行数据操作算法的问题,提出了基CMD多维数据分布方法的并行CMD-Join算法,理论分析和实验结果表明,并行CMD-Join算法的效率高于其它并行Join算法。 相似文献
7.
8.
针对传统超高频射频识别(UHF RFID)系统中出现的多标签碰撞问题,提出一种基于锁位的并行二进制分割(LPBS)防碰撞算法。利用曼彻斯特编码发送锁位指令,确定并提取碰撞位,不再传输非碰撞位信息;利用并行二进制分割技术,使得阅读器和标签可以进行一位标签应答。该算法减少阅读器和标签之间传送的比特数量的同时,减少了碰撞时隙。仿真结果表明,在大多数情况下,该算法在吞吐率、时间延迟等方面优于传统的防碰撞算法。 相似文献
9.
建立了一个把半正定稀疏多项式表为多项式平方和的算法.这一算法依赖于Hilbert第17问题的一系列经典研究结果以及实闭域上量词消去的柱形代数剖分算法.该算法的机器实现为一类代数不等式可读性证明的自动生成提供了一种非常自然的途径. 相似文献
10.
11.
12.
The first-order logical theory of dense linear order has long been known to admit quantifier elimination. This paper develops an explicit algorithm that yields an equivalent quantifier free form of its input formula. This algorithm performs existential quantifier elimination via constraint propagation. The result is computed incrementally using functional programming techniques. This approach may be of interest in implementing query languages for constraint databases. 相似文献
13.
《Journal of Symbolic Computation》2001,31(5):521-547
This paper presents a method for the simplification of truth-invariant cylindrical algebraic decompositions (CADs). Examples are given that demonstrate the usefulness of the method in speeding up the solution formula construction phase of the CAD-based quantifier elimination algorithm. Applications of the method to the construction of truth-invariant CADs for very large quantifier-free formulas and quantifier elimination of non-prenex formulas are also discussed. 相似文献
14.
Linear equalities, disequalities and inequalities on fixed-width bit-vectors, collectively called linear modular constraints, form an important fragment of the theory of fixed-width bit-vectors. We present a practically efficient and bit-precise algorithm for quantifier elimination from conjunctions of linear modular constraints. Our algorithm uses a layered approach, whereby sound but incomplete and cheaper layers are invoked first, and expensive but complete layers are called only when required. We then extend this algorithm to work with arbitrary Boolean combinations of linear modular constraints as well. Experiments on an extensive set of benchmarks demonstrate that our techniques significantly outperform alternative quantifier elimination techniques based on bit-blasting and linear integer arithmetic. 相似文献
15.
Minimizing envy in distributed discrete resource or task allocation, is an unusual distributed optimization challenge, since the quality of the allocation for each of the agents is dependent, not only on its own allocation, but on the allocation of others as well. Thus, in order to perform distributed search for allocations with minimal envy there is a need to design innovative algorithms that can cope with the challenging constraint structure of an envy minimization problem. Distributed methods for minimizing envy among agents in indivisible resource allocation problems are presented. First, Distributed Envy Minimization Problems (DEMP) are formulated as Distributed Constraint Reasoning problems. When the DEMPs are large, and cannot be solved by a complete search an incomplete local search algorithm is presented. Each transfer of a good from one agent to another involves the change of state of more than one agent. Thus, a minimizing envy local search algorithm must build upon actions (transfers) that include multiple agents. Since DEMPs are particularly susceptible to local minima during local search, the paper proposes an algorithm that alternates between two different hill climbing search phases. The first phase uses one-transfer steps while the other exploits envy cycle elimination steps. An algorithm that minimizes envy while preserving efficiency, is proposed. The proposed algorithm finds a Pareto optimal allocation with low envy. In the context of resource allocation problems, a Pareto optimal solution is particularly desirable since it presents a stable solution. The proposed algorithm first finds a divisible Pareto optimal envy-free allocation using a Fisher market equilibrium. This allocation is transferred into an indivisible allocation of goods while maintaining the Pareto optimal characteristic of the allocation and a low envy level among agents. 相似文献
16.
为了提高虚拟环境中碰撞检测的实时性和有效性,提出了一种基于可能碰撞集的碰撞检测方法.该方法首先通过预测环境中刚体在当前帧和下一帧之间的可能运动轨迹来构建一个各边与世界坐标系各坐标轴平行,且包围该运动轨迹的包围盒;然后利用空间平铺技术来快速检测与某一平铺单元同时相交的轨迹包围盒,即可得到当前帧的可能碰撞集;接着对可能碰撞集中的刚体对进行最早碰撞时间tmin的求解,并根据tmin进行排序;最后只对具有最小tmin值的刚体对进行碰撞检测.仿真试验结果表明,与目前已有的碰撞检测算法相比,该方法简单、快速,不仅可以有效解决多个刚体环境中碰撞发生的次序问题,同时,该方法还能保证碰撞检测的完整性和唯一性.另外,理论和实践也证明了该方法的正确性和有效性. 相似文献
17.
《Journal of Symbolic Computation》2001,32(5):447-465
McCallum’s projection operator for cylindrical algebraic decomposition (CAD) represented a huge step forward for the practical utility of the CAD algorithm. This paper presents a simple theorem showing that the mathematics in McCallum’s paper actually point to a better projection operator than he proposes—a reduced McCallum projection. The reduced projection has the potential to not simply speed up CAD computation for problems that are currently solvable in practice, but actually increase the scope of problems that can realistically be attacked via CADs. Additionally, the same methods are used to show that McCallum’s projection can be reduced still further when CAD is applied to certain types of commonly occurring quantifier elimination problems. 相似文献
18.
19.
《Journal of Symbolic Computation》1999,27(5):479-499
This paper describes an algorithm for the following problem: given two multivariate complex or real polynomials f and g , decide whether there exist complex or real polynomials h and k such that both k and fh + gk have no zero in the unit polydisc. This problem, known as strong stabilizability, is fundamental in control theory, with important applications in designing stable feedback systems with a stable compensator. Our algorithm for solving the problem is formulated based on the cylindrical algebraic decomposition(cad) of an algebraic variety. While recent applications of cad to systems and control have been focused on those problems which have a quantifier elimination formulation, our method is novel in that it explicitly computes some topological properties of an algebraic variety based on the cad to solve the problem for which a quantifier elimination formulation is not readily available. 相似文献
20.
This paper considers an optimal control problem for linear hybrid automata (LHA). First, we present a controller synthesis algorithm based on reachability analysis. The algorithm computes the maximal initial set from which the controller drives the system to a given target set. It is shown that, using quantifier elimination (QE), an under-approximation of the maximal reachable set can be derived. Next, a weighted time-optimal control problem is solved by transforming it into a constrained optimization problem whose constraints are a set of inequalities with quantifiers. Quantifier elimination (QE) techniques are employed in order to derive the quantifier free inequalities that are shown to be linear. Thus, the optimal cost is obtained using linear programming. For any state belonging to the maximal initial set the optimal switching times and the optimal continuous control inputs are computed. These are used in order to derive a hybrid controller which is optimal with respect to the cost function. Our results are applied to an air traffic management example which is of practical interest. 相似文献