Stability and nonsingular stable precompensation: An algebraic approach

The module theoretic framework in linear time invariant system theory is extended to include stability considerations as well. The resulting setup is then applied to an investigation of nonsingular, causal, and stable precompensation. The main issues are resolved through the introduction of two sets of integer invariants-thestability indices and thepole indices. The stability indices characterize the dynamical properties of all the stable systems that can be obtained from a specified system through the application of nonsingular, causal, and stable precompensation. The pole indices characterize the dynamical properties of all the nonsingular, causal, and stable precompensators that stabilize a specified system.     

A delineability-based method for computing critical sets of algebraic surfaces

In this paper, we address the problem of determining a real finite set of z$z$-values where the topology type of the level curves of a (maybe singular) algebraic surface may change. We use as a fundamental and crucial tool McCallum’s theorem on analytic delineability of polynomials (see [McCallum, S., 1998. An improved projection operation for cylindrical algebraic decomposition. In: Caviness, B.F., Johnson, J.R. (Eds.), Quantifier Elimination and Cylindrical Algebraic Decomposition. Springer Verlag, pp. 242–268]). Our results allow to algorithmically compute this finite set by analyzing the real roots of a univariate polynomial; namely, the double discriminant of the implicit equation of the surface. As a consequence, an application to offsets is shown.     

Reduction of stable differential–algebraic equation systems via projections and system identification

Most large-scale process models derived from first principles are represented by nonlinear differential–algebraic equation (DAE) systems. Since such models are often computationally too expensive for real-time control, techniques for model reduction of these systems need to be investigated. However, models of DAE type have received little attention in the literature on nonlinear model reduction. In order to address this, a new technique for reducing nonlinear DAE systems is presented in this work. This method reduces the order of the differential equations as well as the number and complexity of the algebraic equations. Additionally, the algebraic equations of the resulting system can be replaced by an explicit expression for the algebraic variables such as a feedforward neural network. This last property is important insofar as the reduced model does not require a DAE solver for its solution but system trajectories can instead be computed with regular ODE solvers. This technique is illustrated with a case study where responses of several different reduced-order models of a distillation column with 32 differential equations and 32 algebraic equations are compared.     

Non-local isotopic approximation of nonsingular surfaces

We consider the problem of approximating nonsingular surfaces which are implicitly represented by equations of the form $f(x,y,z)=0$. Our correctness criterion is an isotopy of the approximate surface to the exact surface. We focus on methods based on domain subdivision using numerical primitives. Such methods are practical and have adaptive and local complexity. Previously, Snyder (1992) [3] and Plantinga-Vegter (2004) [4] have introduced techniques based on parameterizability and non-local isotopy, respectively. In our previous work (SoCG 2009), we synthesized these two techniques into an efficient and practical algorithm for curves. This paper extends our approach to surfaces. The extension is by no means routine: the correctness argument is much more intricate. Unlike the 2-D case, a new phenomenon arises in which local rules for constructing surfaces are no longer sufficient.We treat an important extension to exploit anisotropic subdivision. Anisotropy means that we allow boxes to be split into 2, 4 or 8 subboxes with arbitrary but bounded aspect ratio. This could greatly improve the adaptivity of the algorithm.Our algorithms are relatively easy to implement, as the underlying primitives are based on interval arithmetic and exact BigFloat numbers. We report on encouraging preliminary experimental results.     

Rasterizing algebraic curves and surfaces

A new, recursive, space-subdivision algorithm for rasterizing algebraic curves and surfaces gets its accuracy from a newly devised, computationally efficient, and asymptotically correct test. The approach followed is essentially the interval arithmetic method for rendering implicit curves. The author's contribution is a particularly efficient way to construct inclusion functions for polynomials. An ideal algorithm is given for rendering an algebraic curve Z(f)={(x,y):f(x,y)=0} in a square box of side n. The algorithm scans the square and paints only those pixels cut by the curve. This algorithm is ideal, because every correct algorithm should paint exactly the same pixels, but it is impractical. It requires n² test evaluations, one for each pixel in the square. However, since in general it will be rendering a curve on a planar region, the number of pixels it is expected to paint is only O(n). We need a more efficient algorithm. There are two issues to examine. The first is how to reduce the computational complexity by recursive subdivision. The second is how to test whether the curve Z(f) cuts a square     

Safe projections of binary data sets

Selectivity estimation of a boolean query based on frequent itemsets can be solved by describing the problem by a linear program. However, the number of variables in the equations is exponential, rendering the approach tractable only for small-dimensional cases. One natural approach would be to project the data to the variables occurring in the query. This can, however, change the outcome of the linear program.We introduce the concept of safe sets: projecting the data to a safe set does not change the outcome of the linear program. We characterise safe sets using graph theoretic concepts and give an algorithm for finding minimal safe sets containing given attributes. We describe a heuristic algorithm for finding almost-safe sets given a size restriction, and show empirically that these sets outperform the trivial projection.We also show a connection between safe sets and Markov Random Fields and use it to furtherreduce the number of variables in the linear program, given some regularity assumptions on the frequent itemsets.     

Quotients and weakly algebraic sets in pseudoeffect algebras

In the paper, we show that the quotient [E]_I[E]_I of a lattice-ordered pseudoeffect algebra EE with respect to a normal weak Riesz ideal II is linearly ordered if and only if II is a prime normal weak Riesz ideal, and [E]_I[E]_I is a representable pseudo MV-algebra if and only if II is an intersection of prime normal weak Riesz ideals. Moreover, we introduce the concept of weakly algebraic sets in pseudoeffect algebras, discuss the characterizations of weakly algebraic sets and show that weakly algebraic sets in pseudoeffect algebra EE are in a one-to-one correspondence with normal weak Riesz ideals in pseudoeffect algebra E.E.     

Real-time ray casting of algebraic B-spline surfaces

Piecewise algebraic B-spline surfaces (ABS surfaces) are capable of modeling globally smooth shapes of arbitrary topology. These can be potentially applied in geometric modeling, scientific visualization, computer animation and mathematical illustration. However, real-time ray casting the surface is still an obstacle for interactive applications, due to the large amount of numerical root findings of nonlinear polynomial systems that are required. In this paper, we present a GPU-based real-time ray casting method for ABS surfaces. To explore the powerful parallel computing capacity of contemporary GPUs, we adopt iterative numerical root-finding algorithms, e.g., the Newton-Raphson and regula falsi algorithms, rather than recursive ones. To facilitate convergence of the Newton-Raphson or regula falsi algorithm, their initial guesses are determined through rasterization of the isotopic isosurface, and the isosurface is generated based on regular criteria for surface domain subdivision. Meanwhile, polar surfaces are adopted to identify single roots or to isolate different roots, i.e., ray and surface intersections. As an important geometric feature, the silhouette curve is elaborately computed to floating-point accuracy, which can be applied in further anti-aliasing processes. The experimental results show that the proposed method can render thousands of piecewise algebraic surface patches of degrees 6-9 in real time.     

Extreme simplification and rendering of point sets using algebraic multigrid

We present a novel approach for extreme simplification of point set models, in the context of real-time rendering. Point sets are often rendered using simple point primitives, such as oriented discs. However, this requires using many primitives to render even moderately simple shapes. Often, one wishes to render a simplified model using only a few primitives, thus trading accuracy for simplicity. For this goal, we propose a more complex primitive, called a splat, that is able to approximate larger and more complex surface areas than oriented discs. We construct our primitive by decomposing the model into quasi-flat regions, using an efficient algebraic multigrid algorithm. Next, we encode these regions into splats implemented as planar support polygons textured with color and transparency information and render the splats using a special blending algorithm. Our approach combines the advantages of mesh-less point-based techniques with traditional polygon-based techniques. We demonstrate our method on various models.     

A fast and stable facial interface using integral projections

Integral projections are a useful technique in many computer vision problems. In this paper, we present a perceptual interface which allows us to navigate through a virtual 3D world by using the movements of the face of human users. The system applies advanced computer vision techniques to detect, track, and estimate the pose of the user’s head. The core of the proposed approach consists of a face tracker, which is based on the computation, alignment, and analysis of integral projections. This technique provides a robust, accurate, and stable 2D location of the face in each frame of the input video. Then, 3D location and orientation of the head are estimated, using some predefined heuristics. Finally, the resulting 3D pose is transformed into control signals for the navigation in the virtual world. The proposed approach has been implemented and tested in a prototype, which is publicly available. Some experimental results are shown, proving the feasibility of the method. The perceptual interface is fast, stable, and robust to facial expression and illumination conditions.     

On the algebraic characterization of invariant sets of switched linear systems

In this paper, a suitable LaSalle principle for continuous-time linear switched systems is used to characterize invariant sets and their associated switching laws. An algorithm to determine algebraically these invariants is proposed. The main novelty of our approach is that we require no dwell time conditions on the switching laws. By not focusing on restricted control classes we are able to describe the asymptotic properties of the considered switched systems. Observability analysis of a flying capacitor converter is proposed as an illustration.     

Representation of piecewise continuous algebraic surfaces in terms of B-splines

A method for representing shape using portions of algebraic surfaces bounded by rectangular boxes defined in terms of triple product Bernstein polynomials is described and some of its properties are outlined. The method is extended to handle piecewise continuous algebraic surfaces within rectangular boxes defined in terms of triple products of B-spline basis functions. Next, two techniques for sculptured shape creation are studied. The first is based on geometric manipulation of existing primitives and the second on approximation/interpolation of lower dimensional entities using least-squares techniques based on singular value decomposition. In addition, several interrogation techniques, such as contouring, ray tracing and curvature evaluation, used in the design and analysis of piecewise continuous algebraic surfaces are discussed.     

Good local behavior of offsets to rational regular algebraic surfaces

Local information on the shape of a regular surface is provided by the well-known notions in Differential Geometry of elliptic, parabolic and hyperbolic points. Here, we provide algorithms to check that, for a given distance, the offsetting process does not introduce relevant local changes in the shape of a surface, under the hypothesis that the surface is described by means of a rational, regular, real parametrization. Also, we provide algorithms for computing intervals of distances with this nice property.     

Missing sets in rational parametrizations of surfaces of revolution

Parametric representations do not cover, in general, the whole geometric object that they parametrize. This can be a problem in practical applications. In this paper we analyze the question for surfaces of revolution generated by real rational profile curves, and we describe a simple small superset of the real zone of the surface not covered by the parametrization. This superset consists, in the worst case, of the union of a circle and the mirror curve of the profile curve.     

Global analyses of crisis and stochastic bifurcation in the hardening Helmholtz-Duffing oscillator

Crisis and stochastic bifurcation of the hardening Helmholtz-Duffing oscillator are studied by means of the generalized cell mapping method using digraph.For the system subject to a single deterministic harmonic excitation,our study reveals that a series of crisis phenomena can occur when the system parameter passes through different critical values,including chaotic boundary crisis,regular boundary crisis and interior crisis.A chaotic boundary crisis due to the collision of regular attractor with chaotic s...     

The enumerative geometry of projective algebraic surfaces and the complexity of aspect graphs

The aspect graph is a popular viewer-centered representation that enumerates all the topologically distinct views of an object. Building the aspect graph requires partitioning viewpoint space in view-equivalent cells by a certain number of visual event surfaces. If the object is piecewise-smooth algebraic, then all visual event surfaces are either made of lines having specified contacts with the object or made of lines supporting the points of contacts of planes having specified contacts with the object. In this paper, we present a general framework for studying the enumerative properties of line and plane systems. The context is that of enumerative geometry and intersection theory. In particular, we give exact results for the degrees of all visual event surfaces coming up in the construction of aspect graphs of piecewise-smooth algebraic bodies. We conclude by giving a bound on the number of topologically distinet views of such objects.This work was supported by a fellowship from the Ministry of Higher Education and Research of France.     

Irreducible decomposition of algebraic varieties via characteristics sets and Gröbner bases

This paper presents a method for decomposing algebraic varieties into irreducible components by using characteristic sets and Gröbner bases. A set of 16 examples is provided to explain the geometric meaning of the irreducible decomposition and as a test bed for our experiments with the method. A function that implements the presented method has been included in the author's characteristic sets package in the Maple system and used to decompose a number of non-trivial algebraic varieties. A few strategies adopted in our implementation and the timing statistics for the 16 test examples are given.     

Visual exploration of large relational data sets through 3D projections and footprint splatting

This paper discusses 3D visualization and interactive exploration of large relational data sets through the integration of several well-chosen multidimensional data visualization techniques and for the purpose of visual data mining and exploratory data analysis. The basic idea is to combine the techniques of grand tour, direct volume rendering, and data aggregation in databases to deal with both the high dimensionality of data and a large number of relational records. Each technique has been enhanced or modified for this application. Specifically, positions of data clusters are used to decide the path of a grand tour. This cluster-guided tour makes intercluster-distance-preserving projections in which data clusters are displayed as separate as possible. A tetrahedral mapping method applied to cluster centroids helps in choosing interesting cluster-guided projections. Multidimensional footprint splatting is used to directly render large relational data sets. This approach abandons the rendering techniques that enhance 3D realism and focuses on how to efficiently produce real-time explanatory images that give comprehensive insights into global features such as data clusters and holes. Examples are given where the techniques are applied to large (more than a million records) relational data sets.