Efficient Parallel Computation of the Characteristic Polynomial of a Sparse, Separable Matrix

{This paper is concerned with the problem of computing the characteristic polynomial of a matrix. In a large number of applications, the matrices are symmetric and sparse : with O(n) non-zero entries. The problem has an efficient sequential solution in this case, requiring O(n ² ) work by use of the sparse Lanczos method. A major remaining open question is: to find a polylog time parallel algorithm with matching work bounds. Unfortunately, the sparse Lanczos method cannot be parallelized to faster than time Ω (n) using n processors. Let M(n) be the processor bound to multiply two n \times n matrices in O(log n) parallel time. Giesbrecht [G2] gave the best previous polylog time parallel algorithms for the characteristic polynomial of a dense matrix with O (M(n)) processors. There is no known improvement to this processor bound in the case where the matrix is sparse. Often, in addition to being symmetric and sparse, the matrix has a sparsity graph (which has edges between indices of the matrix with non-zero entries) that has small separators. This paper gives a new algorithm for computing the characteristic polynomial of a sparse symmetric matrix, assuming that the sparsity graph is s(n) -separable and has a separator of size s(n)=O(n ^γ ) , for some γ , 0 < γ < 1 , that when deleted results in connected components of ≤α n vertices, for some 0 < α < 1 , with the same property. We derive an interesting algebraic version of Nested Dissection, which constructs a sparse factorization of the matrix A-λ I _n where A is the input matrix and I _n is the n \times n identity matrix. While Nested Dissection is commonly used to minimize the fill-in in the solution of sparse linear systems, our innovation is to use the separator structure to bound also the work for manipulation of rational functions in the recursively factored matrices. The matrix elements are assumed to be over an arbitrary field. We compute the characteristic polynomial of a sparse symmetric matrix in polylog time using P(n)(n+M(s(n))) ≤ P(n)(n+ s(n) ^2.376 ) processors, where P(n) is the processor bound to multiply two degree n polynomials in O(log n) parallel time using a PRAM (P(n) = O(n) if the field supports an FFT of size n but is otherwise O(nlog log n) [CK]. Our method requires only that a matrix be symmetric and non-singular (it need not be positive definite as usual for Nested Dissection techniques). For the frequently occurring case where the matrix has small separator size, our polylog parallel algorithm has work bounds competitive with the best known sequential algorithms (i.e., the Ω(n ² ) work of sparse Lanczos methods), for example, when the sparsity graph is a planar graph, s(n) ≤ O( \sqrt n ) , and we require polylog time with only P(n)n ^1.188 processors. } Received September 26, 1997; revised June 5, 1999.     

一种高效的最短路径树动态更新算法

计算动态环境下最短路径树是一个典型的组合优化问题。Ba11-and-String模型是一种高效的动态更新算法,但仍存在不少冗余计算。针对Ba11-and-String算法中边的处理进行了优化,从而提高了动态更新的效率,同时实现了对节点的删除和增加,以适应最短路径树的拓扑变化。实验结果表明新算法效率更高。     

广义可能性计算树逻辑和计算树逻辑的关系

广义可能性计算树逻辑(generalized possibilistic computation tree logic,GPo CTL)在不确定性模型检测中扮演着非常重要的角色,但其表达能力还尚未研究全面。为此,讨论了GPo CTL与计算树逻辑(computation tree logic,CTL)表达能力之间的关系。首先定义了区间广义可能性计算树逻辑(interval generalized pos-sibilistic computation tree logic,IGPo CTL),并给出了IGPo CTL公式和CTL公式等价的定义。然后证明了CTL是IGPo CTL的一个真子类,因为IGPo CTL是GPo CTL的一种简单分明化形式,则CTL可看作GPo CTL的一个真子类。此外,还给出了IGPo CTL公式和CTL公式α-等价的定义,并得出了一些更一般的结果。     

Computation of Approximate Polynomial GCDs and an Extension

Computation of approximate polynomial greatest common divisors (GCDs) is important both theoretically and due to its applications to control linear systems, network theory, and computer-aided design. We study two approaches to the solution so far omitted by the researchers, despite intensive recent work in this area. Correlation to numerical Padé approximation enabled us to improve computations for both problems (GCDs and Padé). Reduction to the approximation of polynomial zeros enabled us to obtain a new insight into the GCD problem and to devise effective solution algorithms. In particular, unlike the known algorithms, we estimate the degree of approximate GCDs at a low computational cost, and this enables us to obtain certified correct solution for a large class of input polynomials. We also restate the problem in terms of the norm of the perturbation of the zeros (rather than the coefficients) of the input polynomials, which leads us to the fast certified solution for any pair of input polynomials via the computation of their roots and the maximum matchings or connected components in the associated bipartite graph.     

非精确任务集的容错单调比率调度

Meeting deadline and geting high throughput are the main objective of real-time system.They are both important,but sometimes incompatible,such as reserving resource for fault tolerance.We describe a new scheme,through making use of the fualt-tolerant rate-monotonic scheduling and imprecise computation,a real-time system can get high throughput when operating normally and can meet the deadline of critical tasks when there are one or more transient error.     

非精确任务集的容错EDF调度

该文将容错EDF调度算法和非精确计算技术结合起来,提高了算法的调度性能,使单处理器系统正常运行时具有高吞吐量,同时,在出现一个或多个偶发性软件错误时,仍能满足系统中关键任务的时限要求。     

静态优先级实时任务的多项式时间近似分析

经典的硬实时任务响应时间分析及其各种基于初始值的递归改进无法适用交互的实时设计环境.高效的近似分析方法是一种有效的选择,提出能高效计算任务最差响应时间上限的方法并给出与精确调度的误差量化分析,定义响应时间分析的线性近似请求约束函数并由此提出一个具有ε参数多项式时间复杂度的死线约束分析方法.针对死线约束分析方法本文将采用经典的近似比率技术和资源增值技术来分析该方法所提供的性能保证的程度.随机任务集的相关实验证明了所提出近似方法的有效性.     

Computation of the Resonance Set of a Polynomial under Constraints on Its Coefficients

Programming and Computer Software - Methods for computing the generalized discriminant set of a polynomial the roots of which satisfy a linear relation are considered. Using a q-analog of the...     

Computation of All Polynomial Solutions of a Class of Nonlinear Differential Equations

A class of nonlinear differential equations is considered. We show that all their polynomial solutions can be computed in a systematic manner. Implementation of our method is also illustrated by means of Maple programs.     

Efficient Computation of the Euclidean Distance Transform

We present a simple algorithm for the Euclidean distance transform of a binary image that runs more efficiently than other algorithms in the literature. We show that our algorithm runs in optimal time for many architectures and has optimal cost for the RAM and EREW PRAM.     

Reliable and Efficient Computation of Optical Flow

In this paper, we present two very efficient and accurate algorithms for computing optical flow. The first is a modified gradient-based regularization method, and the other is an SSD-based regularization method. For the gradient-based method, to amend the errors in the discrete image flow equation caused by numerical differentiation as well as temporal and spatial aliasing in the brightness function, we propose to selectively combine the image flow constraint and a contour-based flow constraint into the data constraint by using a reliability measure. Each data constraint is appropriately normalized to obtain an approximate minimum distance (of the data point to the linear flow equation) constraint instead of the conventional linear flow constraint. These modifications lead to robust and accurate optical flow estimation. We propose an incomplete Cholesky preconditioned conjugate gradient algorithm to solve the resulting large and sparse linear system efficiently. Our SSD-based regularization method uses a normalized SSD measure (based on a similar reasoning as in the gradient-based scheme) as the data constraint in a regularization framework. The nonlinear conjugate gradient algorithm in conjunction with an incomplete Cholesky preconditioning is developed to solve the resulting nonlinear minimization problem. Experimental results on synthetic and real image sequences for these two algorithms are given to demonstrate their performance in comparison with competing methods reported in literature.     

Symbolic Computation on Complex Polynomial Solution of Differential Equations

A symbolic computation scheme, based on the Lanczos τ-method, is proposed for obtaining exact polynomial solutions to some perturbed differential equations with suitable boundary conditions. The automated τ-method uses symbolic Faber polynomials as the perturbation terms for arbitrary circular sections of the complex plane and has advantages of avoiding rounding error and easy manipulation over the numerical counterpart. The method is illustrated by applying it to the modified Bessel function of the first kindI₀(z) and the quality of the approximation is discussed.     

Exact Computation of Polynomial Zeros Expressible by Square Roots

In this paper we give an efficient algorithm to find symbolically correct zeros of a polynomial f ∈ R[X] which can be represented by square roots. R can be any domain if a factorization algorithm over R[X] is given, including finite rings or fields, integers, rational numbers, and finite algebraic or transcendental extensions of those. Asymptotically, the algorithm needs O(T_f(d²)) operations in R, where T_f(d) are the operations for the factorization algorithm over R[X] for a polynomial of degree d. Thus, the algorithm has polynomial running time for instance for polynomials over finite fields or the rationals. We also present a quick test for deciding whether a given polynomial has zeros expressible by square roots and describe some additional methods for special cases.     

Efficient Computation of Smoothed Exponential Maps

Many applications in geometry processing require the computation of local parameterizations on a surface mesh at interactive rates. A popular approach is to compute local exponential maps, i.e. parameterizations that preserve distance and angle to the origin of the map. We extend the computation of geodesic distance by heat diffusion to also determine angular information for the geodesic curves. This approach has two important benefits compared to fast approximate as well as exact forward tracing of the distance function: First, it allows generating smoother maps, avoiding discontinuities. Second, exploiting the factorization of the global Laplace–Beltrami operator of the mesh and using recent localized solution techniques, the computation is more efficient even compared to fast approximate solutions based on Dijkstra's algorithm.     

高效安全向量计算及其推广

安全多方计算是密码学的一个重要研究方向,也是目前国际密码学界的研究热点.因为许多实际问题都可以用向量来描述,研究向量的保密计算具有重要的理论与实际意义.目前,关于向量保密计算问题大多是在整数集上进行研究,关于有理数向量问题的研究很少.在此主要研究有理数域上向量的安全多方计算问题,包括向量点积、向量相等、向量优势等问题,设计了安全高效的计算协议,扩大了向量保密计算的应用范围.对这些协议的安全性分析和效率分析表明,它们在安全性和效率方面与现有协议相比具有明显优势.并且利用所设计的协议解决了一些新的向量问题和计算几何问题.     

计算树逻辑特性模式研究

模型检查是系统验证的有效方法,在验证过程中需要对系统待检验特性用时态逻辑公式进行刻画,然后在模型检查工具中进行检验。介绍计算树逻辑的语法及语义,根据计算树逻辑中特性模式的划分及作用范围给出计算树逻辑常见的特性模式,包括缺失性模式、存在性模式、普遍性模式、优先性模式和跟随性模式等。     

加强局部简便计算的点在多边形内的高效判定

点在多边形内的检测是计算几何中的一个基本问题,有着广泛的应用需求。已提 出许多方法减少要测试的多边形的边以加速。其中,均匀网格法具有很好的作用,因为各网格 中的边很少,而测试点可迅即定位于一个网格。我们曾提出一种均匀网格法,预计算各网格中 心点位于多边形内/外的属性,然后将测试点与所在网格的中心点连线,检测该连线与多边形的 边的相交情况即可。其预处理和检测的复杂度分别为 O(N)和 O( N ),N 为多边形的边数。本 文在此基础上进一步改进,预计算网格交点位于多边形内/外的属性,然后将测试点与其邻近网 格交点的连线,转换为与坐标轴平行的两条相连直线段,以提高与多边形边求交计算的便捷性。 实验结果表明,可将检测速度提高 2 倍多。     

Efficient Stack Distance Computation for a Class of Priority Replacement Policies

The Linear-Scan algorithm (1970), applicable to priority replacement policies, computes stack distances and the number of misses incurred on a given address trace, for all cache sizes, in time O(V) per access. Here, V is the number of distinct (virtual) items referenced within the trace. While the time bound was subsequently lowered to O(log V) for the Least Recently Used policy, no improvements have been reported for general priority policies. This work introduces the class of policies with nearly static priorities (NSP), which encompasses several known policies. The Min-Tree algorithm is proposed for NSP policies, whose performance is quite sensitive to the policy as well as to the address trace. Under suitable probabilistic assumptions, the expected time per access is O(log² V). Experimental evidence collected on a mix of 30 benchmarks shows that the Min-Tree algorithm can be significantly faster than Linear-Scan, for interesting policies such as OPT (or Belady), Least Frequently Used (LFU), and Most Recently Used (MRU). Min-Tree can be parallelized to run in time O(log V) using O(V/log V) processors, in the worst case. A more sophisticated Lazy Min-Tree algorithm is also developed with ${O(\sqrt{V}\log V)}$ worst-case time per access. This bound applies, in particular, to the policies OPT, LFU, and Least Recently/Frequently Used (LRFU), for which the best previously known bound was O(V). Although random replacement is not an NSP policy, the framework developed in this work leads to a stack-distance algorithm with O(log V) expected time per access.