Search results for "DECOMPOSITION"

Incremental bipartite drawing problem

2001

Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…

Using the witness method to detect rigid subsystems of geometric constraints in CAD

2010

International audience; This paper deals with the resolution of geometric constraint systems encountered in CAD-CAM. The main results are that the witness method can be used to detect that a constraint system is over-constrained and that the computation of the maximal rigid subsystems of a system leads to a powerful decomposition method. In a first step, we recall the theoretical framework of the witness method in geometric constraint solving and extend this method to generate a witness. We show then that it can be used to incrementally detect over-constrainedness. We give an algorithm to efficiently identify all maximal rigid parts of a geometric constraint system. We introduce the algorit…

Analysis of human skin hyper-spectral images by non-negative matrix factorization

2011

International audience; This article presents the use of Non-negative Matrix Factorization, a blind source separation algorithm, for the decomposition of human skin absorption spectra in its main pigments: melanin and hemoglobin. The evaluated spectra come from a Hyper-Spectral Image, which is the result of the processing of a Multi-Spectral Image by a neural network-based algorithm. The implemented source separation algorithm is based on a multiplicative coeffi cient upload. The goal is to represent a given spectrum as the weighted sum of two spectral components. The resulting weighted coefficients are used to quantify melanin and hemoglobin content in the given spectra. Results present a …

An IMEX-Scheme for Pricing Options under Stochastic Volatility Models with Jumps

2014

Partial integro-differential equation (PIDE) formulations are often preferable for pricing options under models with stochastic volatility and jumps, especially for American-style option contracts. We consider the pricing of options under such models, namely the Bates model and the so-called stochastic volatility with contemporaneous jumps (SVCJ) model. The nonlocality of the jump terms in these models leads to matrices with full matrix blocks. Standard discretization methods are not viable directly since they would require the inversion of such a matrix. Instead, we adopt a two-step implicit-explicit (IMEX) time discretization scheme, the IMEX-CNAB scheme, where the jump term is treated ex…

A Domain Decomposition/Nash Equilibrium Methodology for the Solution of Direct and Inverse Problems in Fluid Dynamics with Evolutionary Algorithms

2008

Quasiregular ellipticity of open and generalized manifolds

2014

We study the existence of geometrically controlled branched covering maps from \(\mathbb R^3\) to open \(3\)-manifolds or to decomposition spaces \(\mathbb {S}^3/G\), and from \(\mathbb {S}^3/G\) to \(\mathbb {S}^3\).

Integration of multifunctions with closed convex values in arbitrary Banach spaces

2018

Integral properties of multifunctions with closed convex values are studied. In this more general framework not all the tools and the technique used for weakly compact convex valued multifunctions work. We pay particular attention to the "positive multifunctions". Among them an investigation of multifunctions determined by vector-valued functions is presented. Finally, decomposition results are obtained for scalarly and gauge-defined integrals of multifunctions and a full description of McShane integrability in terms of Henstock and Pettis integrability is given.

A Linear Cost Algorithm to Compute the Discrete Gabor Transform

2010

In this paper, we propose an alternative efficient method to calculate the Gabor coefficients of a signal given a synthesis window with a support of size much lesser than the length of the signal. The algorithm uses the canonical dual of the window (which does not need to be calculated beforehand) and achieves a computational cost that is linear with the signal length in both analysis and synthesis. This is done by exploiting the block structure of the matrices and using an ad hoc Cholesky decomposition of the Gabor frame matrix.

BMaD – A Boolean Matrix Decomposition Framework

2014

Boolean matrix decomposition is a method to obtain a compressed representation of a matrix with Boolean entries. We present a modular framework that unifies several Boolean matrix decomposition algorithms, and provide methods to evaluate their performance. The main advantages of the framework are its modular approach and hence the flexible combination of the steps of a Boolean matrix decomposition and the capability of handling missing values. The framework is licensed under the GPLv3 and can be downloaded freely at http://projects.informatik.uni-mainz.de/bmad.

What is the Best Method of Matrix Adjustment? A Formal Answer by a Return to the World of Vectors

2003

The principle of matrix adjustment methods consists into finding what is the matrix which is the closest to an initial matrix but with respect of the column and row sum totals of a second matrix. In order to help deciding which matrix-adjustment method is the better, the article returns to the simpler problem of vector adjustment then back to matrices. The information-lost minimization (biproportional methods and RAS) leads to a multiplicative form and generalize the linear model. On the other hand, the distance minimization which leads to an additive form tends to distort the data by giving a result asymptotically independent to the initial matrix. The result allows concluding non-ambiguou…