|
Polynomial Solutions Of P-recursive Equations
In mathematics a P-recursive equation can be solved for polynomial solutions. Sergei A. Abramov in 1989 and Marko Petkovšek in 1992 described an algorithm which finds all polynomial solutions of those recurrence equations with polynomial coefficients. The algorithm computes a ''degree bound'' for the solution in a first step. In a second step an ansatz for a polynomial of this degree is used and the unknown coefficients are computed by a system of linear equations. This article describes this algorithm. In 1995 Abramov, Bronstein and Petkovšek showed that the polynomial case can be solved more efficiently by considering power series solution of the recurrence equation in a specific power basis (i.e. not the ordinary basis (x^n)_). Other algorithms which compute rational or hypergeometric solutions of a linear recurrence equation with polynomial coefficients also use algorithms which compute polynomial solutions. Degree bound Let \mathbb be a field of characteristic zero and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
P-recursive Equation
In mathematics a P-recursive equation is a linear equation of sequences where the coefficient sequences can be represented as polynomials. P-recursive equations are linear recurrence equations (or linear recurrence relations or linear difference equations) with polynomial coefficients. These equations play an important role in different areas of mathematics, specifically in combinatorics. The sequences which are solutions of these equations are called holonomic, P-recursive or D-finite. From the late 1980s, the first algorithms were developed to find solutions for these equations. Sergei A. Abramov, Marko Petkovšek and Mark van Hoeij described algorithms to find polynomial, rational, hypergeometric and d'Alembertian solutions. Definition Let \mathbb be a field of characteristic zero (for example \mathbb = \mathbb), p_k(n) \in \mathbb /math> polynomials for k = 0,\dots,r,f \in \mathbb^ a sequence and y \in \mathbb^ an unknown sequence. The equation\sum_^r p_k(n) \, y (n+k ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Marko Petkovšek
Marko Petkovšek (1955 – 24 March 2023) was a Slovenian mathematician working mainly in symbolic computation. He was a professor of discrete and computational mathematics at the University of Ljubljana. He is best known for Petkovšek's algorithm, and for the book that he coauthored with Herbert Wilf and Doron Zeilberger, '' A = B''. Education and career Petkovšek was born in 1955 in Ljubljana, Slovenia. He attended the University of Ljubljana for his bachelors and masters degrees, which he finished respectively in 1978 and 1986. He completed his PhD at Carnegie Mellon University under the supervision of Dana Scott Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, C ..., with a thesis titled ''Finding Closed-Form Solutions of Difference Equations by Symbolic Methods''. After his PhD ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use Conditional (computer programming), conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning). In contrast, a Heuristic (computer science), heuristic is an approach to solving problems without well-defined correct or optimal results.David A. Grossman, Ophir Frieder, ''Information Retrieval: Algorithms and Heuristics'', 2nd edition, 2004, For example, although social media recommender systems are commonly called "algorithms", they actually rely on heuristics as there is no truly "correct" recommendation. As an e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
Polynomial Ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates (traditionally also called variables) with coefficients in another ring, often a field. Often, the term "polynomial ring" refers implicitly to the special case of a polynomial ring in one indeterminate over a field. The importance of such polynomial rings relies on the high number of properties that they have in common with the ring of the integers. Polynomial rings occur and are often fundamental in many parts of mathematics such as number theory, commutative algebra, and algebraic geometry. In ring theory, many classes of rings, such as unique factorization domains, regular rings, group rings, rings of formal power series, Ore polynomials, graded rings, have been introduced for generalizing some properties of polynomial rings. A closely related notion is that of the ring of polynomial functions on a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Ansatz
In physics and mathematics, an ansatz (; , meaning: "initial placement of a tool at a work piece", plural ansatzes or, from German, ansätze ; ) is an educated guess or an additional assumption made to help solve a problem, and which may later be verified to be part of the solution by its results. Use An ansatz is the establishment of the starting equation(s), the theorem(s), or the value(s) describing a mathematical or physical problem or solution. It typically provides an initial estimate or framework to the solution of a mathematical problem, and can also take into consideration the boundary conditions (in fact, an ansatz is sometimes thought of as a "trial answer" and an important technique in solving differential equations). After an ansatz, which constitutes nothing more than an assumption, has been established, the equations are solved more precisely for the general function of interest, which then constitutes a confirmation of the assumption. In essence, an ansatz makes ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
System Of Linear Equations
In mathematics, a system of linear equations (or linear system) is a collection of two or more linear equations involving the same variable (math), variables. For example, : \begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of three equations in the three variables . A ''Solution (mathematics), solution'' to a linear system is an assignment of values to the variables such that all the equations are simultaneously satisfied. In the example above, a solution is given by the Tuple, ordered triple (x,y,z)=(1,-2,-2), since it makes all three equations valid. Linear systems are a fundamental part of linear algebra, a subject used in most modern mathematics. Computational algorithms for finding the solutions are an important part of numerical linear algebra, and play a prominent role in engineering, physics, chemistry, computer science, and economics. A Nonlinear system, system of non-linear equations can often be Approximation, approximated by a linear system (see linea ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
Formal Power Series
In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial sums, etc.). A formal power series is a special kind of formal series, of the form \sum_^\infty a_nx^n=a_0+a_1x+ a_2x^2+\cdots, where the a_n, called ''coefficients'', are numbers or, more generally, elements of some ring, and the x^n are formal powers of the symbol x that is called an indeterminate or, commonly, a variable. Hence, power series can be viewed as a generalization of polynomials where the number of terms is allowed to be infinite, and differ from usual power series by the absence of convergence requirements, which implies that a power series may not represent a function of its variable. Formal power series are in one to one correspondence with their sequences of coefficients, but the two concepts must not be confused, sin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Abramov's Algorithm
In mathematics, particularly in computer algebra, Abramov's algorithm computes all Rational function, rational solutions of a P-recursive equation, linear recurrence equation with polynomial coefficients. The algorithm was published by Sergei A. Abramov in 1989. Universal denominator The main concept in Abramov's algorithm is a universal denominator. Let \mathbb be a Field (mathematics), field of Characteristic (algebra), characteristic zero. The ''dispersion'' \operatorname (p,q) of two polynomials p, q \in \mathbb[n] is defined as\operatorname (p,q) =\max \ \cup \,where \N denotes the set of non-negative integers. Therefore the dispersion is the maximum k \in \N such that the polynomial p and the k-times shifted polynomial q have a common factor. It is -1 if such a k does not exist. The dispersion can be computed as the largest non-negative integer root of the resultant \operatorname_n (p(n), q(n+k) ) \in \mathbb[k]. Let \sum_^r p_k(n) \, y (n+k) = f(n) be a P-recursive equation, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Field (mathematics)
In mathematics, a field is a set (mathematics), set on which addition, subtraction, multiplication, and division (mathematics), division are defined and behave as the corresponding operations on rational number, rational and real numbers. A field is thus a fundamental algebraic structure which is widely used in algebra, number theory, and many other areas of mathematics. The best known fields are the field of rational numbers, the field of real numbers and the field of complex numbers. Many other fields, such as field of rational functions, fields of rational functions, algebraic function fields, algebraic number fields, and p-adic number, ''p''-adic fields are commonly used and studied in mathematics, particularly in number theory and algebraic geometry. Most cryptographic protocols rely on finite fields, i.e., fields with finitely many element (set), elements. The theory of fields proves that angle trisection and squaring the circle cannot be done with a compass and straighte ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
Falling And Rising Factorials
In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial \begin (x)_n = x^\underline &= \overbrace^ \\ &= \prod_^n(x-k+1) = \prod_^(x-k) . \end The rising factorial (sometimes called the Pochhammer function, Pochhammer polynomial, ascending factorial, — A reprint of the 1950 edition by Chelsea Publishing. rising sequential product, or upper factorial) is defined as \begin x^ = x^\overline &= \overbrace^ \\ &= \prod_^n(x+k-1) = \prod_^(x+k) . \end The value of each is taken to be 1 (an empty product) when n=0. These symbols are collectively called factorial powers. The Pochhammer symbol, introduced by Leo August Pochhammer, is the notation (x)_n, where is a non-negative integer. It may represent ''either'' the rising or the falling factorial, with different articles and authors using different conventions. Pochhammer himself actually used (x)_n with yet another meaning, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |