|
Petkovšek's Algorithm
Petkovšek's algorithm (also Hyper) is a computer algebra algorithm that computes a basis of hypergeometric terms solution of its input linear recurrence equation with polynomial coefficients. Equivalently, it computes a first order right factor of linear difference operators with polynomial coefficients. This algorithm was developed by Marko Petkovšek in his PhD-thesis 1992. The algorithm is implemented in all the major computer algebra systems. Gosper-Petkovšek representation Let \mathbb be a field of characteristic zero. A nonzero sequence y(n) is called hypergeometric if the ratio of two consecutive terms is rational, i.e. y (n+1) /y(n) \in \mathbb(n). The Petkovšek algorithm uses as key concept that this rational function has a specific representation, namely the ''Gosper-Petkovšek normal form''. Let r(n) \in \mathbb /math> be a nonzero rational function. Then there exist monic polynomials a, b, c \in \mathbb /math> and 0 \neq z \in \mathbb such that r(n) = z \frac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Algebra
In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expressions and other mathematical objects. Although computer algebra could be considered a subfield of scientific computing, they are generally considered as distinct fields because scientific computing is usually based on numerical computation with approximate floating point numbers, while symbolic computation emphasizes ''exact'' computation with expressions containing variables that have no given value and are manipulated as symbols. Software applications that perform symbolic calculations are called ''computer algebra systems'', with the term ''system'' alluding to the complexity of the main applications that include, at least, a method to represent mathematical data in a computer, a user programming language (usually different from the languag ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hypergeometric Identity
In mathematics, hypergeometric identities are equalities involving sums over hypergeometric terms, i.e. the coefficients occurring in hypergeometric series. These Identity (mathematics), identities occur frequently in solutions to combinatorial problems, and also in the analysis of algorithms. These identities were traditionally found 'by hand'. There exist now several algorithms which can find and ''prove'' all hypergeometric identities. Examples : \sum_^ = 2^ : \sum_^ ^2 = : \sum_^ k = n2^ : \sum_^ i = (n+1)- Definition There are two definitions of hypergeometric terms, both used in different cases as explained below. See also hypergeometric series. A term ''tk'' is a hypergeometric term if : \frac is a rational function in ''k''. A term ''F(n,k)'' is a hypergeometric term if : \frac is a rational function in ''k''. There exist two types of sums over hypergeometric terms, the definite and indefinite sums. A definite sum is of the form : \sum_ t_ ... [...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 on 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] |
Difference Operator
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter k that is independent of n; this number k is called the ''order'' of the relation. If the values of the first k numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation. In ''linear recurrences'', the th term is equated to a linear function of the k previous terms. A famous example is the recurrence for the Fibonacci numbers, F_n=F_+F_ where the order k is two and the linear function merely adds the two previous terms. This example is a linear recurrence with constant coefficients, because the coefficients of the linear function (1 and 1) are constants that do not depend on n. For these recurrences, one can express the general term of the sequence as a closed-form expression of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Marko Petkovšek
Marko Petkovšek is a Slovenian mathematician, born: 1955, working mainly in symbolic computation. He is a professor of discrete and computational mathematics at the University of Ljubljana. He completed his Ph.D. at Carnegie Mellon University under the supervision of Dana Scott. He is best known for Petkovšek's algorithm. Together with Herbert Wilf and Doron Zeilberger Doron Zeilberger (דורון ציילברגר, born 2 July 1950 in Haifa, Israel) is an Israeli mathematician, known for his work in combinatorics. Education and career He received his doctorate from the Weizmann Institute of Science in 1976, ... he wrote the book '' A = B''. External links "A = B"* 1955 births Carnegie Mellon University alumni Living people 21st-century Slovenian mathematicians University of Ljubljana faculty 20th-century Slovenian mathematicians {{europe-mathematician-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Field (mathematics)
In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers do. 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 fields of rational functions, algebraic function fields, algebraic number fields, and ''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 elements. The relation of two fields is expressed by the notion of a field extension. Galois theory, initiated by Évariste Galois in the 1830s, is devoted to understanding the symmetries of field extensions. Among other results, thi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Characteristic (algebra)
In mathematics, the characteristic of a ring (mathematics), ring , often denoted , is defined to be the smallest number of times one must use the ring's identity element, multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive identity the ring is said to have characteristic zero. That is, is the smallest positive number such that: :\underbrace_ = 0 if such a number exists, and otherwise. Motivation The special definition of the characteristic zero is motivated by the equivalent definitions characterized in the next section, where the characteristic zero is not required to be considered separately. The characteristic may also be taken to be the exponent (group theory), exponent of the ring's additive group, that is, the smallest positive integer such that: :\underbrace_ = 0 for every element of the ring (again, if exists; otherwise zero). Some authors do not include the multiplicative identity element in their r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rational Function
In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be rational numbers; they may be taken in any field ''K''. In this case, one speaks of a rational function and a rational fraction ''over K''. The values of the variables may be taken in any field ''L'' containing ''K''. Then the domain of the function is the set of the values of the variables for which the denominator is not zero, and the codomain is ''L''. The set of rational functions over a field ''K'' is a field, the field of fractions of the ring of the polynomial functions over ''K''. Definitions A function f(x) is called a rational function if and only if it can be written in the form : f(x) = \frac where P\, and Q\, are polynomial functions of x\, and Q\, is not the zero function. The domain of f\, is the set of all values of x\ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ring Of Polynomial Functions
In mathematics, the ring of polynomial functions on a vector space ''V'' over a field ''k'' gives a coordinate-free analog of a polynomial ring. It is denoted by ''k'' 'V'' If ''V'' is finite dimensional and is viewed as an algebraic variety, then ''k'' 'V''is precisely the coordinate ring of ''V''. The explicit definition of the ring can be given as follows. If k _1, \dots, t_n/math> is a polynomial ring, then we can view t_i as coordinate functions on k^n; i.e., t_i(x) = x_i when x = (x_1, \dots, x_n). This suggests the following: given a vector space ''V'', let ''k'' 'V''be the commutative ''k''-algebra generated by the dual space V^*, which is a subring of the ring of all functions V \to k. If we fix a basis for ''V'' and write t_i for its dual basis, then ''k'' 'V''consists of polynomials in t_i. If ''k'' is infinite, then ''k'' 'V''is the symmetric algebra of the dual space V^*. In applications, one also defines ''k'' 'V''when ''V'' is defined over some subfield of ''k'' ( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gosper's Algorithm
In mathematics, Gosper's algorithm, due to Bill Gosper, is a procedure for finding sums of hypergeometric terms that are themselves hypergeometric terms. That is: suppose one has ''a''(1) + ... + ''a''(''n'') = ''S''(''n'') − ''S''(0), where ''S''(''n'') is a hypergeometric term (i.e., ''S''(''n'' + 1)/''S''(''n'') is a rational function of ''n''); then necessarily ''a''(''n'') is itself a hypergeometric term, and given the formula for ''a''(''n'') Gosper's algorithm finds that for ''S''(''n''). Outline of the algorithm Step 1: Find a polynomial ''p'' such that, writing ''b''(''n'') = ''a''(''n'')/''p''(''n''), the ratio ''b''(''n'')/''b''(''n'' − 1) has the form ''q''(''n'')/''r''(''n'') where ''q'' and ''r'' are polynomials and no ''q''(''n'') has a nontrivial factor with ''r''(''n'' + ''j'') for ''j'' = 0, 1, 2, ... . (This is always possible, whether or not the series is summable in cl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proc
Proc may refer to: * Proč, a village in eastern Slovakia * '' Proč?'', a 1987 Czech film * procfs or proc filesystem, a special file system (typically mounted to ) in Unix-like operating systems for accessing process information * Protein C (PROC) * Proc, a term in video game terminology * Procedures or process, in the programming language ALGOL 68 * People's Republic of China, the formal name of China China, officially the People's Republic of China (PRC), is a country in East Asia. It is the world's most populous country, with a population exceeding 1.4 billion, slightly ahead of India. China spans the equivalent of five time zones and ... * the official acronym for the Canadian House of Commons Standing Committee on Procedure and House Affairs {{disambiguation ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algebraic Equation
In mathematics, an algebraic equation or polynomial equation is an equation of the form :P = 0 where ''P'' is a polynomial with coefficients in some field, often the field of the rational numbers. For many authors, the term ''algebraic equation'' refers only to ''univariate equations'', that is polynomial equations that involve only one variable. On the other hand, a polynomial equation may involve several variables. In the case of several variables (the ''multivariate'' case), the term ''polynomial equation'' is usually preferred to ''algebraic equation''. For example, :x^5-3x+1=0 is an algebraic equation with integer coefficients and :y^4 + \frac - \frac + xy^2 + y^2 + \frac = 0 is a multivariate polynomial equation over the rationals. Some but not all polynomial equations with rational coefficients have a solution that is an algebraic expression that can be found using a finite number of operations that involve only those same types of coefficients (that is, can be solved alg ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
