Related Research Articles
In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring K[x1, ..., xn] over a field K. A Gröbner basis allows many important properties of the ideal and the associated algebraic variety to be deduced easily, such as the dimension and the number of zeros when it is finite. Gröbner basis computation is one of the main practical tools for solving systems of polynomial equations and computing the images of algebraic varieties under projections or rational maps.
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.
In the theory of multivariate polynomials, Buchberger's algorithm is a method for transforming a given set of polynomials into a Gröbner basis, which is another set of polynomials that have the same common zeros and are more convenient for extracting information on these common zeros. It was introduced by Bruno Buchberger simultaneously with the definition of Gröbner bases.
In mathematics, the Bernstein–Sato polynomial is a polynomial related to differential operators, introduced independently by Joseph Bernstein (1971) and Mikio Sato and Takuro Shintani, Sato (1990). It is also known as the b-function, the b-polynomial, and the Bernstein polynomial, though it is not related to the Bernstein polynomials used in approximation theory. It has applications to singularity theory, monodromy theory, and quantum field theory.
In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.
John K. S. McKay was a British-Canadian mathematician and academic who worked at Concordia University, known for his discovery of monstrous moonshine, his joint construction of some sporadic simple groups, for the McKay conjecture in representation theory, and for the McKay correspondence relating certain finite groups to Lie groups.
In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms. A major unresolved challenge is to determine if the problem admits a polynomial time algorithm; that is, whether the problem lies in the complexity class P.
In computer algebra, the Faugère F4 algorithm, by Jean-Charles Faugère, computes the Gröbner basis of an ideal of a multivariate polynomial ring. The algorithm uses the same mathematical principles as the Buchberger algorithm, but computes many normal forms in one go by forming a generally sparse matrix and using fast linear algebra to do the reductions in parallel.
The following tables list the computational complexity of various algorithms for common mathematical operations.
In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct.
In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials are identical. More formally, a PIT algorithm is given an arithmetic circuit that computes a polynomial p in a field, and decides whether p is the zero polynomial. Determining the computational complexity required for polynomial identity testing is one of the most important open problems in algebraic computing complexity.
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.
In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the right amount of time it should take is of major practical relevance.
In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form
Vladimir P. Gerdt was a Russian mathematician and a full professor at the Joint Institute for Nuclear Research (JINR) where he was the head of the Group of Algebraic and Quantum Computations. His research interests were concentrated in computer algebra, symbolic and algebraic computations, algebraic and numerical analysis of nonlinear differential equations, polynomial equations, applications to mathematics and physics, and quantum computation with over 210 published articles.
FGLM is one of the main algorithms in computer algebra, named after its designers, Faugère, Gianni, Lazard and Mora. They introduced their algorithm in 1993. The input of the algorithm is a Gröbner basis of a zero-dimensional ideal in the ring of polynomials over a field with respect to a monomial order and a second monomial order. As its output, it returns a Gröbner basis of the ideal with respect to the second ordering. The algorithm is a fundamental tool in computer algebra and has been implemented in most of the computer algebra systems. The complexity of FGLM is O(nD3), where n is the number of variables of the polynomials and D is the degree of the ideal. There are several generalization and various applications for FGLM.
Ferdinando 'Teo' Mora is an Italian mathematician, and since 1990 until 2019 a professor of algebra at the University of Genoa.
Joris van der Hoeven is a Dutch mathematician and computer scientist, specializing in algebraic analysis and computer algebra. He is the primary developer of GNU TeXmacs.
Andrew Victor Sutherland is an American mathematician and Principal Research Scientist at the Massachusetts Institute of Technology. His research focuses on computational aspects of number theory and arithmetic geometry. He is known for his contributions to several projects involving large scale computations, including the Polymath project on bounded gaps between primes, the L-functions and Modular Forms Database, the sums of three cubes project, and the computation and classification of Sato-Tate distributions.
References
- ↑ Rédei, L. (1973), Lacunary polynomials over finite fields, translated by Földes, I., Elsevier, MR 0352060
- 1 2 Khovanskiĭ, A. G. (1991), Fewnomials, Translations of Mathematical Monographs, vol. 88, translated by Zdravkovska, Smilka, Providence, Rhode Island: American Mathematical Society, doi:10.1090/mmono/088, ISBN 0-8218-4547-0, MR 1108621
- ↑ Roche, Daniel S. (2018), "What can (and can't) we do with sparse polynomials?", in Kauers, Manuel; Ovchinnikov, Alexey; Schost, Éric (eds.), Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2018, New York, NY, USA, July 16-19, 2018, Association for Computing Machinery, pp. 25–30, arXiv: 1807.08289 , doi:10.1145/3208976.3209027, S2CID 49868973
- ↑ Nakos, Vasileios (2020), "Nearly optimal sparse polynomial multiplication", IEEE Transactions on Information Theory, 66 (11): 7231–7236, arXiv: 1901.09355 , doi:10.1109/TIT.2020.2989385, MR 4173637, S2CID 59316578
- ↑ Giorgi, Pascal; Grenet, Bruno; Perret du Cray, Armelle (2020), "Essentially optimal sparse polynomial multiplication", Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (ISSAC '20)., Association for Computing Machinery, pp. 202–209, arXiv: 2001.11959 , doi:10.1145/3373207.3404026, S2CID 211003922
- ↑ Giorgi, Pascal; Grenet, Bruno; Perret du Cray, Armelle (2021), "On Exact Division and Divisibility Testing for Sparse Polynomials", Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation (ISSAC '21)., Association for Computing Machinery, pp. 163–170, arXiv: 2102.04826 , doi:10.1145/3452143.3465539, S2CID 231855563
- ↑ Pan, Victor Y. (2020), "Acceleration of subdivision root-finding for sparse polynomials", Computer algebra in scientific computing, Lecture Notes in Computer Science, vol. 12291, Cham: Springer, pp. 461–477, doi:10.1007/978-3-030-60026-6_27, MR 4184190, S2CID 224820309
- ↑ Zippel, Richard (1979), "Probabilistic algorithms for sparse polynomials", Symbolic and algebraic computation (EUROSAM '79, Internat. Sympos., Marseille, 1979), Lecture Notes in Computer Science, vol. 72, Berlin, New York: Springer, pp. 216–226, MR 0575692
- ↑ Cohen, S. D.; Movahhedi, A.; Salinier, A. (1999), "Galois groups of trinomials", Journal of Algebra, 222 (2): 561–573, doi: 10.1006/jabr.1999.8033 , MR 1734229
- ↑ Averkov, Gennadiy; Scheiderer, Claus (2023-03-07). "Convex hulls of monomial curves, and a sparse positivstellensatz". arXiv: 2303.03826 [math.OC].
