scientific article; zbMATH DE number 1254030

From MaRDI portal
Publication:4227013





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].











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)