近似計算による代数的数の符号判定

• Item type: SIG Technical Reports(1)
• 公開日: 1997-05-16
• タイトル: 近似計算による代数的数の符号判定
• タイトル / 言語: en
• タイトル: A Method for Deciding the Signs of Algebraic Numbers Using Approximate Arithmetic
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院工学系研究科計数工学専攻
• 著者所属: 東京大学大学院工学系研究科計数工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physics, Graduate School of Engineering, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physics, Graduate School of Engineering, University of Tokyo
• 著者名: 日吉, 久礎; 杉原, 厚吉
• 著者名(英): Hisamoto, Hiyoshi; Kokichi, Sugihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 実代数的数を係数とする多項式f(_1，・・・，x_)および実代数的数α_1，・・・，α_nに対して，f（α_1，・・・，α_)の符号を判定する問題を考察する．従来のアプローチは，f（α_1，・・・，α_)を厳密計算によって求めて符号を判定するというものであった．これに対し，関川[5]は，機械区間演算と Mahler の measure を組み合わせた実代数的数の符号判定法を提案した，しかし，関川の符号判定法においては，符号判定の可能な精度を事前に知ることができなかった．本稿では，符号判定の可能な精度を事前に推定し，かつ機械区間演算の代わりに浮動小数点演算を用いる実代数的数の符号判定法を提案する．また，2つの方法を凸包を構成するための Graham のアルゴリズムに対して応用し，比較を行なう．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper considers the problem of deciding the sign of f(α_1,・・・,α_n) where f(x_1,・・・,x_n) is a given polynomial whose coefficients are real algebraic numbers and α_1,・・・,α_n are given real algebraic numbers. Approaches known so far are to decide the sign of f(α_1,・・・,α_n) using exact operations. Recently, Sekigawa [5] combined machine interval arithmetic with Mahler's measure and proposed a new method using approximation techniques. In his method, however, the required precision cannot be known in advance. The Method proposed in this paper, on the other hand, estimates the required precision in advance and uses floating point arithmeticf instead of machine interval arithmetic. The proposed method and Sekigawa's method are compared experimentally for Graham's algorithm for constructing convex hulls.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1997, 号 42(1997-AL-057), p. 17-24, 発行日 1997-05-16
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会