Search

Sparse interpolation refers to the exact recovery of a function as a short linear combination of basis functions from a limited number of evaluations. For multivariate functions, the case of the monomial basis is well studied, as is now the basis of exponential functions. Beyond the multivariate Chebyshev polynomial obtained as tensor products of univariate Chebyshev polynomials, the theory of root systems allows to define a variety of generalized multivariate Chebyshev polynomials that have connections to topics such as Fourier analysis and representations of Lie algebras. We present a deterministic algorithm to recover a function that is the linear combination of at most r such polynomials from the knowledge of r and an explicitly bounded number of evaluations of this function., Author(s): Evelyne Hubert [sup.1], Michael F. Singer [sup.2] Author Affiliations: (1) INRIA Méditerranée, , 06902, Sophia Antipolis, France (2) grid.40803.3f, 0000 0001 2173 6074, Department of Mathematics, North Carolina State [...]

For a finite group, we present three algorithms to compute a generating set of invariants simultaneously to generating sets of basic equivariants, i.e., equivariants for the irreducible representations of the group. The main novelty resides in the exploitation of the orthogonal complement of the ideal generated by invariants. Its symmetry adapted basis delivers the fundamental equivariants. Fundamental equivariants allow to assemble symmetry adapted bases of polynomial spaces of higher degrees, and these are essential ingredients in exploiting and preserving symmetry in computations. They appear within algebraic computation and beyond, in physics, chemistry and engineering. Our first construction applies solely to reflection groups and consists in applying symmetry preserving interpolation, as developed by the same authors, along an orbit in general position. The fundamental invariants can be read off the H-basis of the ideal of the orbit while the fundamental equivariants are obtained from a symmetry adapted basis of an invariant direct complement to this ideal in the polynomial ring. The second algorithm takes as input primary invariants and the output provides not only the secondary invariants but also free bases for the modules of basic equivariants. These are constructed as the components of a symmetry adapted basis of the orthogonal complement, in the polynomial ring, to the ideal generated by primary invariants. The third and main algorithm proceeds degree by degree, determining the fundamental invariants as forming a H-basis of the Hilbert ideal, i.e., the polynomial ideal generated by the invariants of positive degree. The fundamental equivariants are simultaneously computed degree by degree as the components of a symmetry adapted basis of the orthogonal complement of the Hilbert ideal. [ABSTRACT FROM AUTHOR]

Quadrature is an approximation of the definite integral of a function by a weighted sum of function values at specified points, or nodes, within the domain of integration. Gaussian quadratures are constructed to yield exact results for any polynomials of degree 2r−1 or less by a suitable choice of r nodes and weights. Cubature is a generalization of quadrature in higher dimension. In this article, we elaborate algorithms to compute all minimal cubatures for a given domain and a given degree. We propose first algorithm in symbolic computation to characterize all cubatures of a given degree with a fixed number of nodes. The determination of the nodes and weights is then left to the computation of the eigenvectors of the matrix identified at the characterization stage and can be performed numerically. The characterization of cubatures on which our algorithms are based stems from moment theory. We formulate the results there in a basis‐independent way: Rather than considering the moment matrix, the central object in moment problems, we introduce the underlying linear map from the polynomial ring to its dual, the Hankel operator. This makes natural the use of bases of polynomials other than the monomial basis, and proves to be computationally relevant, either for numerical properties or to exploit symmetry. [ABSTRACT FROM AUTHOR]

We provide an algebraic formulation of the moving frame method for constructing local smooth invariants on a manifold under an action of a Lie group. This formulation gives rise to algorithms for constructing rational and replacement invariants. The latter are algebraic over the field of rational invariants and play a role analogous to Cartan's normalized invariants in the smooth theory. The algebraic algorithms can be used for computing fundamental sets of differential invariants. [ABSTRACT FROM AUTHOR]

Abstract: Geometric constructions applied to a rational action of an algebraic group lead to a new algorithm for computing rational invariants. A finite generating set of invariants appears as the coefficients of a reduced Gröbner basis. The algorithm comes in two variants. In the first construction the ideal of the graph of the action is considered. In the second one the ideal of a cross-section is added to the ideal of the graph. Zero-dimensionality of the resulting ideal brings a computational advantage. In both cases, reduction with respect to the computed Gröbner basis allows us to express any rational invariant in terms of the generators. [Copyright &y& Elsevier]

Discusses the kinds of algorithms for computing stable manifolds of hyperbolic stationary solutions of autonomous systems. Computation of a single point on the manifold or the entire manifold; Use of indirect methods; Discretization of the problem by a one-step scheme; Application of the Lyapunov-Perron or Hadamard graph transform to the resulting discrete dynamical system.