計算機代数(数式処理)において,入力に誤差を許容する(もしくは厳密な近傍を考慮する)代数的な性質を計算する,もしくは,数値計算の手法を導入する研究分野となる近似代数と,その周辺領域(制御理論や数値解析など)について,重点的に議論を行うワークショップを開催します。
今回は,近似GCDについての歴史から今後の展開,特にその理論的な背景の議論を中心に,近似代数に関連する分野の議論も含めて行いたいと考えています。近似GCDについての導入的講演も設定しますので,計算機代数(数式処理)について一定の知識を前提としますが,幅広い研究者の方の参加を歓迎します。
計算機代数(数式処理)に関する基礎的な資料を参考までに掲載します。
体上の多項式環でのGCDの基本的な性質(Euclidの互除法やHalf GCD,部分終結式写像など)と,そこにおいて近似GCDが導入された歴史と,いくつかの基本的なアルゴリズム(QRGCD,UVGCD,FastGCD,STLNベースなど)について紹介します。
制御工学で有名な補題としてKYP補題があるが,これを一般化したものとして原・岩崎による「一般化されたKYP補題」がある。本発表ではこの「一般化されたKYP補題」のパラメータを含んだシステムへの拡張について議論する。
点と直線の位置関係を判定することは,計算幾何学の問題を解く際に重要な役割を果たす。この位置関係判定問題は2D Orientation Problemと呼ばれ,行列式の符号で判定することができ,計算機で判定する際の精度と速度を求める研究が行われてきた。この講演では,この 2D Orientation Problemに対する既知の判定手法の紹介を行う。
前半に紹介した既知の判定手法を元に,その正確さや判定可能な問題の範囲について改善できることがわかった。そこでこの講演では,その改善方法について説明する。
近似GCDに特徴がある場合(微小主係数,巨大主係数など),近似GCD計算は(規則的に)不安定なふるまいをすることが知られている。本講演では,不安定になる原因について触れたうえで,不安定さを利用する試みを行う。
近似GCDを計算する問題は,最適化問題の一つとしても注目を集めてきました。本講演では,主に最適化の立場からの近似GCD計算に対するアプローチを,筆者の研究成果も含めて紹介します。
多項式のGCD計算は,基礎的な演算であり,厳密な場合も,誤差を含む場合も,様々な視点からの研究が行われてきています。本講演では,近似GCDを厳密なGCD計算の立場から見直し,今後に必要となる安定性の議論の方向性について議論を行いたいと思います。