Descripción: We introduce a predictor-corrector algorithm to estimate parameters in a nonlinear hyperbolic problem. It can be used to estimate the oil-fractional flow function from the Buckley-Leverett equation. The forward model is non-linear: the sought- for parameter is a function of the solution of the equation. Traditionally, the estimation of functions requires the selection of a fitting parametric model. The algorithm that we develop does not require a predetermined parameter model. Therefore, the estimation problem is carried out over a set of parameters which are functions. The algorithm is based on the linearization of the parameter-to-output mapping. This technique is new in the field of nonlinear estimation. It has the advantage of laying aside parametric models. The algorithm is iterative and is of predictor-corrector type. We present theoretical results on the inverse problem. We use synthetic data to test the new algorithm. © 2008 IOP Publishing Ltd.

Descripción: Given a reduced affine algebra A over a perfect field K, we present parallel algorithms to compute the normalization Ā of A. Our starting point is the algorithm of Greuel et al. (2010), which is an improvement of de Jong's algorithm (de Jong, 1998; Decker et al., 1999). First, we propose to stratify the singular locus Sing(A) in a way which is compatible with normalization, apply a local version of the normalization algorithm at each stratum, and find Ā by putting the local results together. Second, in the case where K=Q is the field of rationals, we propose modular versions of the global and local-to-global algorithms. We have implemented our algorithms in the computer algebra system Singular and compare their performance with that of the algorithm of Greuel et al. (2010). In the case where K=Q, we also discuss the use of modular computations of Gröbner bases, radicals, and primary decompositions. We point out that in most examples, the new algorithms outperform the algorithm of Greuel et al. (2010) by far, even if we do not run them in parallel. © 2012 Elsevier B.V.

Descripción: Computing the minimum spanning tree (MST) is a common task in the pattern recognition and the computer vision fields. However, little work has been done on efficient general methods for solving the problem on large datasets where graphs are complete and edge weights are given implicitly by a distance between vertex attributes. In this work we propose a generic algorithm that extends the classical Boruvka's algorithm by using nearest neighbors search structures to significantly reduce time and memory consumption. The algorithm can also compute in a straightforward way approximate MSTs thus further improving speed. Experiments show that the proposed method outperforms classical algorithms on large low-dimensional datasets by several orders of magnitude. © Springer-Verlag 2013.

Descripción: We present a new algorithm to compute the integral closure of a reduced Noetherian ring in its total ring of fractions. A modification, applicable in positive characteristic, where actually all computations are over the original ring, is also described. The new algorithm of this paper has been implemented in Singular, for localizations of affine rings with respect to arbitrary monomial orderings. Benchmark tests show that it is in general much faster than any other implementation of normalization algorithms known to us. © 2010 Elsevier Ltd.

Descripción: Fil:Flexer, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Descripción: We present a new algorithm for the computation of resultants associated with multihomogeneous (and, in particular, homogeneous) polynomial equation systems using straight-line programs. Its complexity is polynomial in the number of coefficients of the input system and the degree of the resultant computed. © 2006 Elsevier Ltd. All rights reserved.

Descripción: We consider first the zero-nonzero determination problem, which consists in determining the list of zero-nonzero conditions realized by a finite list of polynomials on a finite set ZâŠCk with C an algebraic closed field. We describe an algorithm to solve the zero-nonzero determination problem and we perform its bit complexity analysis. This algorithm, which is in many ways an adaptation of the methods used to solve the more classical sign determination problem, presents also new ideas which can be used to improve sign determination. Then, we consider the real-nonreal sign determination problem, which deals with both the sign determination and the zero-nonzero determination problem. We describe an algorithm to solve the real-nonreal sign determination problem, we perform its bit complexity analysis and we discuss this problem in a parametric context. © 2013 Elsevier Inc.

Descripción: We propose a new algorithm for the Capacitated Arc Routing Problem (CARP). Our motivation to deal with this problem is related to its application in several real world scenarios such as street sweeping, urban waste collection and electric meter reading just to mention a few. Based on BRKGA metaheuristic, our algorithm introduces a new random key encoding for CARP, mutation to random keys strings, a restart phase to avoid stagnation and local search. The algorithm was tested with several well-known instances from the literature. The results obtained were competitive in terms of objective function value and required computational time. © 2011 Elsevier B.V.

Descripción: We present a symbolic probabilistic algorithm to compute the isolated roots in Cn of sparse polynomial equation systems. As some already known numerical algorithms solving this task, our procedure is based on polyhedral deformations and homotopies, but it amounts to solving a smaller number of square systems of equations and in fewer variables. The output of the algorithm is a geometric resolution of a finite set of points including the isolated roots of the system. The complexity is polynomial in the size of the combinatorial structure of the system supports up to a pre-processing yielding the mixed cells in a subdivision of the family of these supports. © 2010 Elsevier B.V. All rights reserved.

Descripción: In this paper we obtain an effective algorithm for quantifier elimination over algebraically closed fields: For every effective infinite integral domain k, closed under the extraction of pth roots when the characteristic p of k is positive, and every prenex formula φ with r blocks of quantifiers involving s polynomials F1,...,Fs∈k[X1,...,Xn] encoded in dense form, there exists a well-parallelizable algorithm without divisions whose output is a quantifier-free formula equivalent to φ. The sequential complexity of this algorithm is bounded by O(|φ|) - D(O(n))r, where |φ| is the length of φ and D ≥ n is an upper bound for 1 + ∑si-1 deg Fi, and the polynomials in the output are encoded by means of a straight line program. The complexity bound obtained is better than the bounds of the known elimination algorithms, which are of the type |φ|.Dncr, where c ≥ 2 is a constant. This becomes notorious when r = 1 (i.e., when there is only one block of quantifiers): the complexity bounds known up to now are not less than Dn2, while our bound is DO(n). Moreover, in the particular case that there is only one block of existential quantifiers and the input polynomials are given by a straight line program, we construct an elimination algorithm with even better bounds which depend on the length of this straight line program: Given a formula of the type ∃xn-m + 1, . . . , ∃xn: F1(x1, . . . ,Xn) = 0 ∧ ⋯ ∧ Fs(x1, . . . ,Xn) = 0 ∧ G1(x1, . . . , Xn) ≠ 0 ∧ ⋯ ∧ Gs′ (x1, . . . ,xn) ≠ 0, where F1, . . . ,Fs ∈ k[X1, . . . ,Xn] are polynomials whose degrees in the m variables Xn-m+1,. . . ,Xn are bounded by an integer d ≥ m and G1, . . . ,Gs′ ∈ k[X1, . . . ,Xn] are polynomials whose degrees in the same variables are bounded by an integer δ, this algorithm eliminates quantifiers in time L2.(s.s′.δ)O(1).dO(m), where L is the length of the straight line program that encodes F1, . . . ,Fs, G1, . . . ,Gs′. Finally, we construct a fast algorithm to compute the Chow Form of an irreducible projective variety. The construction of all the algorithms mentioned above relies on a preprocessing whose cost exceedes the complexity classes considered (they are based on the construction of correct test sequences). In this sense, our algorithms are non-uniform but may be considered uniform as randomized algorithms (choosing the correct test sequences randomly). © 1998 Elsevier Science B.V. All rights reserved.

Descripción: The subcellular localization and physiological functions of biomolecules are closely related and thus it is crucial to precisely determine the distribution of different molecules inside the intracellular structures. This is frequently accomplished by fluorescence microscopy with well-characterized markers and posterior evaluation of the signal colocalization. Rigorous study of colocalization requires statistical analysis of the data, albeit yet no single technique has been established as a standard method. Indeed, the few methods currently available are only accurate in images with particular characteristics. Here, we introduce a new algorithm to automatically obtain the true colocalization between images that is suitable for a wide variety of biological situations. To proceed, the algorithm contemplates the individual contribution of each pixel's fluorescence intensity in a pair of images to the overall Pearsońs correlation and Manders' overlap coefficients. The accuracy and reliability of the algorithm was validated on both simulated and real images that reflected the characteristics of a range of biological samples. We used this algorithm in combination with image restoration by deconvolution and time-lapse confocal microscopy to address the localization of MEK1 in the mitochondria of different cell lines. Appraising the previously described behavior of Akt1 corroborated the reliability of the combined use of these techniques. Together, the present work provides a novel statistical approach to accurately and reliably determine the colocalization in a variety of biological images. © 2011 Villalta et al.

Descripción: We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bézout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety. © 2006 American Mathematical Society.

Descripción: We prove that a polynomial f ∈ R [x, y] with t non-zero terms, restricted to a real line y = a x + b, either has at most 6 t - 4 zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y - a x - b ∈ K [x, y] divides a lacunary polynomial f ∈ K [x, y], where K is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of f, in the logarithm of the degree of f, in the degree of the extension K / Q and in the logarithmic height of a, b and f. © 2009 Elsevier Ltd. All rights reserved.

Descripción: In this paper we present a probabilistic algorithm which computes, from a finite set of polynomials defining an algebraic variety V, the decomposition of V into equidimensional components. If V is defined by s polynomials in n variables of degrees bounded by an integer d ≥ n and V = ∪l=0 r Vℓ is the equidimensional decomposition of V, the algorithm obtains in sequential time bounded by sO(1)dO(n), for each 0 ≤ ℓ ≤r, a set of n + 1 polynomials of degrees bounded by deg(Vℓ) which define Vℓ. © 2002 Elsevier Science B.V. All rights reserved.

Descripción: Let G = (V, E) be a graph and d a positive integer. We study the following problem: for which labelings fE : E → Zd is there a labeling fV : V → Zd such that fE (i, j) = fV (i) + fV (j) (mod d), for every edge (i, j) ∈ E? We also explore the connections of the equivalent multiplicative version to toric ideals. We derive a polynomial algorithm to answer these questions and to obtain all possible solutions. © 2009 Elsevier B.V. All rights reserved.

Descripción: This paper deals with the index reduction problem for the class of quasi-regular DAE systems. It is shown that any of these systems can be transformed to a generically equivalent first order DAE system consisting of a single purely algebraic (polynomial) equation plus an under-determined ODE (a differential Kronecker representation) in as many variables as the order of the input system. This can be done by means of a Kronecker-type algorithm with bounded complexity. © 2011 Elsevier Ltd.

Descripción: We prove upper bounds on the order and degree of the polynomials involved in a resolvent representation of the prime differential ideal associated with a polynomial differential system for a particular class of ordinary first order algebraic-differential equations arising in control theory. We also exhibit a probabilistic algorithm which computes this resolvent representation within time polynomial in the natural syntactic parameters and the degree of a certain algebraic variety related to the input system. In addition, we give a probabilistic polynomial-time algorithm for the computation of the differential Hilbert function of the ideal. © 2005 Elsevier Inc. All rights reserved.

Descripción: We present an algorithm to compute a parametric description of the totally mixed Nash equilibria of a generic game in normal form with a fixed structure. Using this representation, we also show an algorithm to compute polynomial inequality conditions under which a game has the maximum possible number of this kind of equilibria. Then, we present symbolic procedures to describe the set of isolated totally mixed Nash equilibria of an arbitrary game and to compute, under certain general assumptions, the exact number of these equilibria. The complexity of all these algorithms is polynomial in the number of players, the number of each player's strategies and the generic number of totally mixed Nash equilibria of a game with the considered structure. © 2009 Elsevier Ltd. All rights reserved.

Descripción: Synthetic Aperture Radar (SAR) images are dificult to segment due to their characteristic noise, called speckle, which is multiplicative, non-gaussian and has a low signal to noise ratio. In this work we use the GH distribution to model the SAR data from the different regions of the image. We estimate their statistical parameters and use them in a segmentation algorithm based on multiregion competition. We then apply this algorithm to segment simulated as well as real SAR images and evaluate the accuracy of the segmentation results obtained. © 2009 Springer-Verlag Berlin Heidelberg.