Parametric polynomial spectral factorization using the sum of roots and its application to a control design problem

This paper presents an algebraic approach to polynomial spectral factorization, an important mathematical tool in signal processing and control. The approach exploits an intriguing relationship between the theory of Gröbner bases and polynomial spectral factorization which can be observed through the sum of roots, and allows us to perform polynomial spectral factorization in the presence of real parameters. It is discussed that parametric polynomial spectral factorization enables us to express quantities such as the optimal cost in terms of parameters and the sum of roots. Furthermore an optimization method over parameters is suggested that makes use of the results from parametric polynomial spectral factorization and also employs two quantifier elimination techniques. This proposed approach is demonstrated in a numerical example of a particular control problem.     

An Optimizing Compiler for Parallel Chemistry Simulations

Well designed domain specific languages have three important benefits: (1) the easy expression of problems, (2) the application of domain specific optimizations (including parallelization), and (3) dramatic improvements in productivity for their users. In this paper we describe a compiler and parallel runtime system for modeling the complex kinetics of rubber vulcanization and olefin polymerization that achieves all of these goals. The compiler allows the development of a system of ordinary differential equations describing a complex vulcanization reaction or single-site olefin polymerization reaction—a task that used to require months—to be done in hours. A specialized common sub-expression elimination and other algebraic optimizations sufficiently simplify the complex machine generated code to allow it to be compiled—eliminating all but 8.0% of the operations in our largest program and enabling over 60 times faster execution on our largest benchmark codes. The parallel runtime and dynamic load balancing scheme enables fast simulations of the model.     

基于视频虚拟检测带的交通流量检测方法

交通数据的正确掌握对后续的交通控制起着至关重要的作用,采用基于视频虚拟检测带的交通流量检测方法,对检测带范围内像素点RGB的强度值进行统计,将无车辆时的统计值作为标准特征模板并执行模板更新策略,通过计算每一帧实时视频图像的特征值与标准模板特征值的距离进行车辆检测.为了提高检测精度,提出了一种基于阴影特征的阴影检测算法.在早晨和中午的不同光照条件下进行试验,在阴影明显的情况下,该方法的检测准确率在91％以上,在阴影不明显的情况下,检测准确率达到95％,可满足智能交通的需要.     

求解最小闭包球问题改进的SMO-型算法

研究n维空间中m个点的最小闭包球(MEB)问题。通过结合确定并删除内部点的技术到序列最小最优化(SMO)方法中,提出一种近似求解MEB问题的改进的SMO-型算法。证明了该算法具有线性收敛性。数值结果表明对于一些mn的大规模数据集,改进的算法与原算法相比速度可以提高10倍以上。尤其,当n等于100且m等于100000时,改进的SMO-型算法仅需执行8s。此外,对于n等于10000且m等于1000的大规模数据集,改进的算法也仅需执行150s。     

Combining intensional with extensional query evaluation in tuple independent probabilistic databases

In this paper, we prove that a query plan is safe in tuple independent probabilistic databases if and only if its every answer tuple is tree structured in probabilistic graphical models. We classify hierarchical queries into core and non-core hierarchical queries and show that the existing methods can only generate safe plans for core hierarchical queries. Inspired by the bucket elimination framework, we give the sufficient and necessary conditions for the answer relation of every candidate sub-query to be used as a base relation. Finally, the proposed algorithm generates safe plans for extensional query evaluation on non-boolean hierarchical queries and invokes the SPROUT algorithm [24] for intensional query evaluation on boolean queries. A case study on the TPC-H benchmark reveals that the safe plans of Q7 and Q8 can be evaluated efficiently. Furthermore, extensive experiments show that safe plans generated by the proposed algorithm scale well.     

An approximate duplicate elimination in RFID data streams

The RFID technology has been applied to a wide range of areas since it does not require contact in detecting RFID tags. However, due to the multiple readings in many cases in detecting an RFID tag and the deployment of multiple readers, RFID data contains many duplicates. Since RFID data is generated in a streaming fashion, it is difficult to remove duplicates in one pass with limited memory. We propose one pass approximate methods based on Bloom Filters using a small amount of memory. We first devise Time Bloom Filters as a simple extension to Bloom Filters. We then propose Time Interval Bloom Filters to reduce errors. Time Interval Bloom Filters need more space than Time Bloom Filters. We propose a method to reduce space for Time Interval Bloom Filters. Since Time Bloom Filters and Time Interval Bloom Filters are based on Bloom Filters, they do not produce false negative errors. Experimental results show that our approaches can effectively remove duplicates in RFID data streams in one pass with a small amount of memory.     

Corrected upper bounds for free-cut elimination

Free-cut elimination allows cut elimination to be carried out in the presence of non-logical axioms. Formulas in a proof are anchored provided they originate in a non-logical axiom or non-logical inference. This paper corrects and strengthens earlier upper bounds on the size of free-cut elimination. The correction requires that the notion of a free cut be modified so that a cut formula is anchored provided that all of its introductions are anchored, instead of only requiring that one of its introductions is anchored. With the correction, the originally proved size upper bounds remain unchanged. These results also apply to partial cut elimination. We also apply these bounds to elimination of cuts in propositional logic.If the non-logical inferences are closed under cut and infer only atomic formulas, then all cuts can be eliminated. This extends earlier results of Takeuti and of Negri and von Plato.     

Image reconstruction from in-line Fresnel holograms by using coherent background elimination

Image reconstruction from in-line Fresnel holograms by eliminating a coherent background is studied by computer simulation. The coherent background is calculated by averaging an intensity of a recorded hologram. The quality of the reconstructed image is measured by using a ratio of peak signal to noise. In comparison with the conventional reconstruction method, the results show that the background elimination can improve significantly the quality of the reconstructed images. The text was submitted by the authors in English.     

Fraction-free matrix factors: new forms for LU and QR factors

Gaussian elimination and LU factoring have been greatly studied from the algorithmic point of view, but much less from the point view of the best output format. In this paper, we give new output formats for fraction free LU factoring and for QR factoring. The formats and the algorithms used to obtain them are valid for any matrix system in which the entries are taken from an integral domain, not just for integer matrix systems. After discussing the new output format of LU factoring, the complexity analysis for the fraction free algorithm and fraction free output is given. Our new output format contains smaller entries than previously suggested forms, and it avoids the gcd computations required by some other partially fraction free computations. As applications of our fraction free algorithm and format, we demonstrate how to construct a fraction free QR factorization and how to solve linear systems within a given domain.     

An Efficient Output-Size Sensitive Parallel Algorithm for Hidden-Surface Removal for Terrains

We describe an efficient parallel algorithm for hidden-surface removal for terrain maps. The algorithm runs in O(log ⁴ n) steps on the CREW PRAM model with a work bound of O((n+k) \polylog ( n)) where n and k are the input and output sizes, respectively. In order to achieve the work bound we use a number of techniques, among which our use of persistent data structures is somewhat novel in the context of parallel algorithms. Received July 29, 1998; revised October 5, 1999.