We describe an algorithm for computing the zero-th and the first Betti numbers of the union of n simply connected compact semi-algebraic sets in R-k, where each such set is defined by a constant number of polynomials ...
详细信息
ISBN:
(纸本)3540289666
We describe an algorithm for computing the zero-th and the first Betti numbers of the union of n simply connected compact semi-algebraic sets in R-k, where each such set is defined by a constant number of polynomials of constant degrees. The complexity of the algorithm is O(n(3)). We also describe an implementation of this algorithm in the particular case of arrangements of ellipsoids in R-3 and describe some of our results.
Counting problems, determining the number of possible states of a large system under certain constraints, play an important role in many areas of science. They naturally arise for complex disordered systems in physics...
详细信息
Counting problems, determining the number of possible states of a large system under certain constraints, play an important role in many areas of science. They naturally arise for complex disordered systems in physics and chemistry, in mathematical graph theory, and in computer science. Counting problems, however, are among the hardest problems to access computationally. Here, we suggest a novel method to access a benchmark counting problem, finding chromatic polynomials of graphs. We develop a vertex-oriented symbolic pattern matching algorithm that exploits the equivalence between the chromatic polynomial and the zero-temperature partition function of the Potts antiferromagnet on the same graph. Implementing this bottom-up algorithm using appropriate computeralgebra, the new method outperforms standard top-down methods by several orders of magnitude, already for moderately sized graphs. As a first application, we compute chromatic polynomials of samples of the simple cubic lattice, for the first time computationally accessing three-dimensional lattices of physical relevance. The method offers straightforward generalizations to several other counting problems.
Starting with approximate solutions of the equation -Delta u = wu(3) on the disk, with zero boundary conditions, we prove that there exist true solutions nearby. One of the challenges here lies in the fact that we nee...
详细信息
Starting with approximate solutions of the equation -Delta u = wu(3) on the disk, with zero boundary conditions, we prove that there exist true solutions nearby. One of the challenges here lies in the fact that we need simultaneous and accurate control of both the (inverse) Dirichlet Laplacean and nonlinearities. We achieve this with the aid of a computer, using a Banach algebra of real analytic functions, based on Zernike polynomials. Besides proving existence, and symmetry properties, we also determine the Morse index of the solutions. (C) 2018 Elsevier Ltd. All rights reserved.
In this paper, we study a particular class of matrices generated by generalized permutation matrices corresponding to a subgroup of some permutation group. As applications, we first present a technique from which we c...
详细信息
In this paper, we study a particular class of matrices generated by generalized permutation matrices corresponding to a subgroup of some permutation group. As applications, we first present a technique from which we can get closed formulas for the roots of many families of polynomial equations with degree between 5 and 10, inclusive. Then, we describe a tool that shows how to find solutions to Fermat's last theorem and Beal's conjecture over the square integer matrices of any dimension. Finally, simple generalizations of some of the concepts in numbertheory to integer square matrices are presented.
Given is the Borel probability space on the set of real numbers. The algebraic-analytical structure of the set of all finite atomic random variables on it with a given even number of moments is determined. It is used ...
详细信息
Given is the Borel probability space on the set of real numbers. The algebraic-analytical structure of the set of all finite atomic random variables on it with a given even number of moments is determined. It is used to derive an explicit version of the Chebyshev-Markov-Stieltjes inequalities suitable for computation. These inequalities are based on the theory of orthogonal polynomials, linear algebra, and the polynomial majorant/minorant method. The result is used to derive generalized Laguerre-Samuelson bounds for finite real sequences and generalized Chebyshev-Markov value-at-risk bounds. A financial market case study illustrates how the upper value-at-risk bounds work in the real world.
D. Knuth used the Robinson-Schensted “insertion into a tableau" algorithm to give a direct 1-to-l correspondence between “generalized permutations” and ordered pairs of generalized Young tableaux having the sa...
详细信息
Recently, by using methods of hypercomplex function theory, the authors have shown that a certain sequence S of rational numbers (Vietoris' sequence) combines seemingly disperse subjects in real, complex and hyper...
详细信息
Recently, by using methods of hypercomplex function theory, the authors have shown that a certain sequence S of rational numbers (Vietoris' sequence) combines seemingly disperse subjects in real, complex and hypercomplex analysis. This sequence appeared for the first time in a theorem by Vietoris (1958) with important applications in harmonic analysis (Askey/Steinig, 1974) and in the theory of stable holomorphic functions (Ruscheweyh/Salinas, 2004). A non-standard application of Clifford algebra tools for defining Clifford-holomorphic sequences of Appell polynomials was the hypercomplex context in which a one-parametric generalization S(n), n >= 1, of S (corresponding to n = 2) surprisingly showed up. Without relying on hypercomplex methods this paper demonstrates how purely real methods also lead to s(n). For arbitrary n >= 1 the generating function is determined and for n = 2 a particular case of a recurrence relation similar to that known for Catalan numbers is proved. (C) 2018 Elsevier B.V. All rights reserved.
The proceedings contain 79 papers. The special focus in this conference is on computeralgebra. The topics include: Expression optimization using high-level knowledge;catfact: computeralgebraic tools for applications...
ISBN:
(纸本)9783540515173
The proceedings contain 79 papers. The special focus in this conference is on computeralgebra. The topics include: Expression optimization using high-level knowledge;catfact: computeralgebraic tools for applications of catastrophe theory;computeralgebra application for investigating integrability of nonlinear evolution systems;computer classification of integrable seventh order MKdV — Like equations;symbolic computation and the finite element method;application of lie group and computeralgebra to nonliner mechanics;hierarchical symbolic computations in the analysis of large-scale dynamical systems;schoonschip for computing of gravitino interaction cross sections in N=2 supergravity;creation of efficient symbolic-numeric interface;complexity of quantifier elimination in the theory of ordinary differential equations;Automatic generation of FORTRAN-Coded Jacobians and Hessians;laplace transformations in reduce 3;Reduce 3. 2 on iAPX86/286 — based personal computers;some extensions and applications of reduce system;Infinite structures in scratchpad II;Application of a structured LISP system to computeralgebra;number-theoretic transforms of prescribed length;A hybrid algebraic-numeric system ANS and its preliminary implementation;The calculation of QCD triangular Feynman graphs in the external gluonic field using reduce-2 system;computeralgebra application for determining local symmetries of differential equations;groups and polynomials;trace calculations for gauge theories on a personal computer;evaluation of plasma fluid equations collision integrals using reduce;computerized system of analytic transformations for analysing of differential equations;integral equation with hidden eigenparameter solver: Reduce + fortran in tandem;combinatorial aspects of simplification of algebraic expressions;dynamic program improvement;computeralgebra and numerical convergence;symbolic computation in relativity theory.
Grobner bases is one the most powerful tools in algorithmic nonlinear algebra. Their computation is an intrinsically hard problem with a complexity at least single exponential in the number of variables. However, in m...
详细信息
ISBN:
(纸本)9781450360845
Grobner bases is one the most powerful tools in algorithmic nonlinear algebra. Their computation is an intrinsically hard problem with a complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. We consider sparse systems where the input polynomials have a few non-zero terms. Our approach to exploit sparsity is to embed the systems in a semigroup algebra and to compute Grobner bases over this algebra. Up to now, the algorithms that follow this approach benefit from the sparsity only in the case where all the polynomials have the same sparsity structure, that is the same Newton polytope. We introduce the first algorithm that overcomes this restriction. Under regularity assumptions, it performs no redundant computations. Further, we extend this algorithm to compute Grobner basis in the standard algebra and solve sparse polynomials systems over the torus (C*)(n). The complexity of the algorithm depends on the Newton polytopes.
This book constitutes the strictly refereed proceedings of the 12th International Symposium on Applied algebra, algebraic Algorithms and Error-Correcting Codes, AAECC-12, held in Toulouse, France, June 1997.;The 27 re...
详细信息
ISBN:
(数字)9783540691938
ISBN:
(纸本)9783540631637
This book constitutes the strictly refereed proceedings of the 12th International Symposium on Applied algebra, algebraic Algorithms and Error-Correcting Codes, AAECC-12, held in Toulouse, France, June 1997.;The 27 revised full papers presented were carefully selected by the program committee for inclusion in the volume. The papers address a broad range of current issues in coding theory and computeralgebra spanning polynomials, factorization, commutative algebra, real geometry, group theory, etc. on the mathematical side as well as software systems, telecommunication, complexity theory, compression, signal processing, etc. on the computer science and engineering side.
暂无评论