Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProperties of polynomial bases used in a line-surface intersection algorithm
218
0
0.0
(
0
)
Added by
Gun Srijuntongsiri
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In [5], Srijuntongsiri and Vavasis propose the Kantorovich-Test Subdivision algorithm, or KTS, which is an algorithm for finding all zeros of a polynomial system in a bounded region of the plane. This algorithm can be used to find the intersections between a line and a surface. The main features of KTS are that it can operate on polynomials represented in any basis that satisfies certain conditions and that its efficiency has an upper bound that depends only on the conditioning of the problem and the choice of the basis representing the polynomial system. This article explores in detail the dependence of the efficiency of the KTS algorithm on the choice of basis. Three bases are considered: the power, the Bernstein, and the Chebyshev bases. These three bases satisfy the basis properties required by KTS. Theoretically, Chebyshev case has the smallest upper bound on its running time. The computational results, however, do not show that Chebyshev case performs better than the other two.
rate research
Read More
There are very few results on mixed finite element methods on surfaces. A theory for the study of such methods was given recently by Holst and Stern, using a variational crimes framework in the context of finite element exterior calculus. However, we are not aware of any numerical experiments where mixed finite elements derived from discretizations of exterior calculus are used for a surface domain. This short note shows results of our preliminary experiments using mixed methods for Darcy flow (hence scalar Poissons equation in mixed form) on surfaces. We demonstrate two numerical methods. One is derived from the primal-dual Discrete Exterior Calculus and the other from lowest order finite element exterior calculus. The programming was done in the language Python, using the PyDEC package which makes the code very short and easy to read. The qualitative convergence studies seem to be promising.
In a previous paper [1] it was discussed the viability of functional analysis using as a basis a couple of generic functions, and hence vectorial decomposition. Here we complete the paradigm exploiting one of the analysis methodologies developed there, but applied to phase coordinates, so needing only one function as a basis. It will be shown that, thanks to the novel iterative analysis, any function satisfying a rather loose requisite is ontologically a basis. This in turn generalizes the polar version of the Fourier theorem to an ample class of nonorthogonal bases. The main advantage of this generalization is that it inherits some of the properties of the original Fourier theorem. As a result the new transform has a wide range of applications and some remarkable consequences. The new tool will be compared with wavelets and frames. Examples of analysis and reconstruction of functions using the developed algorithms and generic bases will be given. Some of the properties, and applications that can promptly benefit from the theory, will be discussed. The implementation of a matched filter for noise suppression will be used as an example of the potential of the theory.
Composite function minimization captures a wide spectrum of applications in both computer vision and machine learning. It includes bound constrained optimization, $ell_1$ norm regularized optimization, and $ell_0$ norm regularized optimization as special cases. This paper proposes and analyzes a new Generalized Matrix Splitting Algorithm (GMSA) for minimizing composite functions. It can be viewed as a generalization of the classical Gauss-Seidel method and the Successive Over-Relaxation method for solving linear systems in the literature. Our algorithm is derived from a novel triangle operator mapping, which can be computed exactly using a new generalized Gaussian elimination procedure. We establish the global convergence, convergence rate, and iteration complexity of GMSA for convex problems. In addition, we also discuss several important extensions of GMSA. Finally, we validate the performance of our proposed method on three particular applications: nonnegative matrix factorization, $ell_0$ norm regularized sparse coding, and $ell_1$ norm regularized Dantzig selector problem. Extensive experiments show that our method achieves state-of-the-art performance in term of both efficiency and efficacy.
This paper describes the algorithms, features and implementation of PyDEC, a Python library for computations related to the discretization of exterior calculus. PyDEC facilitates inquiry into both physical problems on manifolds as well as purely topological problems on abstract complexes. We describe efficient algorithms for constructing the operators and objects that arise in discrete exterior calculus, lowest order finite element exterior calculus and in related topological problems. Our algorithms are formulated in terms of high-level matrix operations which extend to arbitrary dimension. As a result, our implementations map well to the facilities of numerical libraries such as NumPy and SciPy. The availability of such libraries makes Python suitable for prototyping numerical methods. We demonstrate how PyDEC is used to solve physical and topological problems through several concise examples.
We consider equation systems of the form X_1 = f_1(X_1, ..., X_n), ..., X_n = f_n(X_1, ..., X_n) where f_1, ..., f_n are polynomials with positive real coefficients. In vector form we denote such an equation system by X = f(X) and call f a system of positive polynomials, short SPP. Equation systems of this kind appear naturally in the analysis of stochastic models like stochastic context-free grammars (with numerous applications to natural language processing and computational biology), probabilistic programs with procedures, web-surfing models with back buttons, and branching processes. The least nonnegative solution mu f of an SPP equation X = f(X) is of central interest for these models. Etessami and Yannakakis have suggested a particular version of Newtons method to approximate mu f. We extend a result of Etessami and Yannakakis and show that Newtons method starting at 0 always converges to mu f. We obtain lower bounds on the convergence speed of the method. For so-called strongly connected SPPs we prove the existence of a threshold k_f such that for every i >= 0 the (k_f+i)-th iteration of Newtons method has at least i valid bits of mu f. The proof yields an explicit bound for k_f depending only on syntactic parameters of f. We further show that for arbitrary SPP equations Newtons method still converges linearly: there are k_f>=0 and alpha_f>0 such that for every i>=0 the (k_f+alpha_f i)-th iteration of Newtons method has at least i valid bits of mu f. The proof yields an explicit bound for alpha_f; the bound is exponential in the number of equations, but we also show that it is essentially optimal. Constructing a bound for k_f is still an open problem. Finally, we also provide a geometric interpretation of Newtons method for SPPs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
