Reconstruction of a non-radical triangular set from its primary components and its bit-size estimate (Computer Algebra : Theory and its Applications)

Abstract

Triangular sets that generate a non-radical ideal are far less understood then those that generate a radical one. In the realm of "triangular-decomposition", decomposing and reconstructing such triangular sets is important, based on generalized versions of the Chinese remaindering theorem. In this work we address the reconstruction in the non-radical case. It relies on the recently proposed computation of gcd of univariate polynomials over a non-radical triangular set. As an application, we estimate the coefficient growth entailed in this reconstruction process.

根基でないイデアルの三角形集合は、根基イデアル三角形集合に比べてよく理解されていない。Wu-Ritt氏による三角形分解法においては、一般化された中国剰余定理により三角形集合を分解、また復元するのは大事である。本研究は根基でない場合での復元アルゴリズムを扱う。最近対提案された三角形集合上の係数がある多項式の最大公約因子を使うことにより、このアルゴリズムを導入できることになった。応用として、復元の過程による係数の成長を評価する。