General number field sieveIn number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2 n⌋ + 1 bits) is of the form in O and L-notations. It is a generalization of the special number field sieve: while the latter can only factor numbers of a certain special form, the general number field sieve can factor any number apart from prime powers (which are trivial to factor by taking roots).
Underdetermined systemIn mathematics, a system of linear equations or a system of polynomial equations is considered underdetermined if there are fewer equations than unknowns (in contrast to an overdetermined system, where there are more equations than unknowns). The terminology can be explained using the concept of constraint counting. Each unknown can be seen as an available degree of freedom. Each equation introduced into the system can be viewed as a constraint that restricts one degree of freedom.
Cramer's ruleIn linear algebra, Cramer's rule is an explicit formula for the solution of a system of linear equations with as many equations as unknowns, valid whenever the system has a unique solution. It expresses the solution in terms of the determinants of the (square) coefficient matrix and of matrices obtained from it by replacing one column by the column vector of right-sides of the equations. It is named after Gabriel Cramer (1704–1752), who published the rule for an arbitrary number of unknowns in 1750, although Colin Maclaurin also published special cases of the rule in 1748 (and possibly knew of it as early as 1729).
Monomial orderIn mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all (monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i.e., If and is any other monomial, then . Monomial orderings are most commonly used with Gröbner bases and multivariate division. In particular, the property of being a Gröbner basis is always relative to a specific monomial order.
Schur complementIn linear algebra and the theory of matrices, the Schur complement of a block matrix is defined as follows. Suppose p, q are nonnegative integers, and suppose A, B, C, D are respectively p × p, p × q, q × p, and q × q matrices of complex numbers. Let so that M is a (p + q) × (p + q) matrix. If D is invertible, then the Schur complement of the block D of the matrix M is the p × p matrix defined by If A is invertible, the Schur complement of the block A of the matrix M is the q × q matrix defined by In the case that A or D is singular, substituting a generalized inverse for the inverses on M/A and M/D yields the generalized Schur complement.
Elimination theoryIn commutative algebra and algebraic geometry, elimination theory is the classical name for algorithmic approaches to eliminating some variables between polynomials of several variables, in order to solve systems of polynomial equations. Classical elimination theory culminated with the work of Francis Macaulay on multivariate resultants, as described in the chapter on Elimination theory in the first editions (1930) of Bartel van der Waerden's Moderne Algebra.
