16410515
Finding roots of unity among quotients of the roots of an integral polynomial
We present an efficient algorithm for testing whether a given integral polynomial has two distinct roots a, B such that fflp is a root of unity. The test is based on results obtained by investigation of the structure of the splitting field of the polynomial. By this investigate ion, we found also an improved bound for the least common multiple of the orders of roots of unity appearing as quotients of distinct roots.
6468095
Factoring systems of linear PDEs with finite-dimensional solution spaces
A D-finite system is a finite set of linear homogeneous partial differential equations in several independent and dependent variables, whose solution space is of finite dimension. Let L be a D-finite system with rational function coefficients. We present an algorithm for computing all hyperexponential solutions of L, and an algorithm for computing all D-finite systems whose coefficients are also rational functions, and whose solutions are contained in the solution space of L.
6081722
Factoring zero-dimensional ideals of linear partial differential operators
We present an algorithm for factoring a zero-dimensional left ideal in the ring <b>Q</b>(<i>x, y</i>) [∂<inf><i>x</i></inf>, ∂<inf><i>y</i></inf>], i.e. factoring a linear homogeneous partial differential system whose coefficients belong to <b>Q</b>(<i>x, y</i>), and whose solution space is finite-dimensional over <b>Q.</b> The algorithm computes all the zero-dimensional left ideals containing the given ideal. It generalizes the Beke-Schlesinger algorithm for factoring linear ordinary differential operators, and uses an algorithm for finding hyperexponential solutions of such ideals.
2931347
Rational Solutions of Riccati-like Partial Differential Equations
When factoring linear partial differential systems with a finite-dimensional solution space or analysing symmetries of nonlinear ODEs, we need to look for rational solutions of certain nonlinear PDEs. The nonlinear PDEs are called Riccati-like because they arise in a similar way as Riccati ODEs. In this paper we describe the structure of rational solutions of a Riccati-like system, and an algorithm for computing them. The algorithm is also applicable to finding all rational solutions of Lie?s system { ?xu+u2+a1u+a2v+a3, ?yu+uv+b1u+b2v+b3, ?xv+uv+c1u+c2v+c3, ?yv+v2+d1u+d2v+d3},where a1, . . . , d3are rational functions of x and y.
15151643
QMBF: a QoS-aware multicast routing protocol
Many multicast applications, such as video-on-demand and tele-education, desire quality of service (QoS) support from the underlying network. Recently, many QoS-based multicast protocols have been proposed to meet this requirement. However, few of them can achieve high success ratios while maintaining good scalability. In this paper, we propose a new QoS-aware multicast protocol based on a bounded flooding technique (QMBF). In this protocol, every network node maintains the knowledge of a local network cell (LNC) topology as well as QoS state information (collected from the bounded flooding messages). QMBF utilizes this knowledge to increase the probability and accuracy of finding a feasible branch which connects a new member to an existing multicast tree. The protocol exploits two approaches to find feasible branches: repeatedly computing partial feasible branches using the LNC information and searching multiple paths. The design of QMBF allows it to operate on top of any unicast routing protocol or cooperate with a QoS-based unicast routing protocol. Results obtained using NS-2 simulator demonstrate high success ratio for locating feasible branches for multicast paths.
12665870
Robust statistical methods for securing wireless localization in sensor networks
Many sensor applications are being developed that require the location of wireless devices, and localization schemes have been developed to meet this need. However, as location-based services become more prevalent, the localization infrastructure will become the target of malicious attacks. These attacks will not be conventional security threats, but rather threats that adversely affect the ability of localization schemes to provide trustworthy location information. This paper identifies a list of attacks that are unique to localization algorithms. Since these attacks are diverse in nature, and there may be many unforeseen attacks that can bypass traditional security countermeasures, it is desirable to alter the underlying localization algorithms to be robust to intentionally corrupted measurements. In this paper, we develop robust statistical methods to make localization attack-tolerant. We examine two broad classes of localization: triangulation and RF-based fingerprinting methods. For triangulation-based localization, we propose an adaptive least squares and least median squares position estimator that has the computational advantages of least squares in the absence of attacks and is capable of switching to a robust mode when being attacked. We introduce robustness to fingerprinting localization through the use of a median-based distance metric. Finally, we evaluate our robust localization schemes under different threat conditions.
6048187
Fast video shot retrieval by trace geometry matching in principal component space
Content-based video retrieval technology holds the key to the efficient management and sharing of video content from different sources, in different scales, across different platforms, and shared over different communication channels. In this work we present a fast retrieval algorithm based on matching the geometry of video sequence traces in the principal component space. Techniques to address scale (spatial and temporal) issues, as well as, noise and other possible distortions, such as frame dropping, are discussed. Experimental results demonstrate the effectiveness of the proposed approach.
1327847
On achieving maximum multicast throughput in undirected networks
The transmission of information within a data network is constrained by the network topology and link capacities. In this paper, we study the fundamental upper bound of information dissemination rates with these constraints in undirected networks, given the unique replicable and encodable properties of information flows. Based on recent advances in network coding and classical modeling techniques in flow networks, we provide a natural linear programming formulation of the maximum multicast rate problem. By applying Lagrangian relaxation on the primal and the dual linear programs (LPs), respectively, we derive a) a necessary and sufficient condition characterizing multicast rate feasibility, and b) an efficient and distributed subgradient algorithm for computing the maximum multicast rate. We also extend our discussions to multiple communication sessions, as well as to overlay and ad hoc network models. Both our theoretical and simulation results conclude that, network coding may not be instrumental to achieve better maximum multicast rates in most cases; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality.
31862696
Basic Topological Models for Spatial Entities in 3-Dimensional Space
In recent years, models of spatial relations, especially topological relations, have attracted much attention from the GIS community. In this paper, some basic topologic models for spatial entities in both vector and raster spaces are discussed.It has been suggested that, in vector space, an open set in 1-D space may not be an open set any more in 2-D and 3-D spaces. Similarly, an open set in 2-D vector space may also not be an open set any more in 3-D vector spaces. As a result, fundamental topological concepts such as boundary and interior are not valid any more when a lower dimensional spatial entity is embedded in higher dimensional space. For example, in 2-D, a line has no interior and the line itself (not its two end-points) forms a boundary. Failure to recognize this fundamental topological property will lead to topological paradox. It has also been stated that the topological models for raster entities are different in Z2 and R2. There are different types of possible boundaries depending on the definition of adjacency or connectedness. If connectedness is not carefully defined, topological paradox may also occur. In raster space, the basic topological concept in vector space—connectedness—is implicitly inherited. This is why the topological properties of spatial entities can also be studied in raster space. Study of entities in raster (discrete) space could be a more efficient method than in vector space, as the expression of spatial entities in discrete space is more explicit than that in connected space.