scientific article; zbMATH DE number 1254030
The author presents a well-parallelizable algorithm that, given an ideal \(I\) in \(k[X_1,\dots, X_n]\) by a finite set of polynomials generating it, computes the radical of \(I\) as an intersection of unmixed radical ideals (that is, radical ideals in which all the associated prime ideals have the same dimension), each represented by a characteristic set of polynomials [in the sense of \textit{J. F. Ritt}, Differential algebra (1955; Zbl 0141.03801) and \textit{W. Wu}, J. Autom. Reasoning 2, 221-252 (1986; Zbl 0642.68163)]. A characteristic set of polynomials has a triangular structure: each variable is introduced by one polynomial. The paper is based on a modification made to Kalkbrener's algorithm [\textit{M. Kalkbrener}, J. Symb. Comput. 15, No. 2, 143-167 (1993; Zbl 0783.14039)] in order to avoid the problem of computing superfluous components embedded in other components. The worstcase sequential complexity of any algorithm solving this problem in dense representation is of the same order that the sequential complexity of the algorithm shown in this paper (which is \((d^{n^2})^{O(1)}\), where \(d\) is a bound for the degrees of the input polynomials and \(n\) is the number of variables involved). For the entire collection see [Zbl 0903.00086].
- On the complexity of counting components of algebraic varieties
- Complexity of triangular representations of algebraic sets
- Prime decompositions of radicals in polynomial rings
- Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties
- scientific article; zbMATH DE number 4213458 (Why is no real title available?)
- A new bound on Hrushovski's algorithm for computing the Galois group of a linear differential equation
- On a generalization of Stickelberger's theorem
- Persistent components in Canny's generalized characteristic polynomial
- Choosing variable orderings based on elimination tree for sparse triangular decomposition
- Complexity analysis of triangular decomposition over F₂ with strongly chordal graphs
- Differential elimination and algebraic invariants of polynomial dynamical systems
- Strongly and transitive chordal graphs and their applications in complexity analysis of triangular decomposition
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4227013)