Loading article…
数学において、円筒代数分解( CAD ) は、計算アルゴリズムとともに、コンピュータ代数と実代数幾何学の基礎となる概念です。 R nの多項式の集合Sが与えられたとき、円筒代数分解は、 R nをセルと呼ばれる連結した半代数集合に分解したもので、各多項式は +、−、または 0 のいずれかの一定の符号を持ちます。円筒形であるためには、この分解は次の条件を満たす必要があります。1 ≤ k < nであり、πがR nからR n − kへの射影で、最後のk 個の座標を除いたものである場合、任意のセルcとdのペアに対して、 π ( c ) = π ( d ) またはπ ( c ) ∩ π ( d ) = ∅のいずれかが成り立ちます。これは、セルのπによる像がR n − kの円筒分解を定義することを意味します。
この概念は、1975年にジョージ・E・コリンズによって、それを計算するためのアルゴリズムとともに提唱された。
コリンズのアルゴリズムの計算複雑度はnに対して2倍の指数関数的である。これは上限値であり、ほとんどのエントリでこの上限値に達する。また、最小セル数が2倍の指数関数的になる例もあり、円筒代数分解の一般的なアルゴリズムはすべて2倍の指数関数的複雑度を持つことが示されている。
CADは、実数上の量化子消去法の効率的なバージョンであり、タルスキー・ザイデンベルク定理の元の証明から得られる計算複雑度よりもはるかに優れた計算複雑度を実現しています。コンピュータ上で実装できるほど効率的です。これは、計算実代数幾何学における最も重要なアルゴリズムの1つです。コリンズのアルゴリズムを改良したり、一般的に関心のある部分問題に対してより優れた計算複雑度を持つアルゴリズムを提供したりすることは、活発な研究分野となっています。