Mather invariants in groups of piecewise-linear homeomorphisms

We describe the relation between two characterizations of conjugacy in groups of piecewise-linear homeomorphisms, discovered by Brin and Squier in [2] and Kassabov and Matucci in [5]. Thanks to the interplay between the techniques, we produce a simplified point of view of conjugacy that allows ua to easily recover centralizers and lends itself to generalization.

The simultaneous conjugacy problem in groups of piecewise linear functions

Guba and Sapir asked, in their joint paper [8], if the simultaneous conjugacy problem was solvable in Diagram Groups or, at least, for Thompson's group F. We give an elementary proof for the solution of the latter question. This relies purely on the description of F as the group of piecewise linear orientation-preserving homeomorphisms of the unit. The techniques we develop allow us also to solve the ordinary conjugacy problem as well, and we can compute roots and centralizers. Moreover, these techniques can be generalized to solve the same questions in larger groups of piecewise-linear homeomorphisms.

On the tractability of the piecewise-linear approximation for general discrete-choice network revenue management

The choice network revenue management (RM) model incorporates customer purchase behavioras customers purchasing products with certain probabilities that are a function of the offeredassortment of products, and is the appropriate model for airline and hotel network revenuemanagement, dynamic sales of bundles, and dynamic assortment optimization. The underlyingstochastic dynamic program is intractable and even its certainty-equivalence approximation, inthe form of a linear program called Choice Deterministic Linear Program (CDLP) is difficultto solve in most cases. The separation problem for CDLP is NP-complete for MNL with justtwo segments when their consideration sets overlap; the affine approximation of the dynamicprogram is NP-complete for even a single-segment MNL. This is in contrast to the independentclass(perfect-segmentation) case where even the piecewise-linear approximation has been shownto be tractable. In this paper we investigate the piecewise-linear approximation for network RMunder a general discrete-choice model of demand. We show that the gap between the CDLP andthe piecewise-linear bounds is within a factor of at most 2. We then show that the piecewiselinearapproximation is polynomially-time solvable for a fixed consideration set size, bringing itinto the realm of tractability for small consideration sets; small consideration sets are a reasonablemodeling tradeoff in many practical applications. Our solution relies on showing that forany discrete-choice model the separation problem for the linear program of the piecewise-linearapproximation can be solved exactly by a Lagrangian relaxation. We give modeling extensionsand show by numerical experiments the improvements from using piecewise-linear approximationfunctions.

Conjugacy of piecewise linear Lorenz map that expand on average

For piecewise linear Lorenz map that expand on average, we show that it admits a dichotomy: it is either periodic renormalizable or prime. As a result, such a map is conjugate to a ß-transformation.

Equivalence of piecewise-linear approximation and Lagrangian relaxation for network revenue management

The network revenue management (RM) problem arises in airline, hotel, media,and other industries where the sale products use multiple resources. It can be formulatedas a stochastic dynamic program but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristicshave been proposed to approximate it. Notable amongst these -both for their revenueperformance, as well as their theoretically sound basis- are approximate dynamic programmingmethods that approximate the value function by basis functions (both affinefunctions as well as piecewise-linear functions have been proposed for network RM)and decomposition methods that relax the constraints of the dynamic program to solvesimpler dynamic programs (such as the Lagrangian relaxation methods). In this paperwe show that these two seemingly distinct approaches coincide for the network RMdynamic program, i.e., the piecewise-linear approximation method and the Lagrangianrelaxation method are one and the same.

A subspace correction method for discontinuous Galerkin discretizations of linear elasticity equations

We study preconditioning techniques for discontinuous Galerkin discretizations of isotropic linear elasticity problems in primal (displacement) formulation. We propose subspace correction methods based on a splitting of the vector valued piecewise linear discontinuous finite element space, that are optimal with respect to the mesh size and the Lamé parameters. The pure displacement, the mixed and the traction free problems are discussed in detail. We present a convergence analysis of the proposed preconditioners and include numerical examples that validate the theory and assess the performance of the preconditioners.

Modeling of hybrid systems by piecewise decomposition

Piecewise linear models systems arise as mathematical models of systems in many practical applications, often from linearization for nonlinear systems. There are two main approaches of dealing with these systems according to their continuous or discrete-time aspects. We propose an approach which is based on the state transformation, more particularly the partition of the phase portrait in different regions where each subregion is modeled as a two-dimensional linear time invariant system. Then the Takagi-Sugeno model, which is a combination of local model is calculated. The simulation results show that the Alpha partition is well-suited for dealing with such a system

Renormalization and α-limit set for expanding Lorenz maps

We establish a one-to-one correspondence between the renormalizations and proper totally invariant closed sets (i.e., α-limit sets) of expanding Lorenz map, which enable us to distinguish periodic and non-periodic renormalizations. We describe the minimal renormalization by constructing the minimal totally invariant closed set, so that we can define the renormalization operator. Using consecutive renormalizations, we obtain complete topological characteriza- tion of α-limit sets and nonwandering set decomposition. For piecewise linear Lorenz map with slopes ≥ 1, we show that each renormalization is periodic and every proper α-limit set is countable.

Does urban sprawl increase the costs of providing local public services? Evidence from Spanish municipalities

This paper examines the impact of urban sprawl, a phenomenon of particular interest in Spain, which is currently experiencing this process of rapid, low-density urban expansion. Many adverse consequences are attributed to urban sprawl (e.g., traffic congestion, air pollution and social segregation), though here we are concerned primarily with the rising costs of providing local public services. Our initial aim is to develop an accurate measure of urban sprawl so that we might empirically test its impact on municipal budgets. Then, we undertake an empirical analysis using a cross-sectional data set of 2,500 Spanish municipalities for the year 2003 and a piecewise linear function to account for the potentially nonlinear relationship between sprawl and local costs. The estimations derived from the expenditure equations for both aggregate and six disaggregated spending categories indicate that low-density development patterns lead to greater provision costs of local public services.

Dynamics in Thompson's group F

We describe an explicit relationship between strand diagrams and piecewise-linear functions for elements of Thompson’s group F. Using this correspondence, we investigate the dynamics of elements of F, and we show that conjugacy of one-bump functions can be described by a Mather-type invariant.

Stabilized Petrov-Galerkin methods for the convection-diffusion-reaction and the Helmholtz equations

We present two new stabilized high-resolution numerical methods for the convection–diffusion–reaction (CDR) and the Helmholtz equations respectively. The work embarks upon a priori analysis of some consistency recovery procedures for some stabilization methods belonging to the Petrov–Galerkin framework. It was found that the use of some standard practices (e.g. M-Matrices theory) for the design of essentially non-oscillatory numerical methods is not feasible when consistency recovery methods are employed. Hence, with respect to convective stabilization, such recovery methods are not preferred. Next, we present the design of a high-resolution Petrov–Galerkin (HRPG) method for the 1D CDR problem. The problem is studied from a fresh point of view, including practical implications on the formulation of the maximum principle, M-Matrices theory, monotonicity and total variation diminishing (TVD) finite volume schemes. The current method is next in line to earlier methods that may be viewed as an upwinding plus a discontinuity-capturing operator. Finally, some remarks are made on the extension of the HRPG method to multidimensions. Next, we present a new numerical scheme for the Helmholtz equation resulting in quasi-exact solutions. The focus is on the approximation of the solution to the Helmholtz equation in the interior of the domain using compact stencils. Piecewise linear/bilinear polynomial interpolation are considered on a structured mesh/grid. The only a priori requirement is to provide a mesh/grid resolution of at least eight elements per wavelength. No stabilization parameters are involved in the definition of the scheme. The scheme consists of taking the average of the equation stencils obtained by the standard Galerkin finite element method and the classical finite difference method. Dispersion analysis in 1D and 2D illustrate the quasi-exact properties of this scheme. Finally, some remarks are made on the extension of the scheme to unstructured meshes by designing a method within the Petrov–Galerkin framework.

Mutigrid preconditioner for nonconforming discretization of elliptic problems with jump coefficients

In this paper, we present a multigrid preconditioner for solving the linear system arising from the piecewise linear nonconforming Crouzeix-Raviart discretization of second order elliptic problems with jump coe fficients. The preconditioner uses the standard conforming subspaces as coarse spaces. Numerical tests show both robustness with respect to the jump in the coe fficient and near-optimality with respect to the number of degrees of freedom.

Implementing interactive computing in an object-oriented environment

Statistical computing when input/output is driven by a Graphical User Interface is considered. A proposal is made for automatic control ofcomputational flow to ensure that only strictly required computationsare actually carried on. The computational flow is modeled by a directed graph for implementation in any object-oriented programming language with symbolic manipulation capabilities. A complete implementation example is presented to compute and display frequency based piecewise linear density estimators such as histograms or frequency polygons.

Non-Linear and Non-Conventional Speech Processing: Alternative Techniques

This special issue aims to cover some problems related to non-linear and nonconventional speech processing. The origin of this volume is in the ISCA Tutorial and Research Workshop on Non-Linear Speech Processing, NOLISP’09, held at the Universitat de Vic (Catalonia, Spain) on June 25–27, 2009. The series of NOLISP workshops started in 2003 has become a biannual event whose aim is to discuss alternative techniques for speech processing that, in a sense, do not fit into mainstream approaches. A selected choice of papers based on the presentations delivered at NOLISP’09 has given rise to this issue of Cognitive Computation.

Source separation techniques applied to linear prediction

The prediction filters are well known models for signal estimation, in communications, control and many others areas. The classical method for deriving linear prediction coding (LPC) filters is often based on the minimization of a mean square error (MSE). Consequently, second order statistics are only required, but the estimation is only optimal if the residue is independent and identically distributed (iid) Gaussian. In this paper, we derive the ML estimate of the prediction filter. Relationships with robust estimation of auto-regressive (AR) processes, with blind deconvolution and with source separation based on mutual information minimization are then detailed. The algorithm, based on the minimization of a high-order statistics criterion, uses on-line estimation of the residue statistics. Experimental results emphasize on the interest of this approach.